4
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Akiva Weinberger Jul 27 '15 at 2:30
  • 1
    $\begingroup$ I wouldn't dare say this is the most powerful technique in mathematics. It is useful, though. $\endgroup$ – Pedro Tamaroff Aug 1 '15 at 22:45
  • $\begingroup$ @PedroTamaroff Yeah, I know. (I was quoting someone I know.) $\endgroup$ – Akiva Weinberger Aug 2 '15 at 7:56
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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