# 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.

• It is sometimes called the "hockey stick". – user940 Oct 21 '15 at 15:24
• There is another cute graphical illustration on the plane of $\binom{n}{k}$ – Eli Korvigo Oct 21 '15 at 16:54
• It's pretty straightforward from the picture. Just switch the $1$ at the top of the stick with the $1$ directly below, then repeatedly replace adjacent numbers with the number in the cell below. This can be translated into a formal proof with words and symbols, but an animation or series of pictures is much more effective. – user2357112 Oct 22 '15 at 3:24
• See also this question. Some post which are linked there might be of interest, too. – Martin Sleziak Jan 18 '16 at 15:05

This is purely algebraic. First of all, since $$\dbinom{t}{k} =0$$ when $$k>t$$ we can rewrite the identity in question as $$\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 latter 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}$$

• Beautiful proof. p.-s. you can use the LaTeX command \binom{n}{k} to display $\binom{n}{k}$. – hlapointe Oct 21 '15 at 16:26
• @hlapointe thank you. Sure, I forgot there was a special command for binomial. – Eli Korvigo Oct 21 '15 at 16:32

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+1$$, $$t:= s-1$$ is ranging from $$0$$ to $$n$$ as desired.

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.)

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

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

• How can you say that $\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}$ in your proof. – hlapointe Oct 21 '15 at 15:13
• That's the inductive hypothesis. – Michael Biro Oct 21 '15 at 15:14
• Ok. Can we prove it algebraically? – hlapointe Oct 21 '15 at 15:15
• What's the first step!? Because if I take $n=1$, the hypothesis seem to be incorrect. – hlapointe Oct 21 '15 at 15:21
• @hlapointe One choice of base case for every fixed $k$ is that $\sum_{t=0}^{k} \binom{t}{k} = \binom{k}{k} = 1 = \binom{k+1}{k+1}$. – Michael Biro Oct 21 '15 at 16:28

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

• It is so nice and weird. +1 – Behrouz Maleki Jul 5 '16 at 10:27
• +1. Nice work. You must subtract $\displaystyle{\delta_{k,-1}}$ in order to take account of the case $\displaystyle{k = -1}$. When $\displaystyle{k = -1}$, the LHS is equal to $\displaystyle{0}$ and your RHS is equal to $\displaystyle{1}$. With the $\displaystyle{\delta_{k,-1}}$ you'll get $\displaystyle{1 - 1 = 0}$. – Felix Marin Jul 6 '16 at 21:50

In this answer, I prove the identity $$\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}\tag{1}$$ Here is a generalization of the identity in question, proven using the Vandermonde Identity \begin{align} \sum_{m=0}^M\binom{m+k}{k}\binom{M-m}{n} &=\sum_{m=0}^M\binom{m+k}{m}\binom{M-m}{M-m-n}\tag{2}\\ &=\sum_{m=0}^M(-1)^m\binom{-k-1}{m}(-1)^{M-m-n}\binom{-n-1}{M-m-n}\tag{3}\\ &=(-1)^{M-n}\sum_{m=0}^M\binom{-k-1}{m}\binom{-n-1}{M-m-n}\tag{4}\\ &=(-1)^{M-n}\binom{-k-n-2}{M-n}\tag{5}\\ &=\binom{M+k+1}{M-n}\tag{6}\\ &=\binom{M+k+1}{n+k+1}\tag{7} \end{align} Explanation:
$(2)$: $\binom{n}{k}=\binom{n}{n-k}$
$(3)$: apply $(1)$ to each binomial coefficient
$(4)$: combine the powers of $-1$ which can then be pulled out front
$(5)$: apply Vandermonde
$(6)$: apply $(1)$
$(7)$: $\binom{n}{k}=\binom{n}{n-k}$

To get the identity in the question, set $n=0$.

