Saturday, 30 April 2016

combinatorics - Proof that sumnk=0binomkp = binomn+1p+1




I am currently doing a little self study on difference sequences and they use the following identity nk=0(kp)=(n+1p+1)
I have never seen this identity without proof as if it is obvious, am I missing something is this an obvious result that perhaps is a consequence of some other theorem, if not could someone provide some intuition as to why this identity is true or even a proof. Any help is appreciated, thanks in advance.


Answer




It is more or less famously known as the hockey-stick identity. If you recall Pascal's triangle, notice that each number is the sum of the two above. Now take the orange number 84 below. It is the sum of the two above it: 84=56+28. Similarly, 28 is the sum of the two numbers above it, and then the sum above it etc. so that we end up with



3k=0(k6)=(47)



which more or less uses the definition of the binomial coefficient through Pascal's triangle.



enter image description here







If this is not so obvious, an induction proof isn't too hard:



n+1k=0(kp)=(n+1p)+nk=0(kp)=(n+1p)+(n+1p+1)=(n+2p+1)



The last step was the sum of two binomials equalling the next below it.



It is then clear that this holds for n=1 reqardless of p.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...