Wednesday, 21 September 2016

combinatorics - Binomial coefficients identity: sumibinomnik1=binomn+1k+1



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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...