Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, the most popular answer use the identity
$$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$

What’s the name of this identity? Is it the identity of the Pascal’s triangle modified.

How can we prove it? I tried by induction, but without success. Can we also prove it algebraically?

Thanks for your help.


EDIT 01 : This identity is known as the hockey-stick identity because, on Pascal’s triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.

Hockey-stick

Solutions Collecting From Web of "Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$"

This is purely algebraic. First of all, since $\dbinom{t}{k} =0$ when $k>t$ we can rewrite
$$\binom{n+1}{k+1} = \sum_{t=0}^{n} \binom{t}{k}=\sum_{t=k}^{n} \binom{t}{k}$$

Recall that (by the Pascal’s Triangle),
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Hence
$$\binom{t+1}{k+1} = \binom{t}{k} + \binom{t}{k+1} \implies \binom{t}{k} = \binom{t+1}{k+1} – \binom{t}{k+1}$$

Let’s get this summed by $t$:
$$\sum_{t=k}^{n} \binom{t}{k} = \sum_{t=k}^{n} \binom{t+1}{k+1} – \sum_{t=k}^{n} \binom{t}{k+1}$$

Let’s factor out the last member of the first sum and the first member of the second sum:
$$\sum _{t=k}^{n} \binom{t}{k}
=\left( \sum_{t=k}^{n-1} \binom{t+1}{k+1} + \binom{n+1}{k+1} \right)
-\left( \sum_{t=k+1}^{n} \binom{t}{k+1} + \binom{k}{k+1} \right)$$

Obviously $\dbinom{k}{k+1} = 0$, hence we get
$$\sum _{t=k}^{n} \binom{t}{k}
=\binom{n+1}{k+1}
+\sum_{t=k}^{n-1} \binom{t+1}{k+1}
-\sum_{t=k+1}^{n} \binom{t}{k+1}$$

Let’s introduce $t’=t-1$, then if $t=k+1 \dots n, t’=k \dots n-1$, hence
$$\sum_{t=k}^{n} \binom{t}{k}
= \binom{n+1}{k+1}
+\sum_{t=k}^{n-1} \binom{t+1}{k+1}
-\sum_{t’=k}^{n-1} \binom{t’+1}{k+1}$$

The later two arguments eliminate each other and you get the desired formulation
$$\binom{n+1}{k+1}
= \sum_{t=k}^{n} \binom{t}{k}
= \sum_{t=0}^{n} \binom{t}{k}$$

Imagine the first $n + 1$ numbers, written in order on a piece of paper. The right hand side asks in how many ways you can pick $k+1$ of them. In how many ways can you do this?

You first pick a highest number, which you circle. Call it $s$. Next, you still have to pick $k$ numbers, each less than $s$, and there are $\binom{s – 1}{k}$ ways to do this.

Since $s$ is ranging from $1$ to $n$, $t:= s-1$ is ranging from $0$ to $n$ as desired.

$$\begin{align}
\sum_{t=\color{blue}0}^n \binom{t}{k} =\sum_{t=\color{blue}k}^n\binom tk&= \sum_{t=k}^n\left[ \binom {t+1}{k+1}-\binom {t}{k+1}\right]\\
&=\sum_{t=\color{orange}k}^\color{orange}n\binom {\color{orange}{t+1}}{k+1}-\sum_{t=k}^n\binom t{k+1}\\
&=\sum_{t=\color{orange}{k+1}}^{\color{orange}{n+1}}\binom {\color{orange}{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}\quad\blacksquare\\
\end{align}$$

We can use the well known identity
$$1+x+\dots+x^n = \frac{x^{n+1}-1}{x-1}.$$
After substitution $x=1+t$ this becomes
$$1+(1+t)+\dots+(1+t)^n=\frac{(1+t)^{n+1}-1}t.$$
Both sides of these equations are polynomials in $t$. (Notice that the RHS simplifies to $\sum_{j=1}^{n+1}\binom {n+1}j t^{j-1}$.)

If we compare coefficient of $t^{k}$ on the LHS and the RHS we see that
$$\binom 0k + \binom 1k + \dots + \binom nk = \binom{n+1}{k+1}.$$


This proof is basically the same as the proof using generating functions, which was posted in other answers. However, I think it is phrased a bit differently. (And if it is formulated this way, even somebody who has never heard of generating functions can follow the proof.)

You can use induction on $n$, observing that

$$
\sum_{t=0}^{n+1} \binom{t}{k}
= \sum_{t=0}^{n} \binom{t}{k} + \binom{n+1}{k}
= \binom{n+1}{k+1} + \binom{n+1}{k}
= \binom{n+2}{k+1}
$$

The RHS is the number of $k+1$ subsets of $\{1,2,…,n+1\}$. Group them according to the largest element in the subset. Sum up all the cases. Get the LHS.

Another technique is to use snake oil. Call your sum:

$\begin{align}
S_k
&= \sum_{0 \le t \le n} \binom{t}{k}
\end{align}$

Define the generating function:

$\begin{align}
S(z)
&= \sum_{k \ge 0} S_k z^k \\
&= \sum_{k \ge 0} z^k \sum_{0 \le t \le n} \binom{t}{k} \\
&= \sum_{0 \le t \le n} \sum_{k \ge 0} \binom{t}{k} z^k \\
&= \sum_{0 \le t \le n} (1 + z)^t \\
&= \frac{(1 + z)^{n + 1} – 1}{(1 + z) – 1} \\
&= z^{-1} \left( (1 + z)^{n + 1} – 1 \right)
\end{align}$

So we are interested in the coefficient of $z^k$ of this:

$\begin{align}
[z^k] z^{-1} \left( (1 + z)^{n + 1} – 1 \right)
&= [z^{k + 1}] \left( (1 + z)^{n + 1} – 1 \right) \\
&= \binom{n + 1}{k + 1}
\end{align}$

We can use the integral representation of the binomial coefficient $$\dbinom{t}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{t}}{z^{k+1}}dz\tag{1}
$$ and get $$\sum_{t=0}^{n}\dbinom{t}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\sum_{k=0}^{n}\left(1+z\right)^{t}}{z^{k+1}}dz
$$ $$=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(z+1\right)^{n+1}}{z^{k+2}}dz-\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{1}{z^{k+2}}dz
$$ and so usign again $(1)$ we have $$\sum_{t=0}^{n}\dbinom{t}{k}=\dbinom{n+1}{k+1}-0=\color{red}{\dbinom{n+1}{k+1}.}$$