Combinatorics – Binomial Coefficients Identity Explained

binomial-coefficientscombinatoricssummation

I am trying to prove

$
\sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}=\binom{n+1}{k+1}
$

Whichever numbers for $k,n$ I try, the terms equal, but when I try to use induction by n, I fail to prove the induction step:

Assume the equation holds for $n$. Now by Pascal's recursion formula,

$
\binom{n+2}{k+1}=\binom{n+1}{k+1} + \binom{n+1}{k}\\
=\sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}+\binom{n+1}{k},
$

by induction assumption. In order to complete the proof, I would need to show

$
(n-k+2) \binom{n-(n-k+2)}{k-1} = \binom{n+1}{k}
$

but the left-hand side is zero. What am I doing wrong?

EDIT:

There were links to similar questions when my question was marked as duplicate. However, these links are now gone, so I add them here as they were useful to me:

(I did search, but did not found these.)

Best Answer

Let's give a combinatorial proof.

$\binom{n+1}{k+1}$ is the number of subsets of $[n] = \{0,1,2, \ldots, n\}$ having exactly $k+1$ elements. Looking at the smallest or largest element of such a subset makes sense.

Let's look at the second smallest element instead. It can be any number from $1$ (for subsets which have $0$ and $1$ as their two smallest elements) to $n-k+1$ (for subsets which have $n-k+1, \ldots, n-1, n$ as their $k$ largest elements).

So $$\binom{n+1}{k+1} = \sum_{i=1}^{n-k+1} \textrm{number of subsets having $i$ as 2nd smallest element}.$$

So how many $(k+1)$-element subsets of $[n]$ have $i$ as 2nd smallest elements?

Well, the recipe to make such a subset is clear:

  1. Chose any number in $0, 1, \ldots, i-1$ to serve as smallest element.
  2. Pick $i$ as second smallest element.
  3. Pick any $(k-1)$-element subset of $\{i+1, \ldots, n\}$ to serve as the $n-1$ elements larger than $i$.

In the first step, you have $i$ choices, the second step involves no choice and you have $\binom{n-i}{k-1}$ choices in the last step, because $\{i+1, \ldots, n\}$ has $n-i$ elements.

So the number of $(k+1)$-element subsets of $[n]$ having $i$ in second position is $i \binom{n-i}{k-1}$, which proves that $$\binom{n+1}{k+1} = \sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}.$$

A slight generalisation of this proof shows that if $a+b=k$ $$ \binom{n+1}{k+1} = \sum_i \binom{i}{a}\binom{n-i}{b}:$$ you only have to look at the $(a+1)$-th largest element of the $(k+1)$-element subsets of $n+1$. We have just done the $a=1$ case.

Related Question