I am currently doing a little self study on difference sequences and they use the following identity \sum_{k=0}^n \binom{k}{p}= \binom{n+1}{p+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
\sum_{k=0}^3\binom k6=\binom47
which more or less uses the definition of the binomial coefficient through Pascal's triangle.
If this is not so obvious, an induction proof isn't too hard:
\sum_{k=0}^{n+1}\binom kp=\binom{n+1}p+\sum_{k=0}^n\binom kp=\binom{n+1}p+\binom{n+1}{p+1}=\binom{n+2}{p+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