HockeyStickFormula Intermediate

Problem - 4139

(Hockey Sticker Identity) Show that for any positive integer $n \ge k$, the following relationship holds: $$\binom{k}{k} +\binom{k+1}{k} + \binom{k+2}{k} + \cdots + \binom{n}{k} = \binom{n+1}{k+1} $$


The hockey stick identity can be visualized on a Pascal triangle.

Alternatively, it can also be proved by repeatedly applying the Pascal identity $\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}$ (# 3925). Note $C_k^k = C_{k+1}^{k+1}$, therefore

$$\begin{array}{rl} & \binom{k}{k} + \binom{k+1}{k} + \binom{k+2}{k} + \cdots + \binom{n-1}{k} + \binom{n}{k} \\ =& \binom{k+1}{k+1} + \binom{k+1}{k} + \binom{k+2}{k} + \cdots + \binom{n-1}{k} + \binom{n}{k}\\ = & \binom{k+2}{k+1} + \binom{k+2}{k} + \cdots + \binom{n-1}{k} + \binom{n}{k} \\ = & \binom{k+3}{k+1}+\cdots + \binom{n-1}{k} + \binom{n}{k} \\ =&\cdots \\ =& \binom{n-1}{k+1}+\binom{n-1}{k} + \binom{n}{k} \\ =& \binom{n-1}{k+1}+\binom{n}{k} \\ = & \binom{n+1}{k+1}\end{array}$$

report an error