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.)
Answer
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.
No comments:
Post a Comment