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