# Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$

I'm looking for an algebraic proof of this identity for $n, k \in \mathbb{N}$:

$$\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$$

So far, I've turned the left hand side of the equality into $\frac{1}{k!}\sum\limits_{m=0}^{n-k} \frac{(m+k)!}{m!}$, but I got stuck there and can't get any further.

• Hint: This is the pascal's triangle column-sum property. Try to use induction. – NoChance Jul 27 '15 at 1:33
• If $i<k$ the binomial value is zero. I think you want to write in the top of the binomial something like $i+k$. – Masacroso Jul 27 '15 at 1:35

Let's examine $\displaystyle\sum_{k=0}^\infty\sum_{i=0}^n\binom{i}{k}x^k$. At the end, we'll look at the coefficient of $x^k$ to get our answer.

\begin{align} \sum_{k=0}^\infty\sum_{i=0}^n\binom ikx^k&=\sum_{i=0}^n\sum_{k=0}^\infty\binom ikx^k\\ &=\sum_{i=0}^n(1+x)^i\\ &=\frac{(1+x)^{n+1}-1}{(1+x)-1}\\ &=\frac{(1+x)^{n+1}-1}{x}\\ &=\frac{\sum_{j=0}^\infty\binom{n+1}j x^j-1}x\\ &=\frac{\sum_{j=\color{Red} 1}^\infty\binom{n+1}j x^j}x\\ &=\sum_{j=1}^\infty\binom{n+1}j x^{j-1}\\ &=\sum_{k=0}^\infty\binom{n+1}{k+1}x^k\\ \sum_{i=0}^n\binom{i}{k}&=\binom{n+1}{k+1} \end{align} The first step is The Most Powerful Proof Technique in Mathematics: switching the order of summation. (Which is why I had to put the extra $\sum$ sign in there. I can't switch the order of summation without two summations there in the first place.)

The $x^k$ term is there so I can get back the answer at the end. If I hadn't put it in there, I would have just ended up with $2^{n+1}-1$ at the end, which isn't very helpful.

• That technique works for a lot of sums, by the way. If there's another variable (i.e. $k$), multiply by $x^k$ and sum over it, and then switch the sigmas. If there isn't another variable (i.e. if the problem was $\sum\binom i{17}$), find a constant (i.e. $17$) and replace it by a variable, and then use the same strategy. – Akiva Weinberger Jul 27 '15 at 2:30
• I wouldn't dare say this is the most powerful technique in mathematics. It is useful, though. – Pedro Tamaroff Aug 1 '15 at 22:45
• @PedroTamaroff Yeah, I know. (I was quoting someone I know.) – Akiva Weinberger Aug 2 '15 at 7:56

Use induction on $n$. The relation $\displaystyle\sum_{i=k}^n\binom ik=\binom{n+1}{k+1}$ is trivially verified if $n=1$ (and $k\le n$).

Suppose, by inductive hypothesis, the formula is true for some $n\ge 1$ and $k\le n$. Then $$\sum_{i=k}^{n+1}\binom ik=\sum_{i=k}^n\binom ik+\binom {n+1}k=\binom{n+1}{k+1}+\binom {n+1}k = \binom{n+2}{k+1}.$$ If $k=n+1$, then the left-hand side is reduced to just one term: $\dbinom{n+1}{n+1}$, which is is equal to $\dbinom{n+2}{n+2}$.