3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I wouldn't say zero but there is a (-1)! involved. Checking out again. $\endgroup$ – BCLC Jan 7 '15 at 22:10
2
$\begingroup$

No, to complete the proof along these lines you need to show that

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

you forgot that the upper number in the binomial coefficient changes when you go from $n$ to $n+1$.

You can rewrite $(1)$ as

$$(n-k+2)\binom{k-1}{k-1}+\sum_{i=1}^{n-k+1}i\left(\binom{n+1-i}{k-1}-\binom{n-i}{k-1}\right)=\binom{n+1}k\;,$$

whose lefthand side reduces to

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

by Pascal’s identity. This in turn can be rewritten as

$$n-k+2+\sum_{i=1}^{n-k+2}i\binom{n-i}{k-2}-(n-k+2)\binom{k-2}{k-2}=\sum_{i=1}^{n-k+2}i\binom{n-i}{k-2}\;.$$

If you took the right induction hypothesis — namely, that the equation holds for $n$ and all $k$ — then your induction hypothesis allows you to reduce this last summation to a single binomial coefficient, which proves to be the one that you want.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the clear proof. Indeed, I was calculating the expected value of the first element, but did not relate this to the second position. $\endgroup$ – Karsten W. Jan 9 '15 at 7:30

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.