Proof of the hockey stick/Zhu Shijie identity \sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}\sum\limits_{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

Imagine the first n + 1 numbers, written in order on a piece of paper. The right hand side asks in how many ways you can pick k+1 of them. In how many ways can you do this?

You first pick a highest number, which you circle. Call it s. Next, you still have to pick k numbers, each less than s, and there are \binom{s – 1}{k} ways to do this.

Since s is ranging from 1 to n+1, t:= s-1 is ranging from 0 to n as desired.

Attribution
Source : Link , Question Author : hlapointe , Answer Author : darij grinberg

Leave a Comment