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:
- How do i reduce this expression of binomial coefficients -- hint to Vandermont's identity
- Closed form for a formula with a summation over i(n−ik−1), and combinatorial proof? -- basically the same question, but two days earlier.
(I did search, but did not found these.)