<s>[INST] Sum of binomial coefficients with increasing $n$ Is there any formula for calculating $$\binom{n}{1} + \binom{n+1}{2} + \binom{n+2}{3} + ... + \binom{n+m}{m+1}$$
I have tried iterative method but is there any constant time method exist.
 [/INST] $\binom{n+1}{2} = \binom{n}{1} + \binom{n}{2} = \binom{n}{1} + \frac{n-1}{2} \binom{n}{1}$
$\binom{n+2}{3} = \binom{n+1}{2} + \binom{n+1}{3} = \binom{n+1}{2} + \frac{n-1}{2} \binom{n+1}{2}$
$\binom{n+3}{4} = \binom{n+2}{3} + \binom{n+2}{4} = \binom{n+2}{3} + \frac{n-1}{3} \binom{n+2}{3}$
...
...
$\binom{n+m}{m} = \binom{n+m-1}{m-1} + \binom{n+m-2}{m} = \binom{n+m-1}{m-1} + \frac{n-1}{m-1}\binom{n+m-1}{m-1} $
Start with $n$ and store each value starting from $\binom{n+1}{2}$ to calculate $\binom{n+2}{3}$ [O(1) operation] and so on.
</s>