La función SuperSuma se define como: SuperSuma(0,n)=nSuperSuma(0,n)=n, para todo n positivo SuperSuma(k,n)=SuperSu

Question

La función SuperSuma se define como:

    SuperSuma(0,n)=nSuperSuma(0,n)=n, para todo n positivo

    SuperSuma(k,n)=SuperSuma(k−1,1)+SuperSuma(k−1,2)+...+SuperSuma(k−1,n)SuperSuma(k,n)=SuperSuma(k−1,1)+SuperSuma(k−1,2)+...+SuperSuma(k−1,n), para todo entero positivo k,nk,n.

Dados k,nk,n, devuelva el valor para SuperSuma(k,n)SuperSuma(k,n).

Answer 1

Ah, this one is interesting. Recall the Hockey-stick identity:
https://en.m.wikipedia.org/wiki/Hockey-stick_identity

And the fortunate fact that SuperSuma(1, n) = n(n+1)/2 = choose(n+1, 2) by Gauss.

By induction you get SuperSuma(k, n) = choose(n + k, k + 1).

Now all you have to do is cook up a choose function that doesn't blow up for large inputs, so beware to reinterpret C(2000, 1999) as C(2000, 1) to avoid performance loss.