Saturday, July 7, 2018

discrete mathematics - Proof of the Hockey-Stick Identity: $sumlimits_{t=0}^n binom tk = binom{n+1}{k+1}$


After reading this question, the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$


What's the name of this identity? Is it the identity of the Pascal's triangle modified.


How can we prove it? I tried by induction, but without success. Can we also prove it algebraically?



Thanks for your help.



EDIT 01 : This identity is known as the hockey-stick identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.


Hockey-stick


Answer



This is purely algebraic. First of all, since $\dbinom{t}{k} =0$ when $k>t$ we can rewrite the identity in question as $$\binom{n+1}{k+1} = \sum_{t=0}^{n} \binom{t}{k}=\sum_{t=k}^{n} \binom{t}{k}$$


Recall that (by the Pascal's Triangle), $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$


Hence $$\binom{t+1}{k+1} = \binom{t}{k} + \binom{t}{k+1} \implies \binom{t}{k} = \binom{t+1}{k+1} - \binom{t}{k+1}$$


Let's get this summed by $t$: $$\sum_{t=k}^{n} \binom{t}{k} = \sum_{t=k}^{n} \binom{t+1}{k+1} - \sum_{t=k}^{n} \binom{t}{k+1}$$


Let's factor out the last member of the first sum and the first member of the second sum: $$\sum _{t=k}^{n} \binom{t}{k} =\left( \sum_{t=k}^{n-1} \binom{t+1}{k+1} + \binom{n+1}{k+1} \right) -\left( \sum_{t=k+1}^{n} \binom{t}{k+1} + \binom{k}{k+1} \right)$$


Obviously $\dbinom{k}{k+1} = 0$, hence we get $$\sum _{t=k}^{n} \binom{t}{k} =\binom{n+1}{k+1} +\sum_{t=k}^{n-1} \binom{t+1}{k+1} -\sum_{t=k+1}^{n} \binom{t}{k+1}$$



Let's introduce $t'=t-1$, then if $t=k+1 \dots n, t'=k \dots n-1$, hence $$\sum_{t=k}^{n} \binom{t}{k} = \binom{n+1}{k+1} +\sum_{t=k}^{n-1} \binom{t+1}{k+1} -\sum_{t'=k}^{n-1} \binom{t'+1}{k+1}$$


The latter two arguments eliminate each other and you get the desired formulation $$\binom{n+1}{k+1} = \sum_{t=k}^{n} \binom{t}{k} = \sum_{t=0}^{n} \binom{t}{k}$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...