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.
 A: $\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.
A: Let's add in an initial value of $1 = \binom{n}{0}$.  The fundamental relationship
$$\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}\tag{1}$$
makes the sum telescope:
$$\eqalign{
&\color{Blue}{\binom{n}{0} + \binom{n}{1}}  &+\binom{n+1}{2} &+ \binom{n+2}{3}  + \cdots &+ \binom{n+m}{m+1} \\
& =\color{Blue}{\binom{n+1}{1}} & +\color{Blue}{\binom{n+1}{2}} &+ \binom{n+2}{3} + \cdots &+ \binom{n+m}{m+1} \\
& &=\color{Blue}{\binom{n+2}{2}} & +\color{Blue}{\binom{n+2}{3}}+ \cdots &+ \binom{n+m}{m+1} \\
& & & = \cdots \\
& & & = \color{Blue}{\binom{n+m}{m}} &+\color{Blue}{ \binom{n+m}{m+1}} \\
& & & &= \color{Blue}{\binom{n+m+1}{m+1}}.
}$$
Subtracting the $1$ originally added in gives the answer, $\binom{n+m+1}{m+1}-1$.

Antoni Parellada kindly points out (in a comment below) that this fundamental relationship $(1)$ is now often called "Pascal's Rule."  This appendix shows how intimately connected that eponym is with the present question.
Here, from Pascal's Complete Works (republished by Hachette, Paris, in 1858 as Oeuvres Completes), is his original diagram of the "Arithmetical Triangle" as it appeared in the Traité du Triangle Arithmetique (1654).
 
Pascal has labeled many of the cells with Greek and latin letters for reference.  After giving its rule of construction--the fundamental relationship above--he draws 18 "consequences."  The second consequence is the present result.  Like many of his time, Pascal's proof proceeds by demonstrating the relationship for a specific case in a way that obviously generalizes:

(From a translation at http://cerebro.xu.edu/math/Sources/Pascal/Sources/arith_triangle.pdf.  I discovered the original some years ago on the Cambridge University Library Web site but apparently it has been put behind a private wall since then.)  It's a nice graphical way to display the telescoping.
