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

  • 6
    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
  • 4
    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

13 Answers 13

up vote 15 down vote accepted

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

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

  • Do you mean $s$ is ranging from $1$ to $n+1$? – Rockstar5645 Jun 2 '17 at 17:07

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

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

  • 2
    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

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.

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

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

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
  • 1
    @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.

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ Assuming $\ds{M \geq 0}$:

\begin{equation} \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} \end{equation}


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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.