• @FoF: I have added a link here and answered your other question. Thanks for mentioning the difficulty. – robjohn Dec 7 '13 at 12:33
• @FoF: That is the Vandermonde Identity that I mentioned at the beginning. – robjohn Dec 8 '13 at 18:56
• @FoF: I added an explanation for each line. – robjohn Dec 9 '13 at 2:20
• I answered my own question about $(5, 6$) here. – NaN Dec 10 '13 at 8:54
• @FoF: Ah. That is why I added the Explanation when I saw difficulty in following the argument. – robjohn Dec 11 '13 at 7:46

You remember that: $$(1+x)^m = \sum_k \binom{m}{k} x^k$$ So the sum $$\sum_{m=0}^M \binom{m+k}{k}$$ is the coefficient of $x^k$ in: $$\sum_{m=0}^M (1+x)^{m+k}$$ Yes? So now use the geometric series formula given: $$\sum_{m=0}^M (1+x)^{m+k} = -\frac{(1+x)^k}{x} \left( 1 - (1+x)^{M+1} \right)$$ And now you want to know what is coefficient of $x^k$ in there. You got it from here.

Recall that for $k\in\Bbb N$ we have the generating function

$$\sum_{n\ge 0}\binom{n+k}kx^n=\frac1{(1-x)^{k+1}}\;.$$

The identity in the question can therefore be rewritten as

$$\left(\sum_{n\ge 0}\binom{n+k}kx^n\right)\left(\sum_{n\ge 0}x^n\right)=\sum_{n\ge 0}\binom{n+k+1}{k+1}x^n\;.$$

The coefficient of $x^n$ in the product on the left is

$$\sum_{i=0}^n\binom{i+k}k\cdot1=\sum_{i=0}^n\binom{i+k}k\;,$$

and the $n$-th term of the discrete convolution of the sequences $\left\langle\binom{n+k}k:n\in\Bbb N\right\rangle$ and $\langle 1,1,1,\dots\rangle$. And at this point you’re practically done.

• Is there a typo in the second equation (first sum)? I believe $k$ should be indexed. – AlanH May 27 '13 at 6:20
• @Alan: No, the sum is over $n$; $k$ is fixed throughout. – Brian M. Scott May 27 '13 at 7:19
• In my text, I have an identity $\sum_{r\geq 0} \binom{r + n}{r} x^r = 1/(1-x)^{n+1}$ This may be the cause of my confusion, but is this identity correct and is it equivalent to the one you used? – AlanH May 27 '13 at 8:22
• @Alan: Sure: your $r$ is my $n$, and your $n$ is my $k$. – Brian M. Scott May 27 '13 at 8:28
• @Alan: $\binom{r+n}r=\binom{r+n}n$; now do the translation. (Sorry: I didn’t notice before that you’d used the symmetrically opposite binomial coefficient.) – Brian M. Scott May 27 '13 at 19:19

A standard technique to prove such identities $\sum_{i=0}^Mf(i)=F(M)$, involving on one hand a sum where only the upper bound $M$ is variable and on the other hand an explicit expression in terms of$~M$, is to use induction on$~M$. It amounts to showing that $f(M)=F(M)-F(M-1)$ (and that $F(0)=f(0)$). This is similar to using the fundamental theorem of calculus in showing that $\int_0^{x_0}f(x)\mathrm dx=F(x_0)$ by establishing $f(x)=F'(x)$ (and $F(0)=0$).

So here you need to check (apart from the obvious starting case $M=0$) that $\binom{M+k}k=\binom{M+k+1}{k+1}-\binom{M+k}{k+1}$. This is just in instance of Pascal's recurrence for binomial coefficients.


$$\mbox{Note that}\quad \sum_{m = 0}^{M}{m + k \choose k} = \sum_{m = k}^{M + k}{m \choose k} = a_{M + k} - a_{k - 1}\quad\mbox{where}\quad a_{n} \equiv \sum_{m = 0}^{n}{m \choose k}\tag{1}$$

