Hockey-stick identity

We have

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

Let ${\displaystyle X=1+x}$, and compare coefficients of ${\displaystyle x^{r}}$.

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}.}$

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}.}$

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}}}$

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}}.}$

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 divide this into ${\displaystyle n-k+1}$ disjoint cases. In general, in case ${\displaystyle x}$, ${\displaystyle 1\leqslant x\leqslant n-k+1}$, 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 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}}.}$