Using sigma notation, the identity states

${\displaystyle \sum _{i=r}^{n}{i \choose r}={n+1 \choose r+1}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r}$ 

or equivalently, the mirror-image by the substitution ${\displaystyle j\to i-r}$ :

${\displaystyle \sum _{j=0}^{n-r}{j+r \choose r}=\sum _{j=0}^{n-r}{j+r \choose j}={n+1 \choose n-r}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r.}$ 

Generating function proof edit

Let ${\displaystyle X=1+x}$ . Then, by the partial sum formula for geometric series, we find that

${\displaystyle X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}={\frac {X^{n+1}-X^{r}}{x}}}$ .

Further, by the binomial theorem, we also find that

${\displaystyle X^{r+k}=(1+x)^{r+k}=\sum _{i=0}^{r+k}{\binom {r+k}{i}}x^{i}}$ .

Note that this means the coefficient of ${\displaystyle x^{r}}$  in ${\displaystyle X^{r+k}}$  is given by ${\displaystyle {\binom {r+k}{r}}}$ .

Thus, the coefficient of ${\displaystyle x^{r}}$  in the left hand side of our first equation can be obtained by summing over the coefficients of ${\displaystyle x^{r}}$  from each term, which gives

${\displaystyle \sum _{k=0}^{n-r}{\binom {r+k}{r}}}$ 

Similarly, we find that the coefficient of ${\displaystyle x^{r}}$  on the right hand side is given by the coefficient of ${\displaystyle x^{r+1}}$  in ${\displaystyle X^{n+1}-X^{r}}$ , which is

${\displaystyle {\binom {n+1}{r+1}}-{\binom {r}{r+1}}={\binom {n+1}{r+1}}}$ 

Therefore, we can compare the coefficients of ${\displaystyle x^{r}}$  on each side of the equation to find that

${\displaystyle \sum _{k=0}^{n-r}{\binom {r+k}{r}}={\binom {n+1}{r+1}}}$ 

Inductive and algebraic proofs edit

The inductive and algebraic proofs both make use of Pascal's identity:

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}$ 

Inductive proof edit

This identity can be proven by mathematical induction on ${\displaystyle n}$ .

Base case Let ${\displaystyle n=r}$ ;

${\displaystyle \sum _{i=r}^{n}{i \choose r}=\sum _{i=r}^{r}{i \choose r}={r \choose r}=1={r+1 \choose r+1}={n+1 \choose r+1}.}$ 

Inductive step Suppose, for some ${\displaystyle k\in \mathbb {N} ,k\geqslant r}$ ,

${\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}}$ 

Then

${\displaystyle \sum _{i=r}^{k+1}{i \choose r}=\left(\sum _{i=r}^{k}{i \choose r}\right)+{k+1 \choose r}={k+1 \choose r+1}+{k+1 \choose r}={k+2 \choose r+1}.}$ 

Algebraic proof edit

We use a telescoping argument to simplify the computation of the sum:

${\displaystyle {\begin{aligned}\sum _{t=\color {blue}0}^{n}{\binom {t}{k}}=\sum _{t=\color {blue}k}^{n}{\binom {t}{k}}&=\sum _{t=k}^{n}\left[{\binom {t+1}{k+1}}-{\binom {t}{k+1}}\right]\\&=\sum _{t=\color {green}k}^{\color {green}n}{\binom {\color {green}{t+1}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&=\sum _{t=\color {green}{k+1}}^{\color {green}{n+1}}{\binom {\color {green}{t}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&={\binom {n+1}{k+1}}-\underbrace {\binom {k}{k+1}} _{0}&&{\text{by telescoping}}\\&={\binom {n+1}{k+1}}.\end{aligned}}}$ 

Combinatorial proofs edit

Proof 1 edit

Imagine that we are distributing ${\displaystyle n}$  indistinguishable candies to ${\displaystyle k}$  distinguishable children. By a direct application of the stars and bars method, there are

${\displaystyle {\binom {n+k-1}{k-1}}}$ 

ways to do this. Alternatively, we can first give ${\displaystyle 0\leqslant i\leqslant n}$  candies to the oldest child so that we are essentially giving ${\displaystyle n-i}$  candies to ${\displaystyle k-1}$  kids and again, with stars and bars and double counting, we have

${\displaystyle {\binom {n+k-1}{k-1}}=\sum _{i=0}^{n}{\binom {n+k-2-i}{k-2}},}$ 

which simplifies to the desired result by taking ${\displaystyle n'=n+k-2}$  and ${\displaystyle r=k-2}$ , and noticing that ${\displaystyle n'-n=k-2=r}$ :

${\displaystyle {\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.}$ 

Proof 2 edit

We can form a committee of size ${\displaystyle k+1}$  from a group of ${\displaystyle n+1}$  people in

${\displaystyle {\binom {n+1}{k+1}}}$ 

ways. Now we hand out the numbers ${\displaystyle 1,2,3,\dots ,n-k+1}$  to ${\displaystyle n-k+1}$  of the ${\displaystyle n+1}$  people. We can then divide our committee-forming process into ${\displaystyle n-k+1}$  exhaustive and disjoint cases based on the committee member with the lowest number, ${\displaystyle x}$ . Note that there are only ${\displaystyle k}$  people without numbers, meaning we must choose at least one person with a number in order to form a committee of ${\displaystyle k+1}$  people. In general, in case ${\displaystyle x}$ , person ${\displaystyle x}$  is on the committee and persons ${\displaystyle 1,2,3,\dots ,x-1}$  are not on the committee. The rest of the committee can then be chosen in

${\displaystyle {\binom {n-x+1}{k}}}$ 

ways. Now we can sum the values of these ${\displaystyle n-k+1}$  disjoint cases, and using double counting, we obtain

${\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n-1}{k}}+{\binom {n-2}{k}}+\cdots +{\binom {k+1}{k}}+{\binom {k}{k}}.}$ 

• Pascal's identity
• Pascal's triangle
• Leibniz triangle
• Vandermonde's identity
• Faulhaber's formula, for sums of arbitrary polynomials.

• On AOPS
• On StackExchange, Mathematics
• Pascal's Ladder on the Dyalog Chat Forum