Then, \begin{align} \color{#f00}{a_{n}} & \equiv \sum_{m = 0}^{n}{m \choose k} = \sum_{m = 0}^{n}\ \overbrace{% \oint_{\verts{z} = 1}{\pars{1 + z}^{m} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}} ^{\ds{m \choose k}}\ =\ \oint_{\verts{z} = 1}{1 \over z^{k + 1}}\sum_{m = 0}^{n}\pars{1 + z}^{m} \,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1}{1 \over z^{k + 1}}\, {\pars{1 + z}^{n + 1} - 1 \over \pars{1 + z} - 1}\,{\dd z \over 2\pi\ic}\ =\ \underbrace{\oint_{\verts{z} = 1}{\pars{1 + z}^{n + 1} \over z^{k + 2}} \,{\dd z \over 2\pi\ic}}_{\ds{n + 1 \choose k + 1}}\ -\ \underbrace{\oint_{\verts{z} = 1}{1 \over z^{k + 2}}\,{\dd z \over 2\pi\ic}} _{\ds{\delta_{k + 2,1}}} \\[8mm] \imp\ \color{#f00}{a_{n}} & = \fbox{$\ds{\quad% {n + 1 \choose k + 1} - \delta_{k,-1}\quad}$} \end{align}
\begin{align} \mbox{With}\ \pars{1}\,,\quad \color{#f00}{\sum_{m = 0}^{M}{m + k \choose k}} & = \bracks{{M + k + 1 \choose k + 1} - \delta_{k,-1}} - \bracks{{k \choose k + 1} - \delta_{k,-1}} \\[3mm] & = {M + k + 1 \choose k + 1} - {k \choose k + 1} \end{align} Thanks to $\ds{@robjohn}$ user who pointed out the following feature: $${k \choose k + 1} = {-k + k + 1 - 1 \choose k + 1}\pars{-1}^{k + 1} = -\pars{-1}^{k}{0 \choose k + 1} = \delta_{k,-1}$$ such that $$\begin{array}{|c|}\hline\mbox{}\\ \ds{\quad\color{#f00}{\sum_{m = 0}^{M}{m + k \choose k}} = \color{#f00}{{M + k + 1 \choose k + 1} - \delta_{k,-1}}\quad} \\ \mbox{}\\ \hline \end{array}$$

• Since $k=-1$ is covered in the first part, it should be noted that since $\binom{-1}{0}=1$, $$\binom{k}{k+1}-\delta_{k,-1}=0$$ therefore the final answer seems it should be $$\binom{M+k+1}{k+1}-\delta_{k,-1}$$ – robjohn Jul 25 '16 at 13:00
• @robjohn Thanks. I'm checking everything right now. – Felix Marin Jul 25 '16 at 21:48
• @robjohn Thanks. Fixed. – Felix Marin Jul 25 '16 at 22:09

We can prove this by counting in two ways.

Let $$S$$ be the set of all $$(k+1)$$-element subsets of $$[n+1]$$. By definition, $$|S|=\binom{n+1}{k+1}$$.

Let $$S_i$$ be the set of all $$(k+1)$$-element subsets of $$[n+1]$$ such that the largest element is $$i+1$$. Picking $$k+1$$ elements from $$[n+1]$$ such that the largest element is $$i+1$$ is a two-step-process.

(Step 1) Pick $$i+1$$. The number of way(s) to do this is $$\binom{1}{1}$$.

(Step 2) Pick the $$k$$ elements from the the remaining $$i$$ elements. The number of way(s) to do this is $$\binom{i}{k}$$.

Therefore, $$|S_i|=\binom{1}{1}\binom{i}{k}=\binom{i}{k}$$. Since we can see that $$S_k, S_{k+1}, S_{k+2}, \dots, S_n$$ partition $$S$$, we have that $$\begin{gather*} \sum_{i=k}^n|S_i|=|S|\\ \sum_{i=k}^n\binom{i}{k}=\binom{n+1}{k+1} \end{gather*}$$ Since we know that if $$i < k$$, then $$\binom{i}{k}=0$$, we can say that $$\sum_{i=k}^n\binom{i}{k}=\sum_{i=0}^n\binom{i}{k}$$. Therefore, we have $$\begin{gather*} \sum_{i=0}^n \binom{i}{k} = \binom{n+1}{k+1} \end{gather*}$$