prove-for-r-n-N-k-r-n-k-r-n-1-r-1-Hockey-stick-identity-

Question Number 185659 by mr W last updated on 25/Jan/23

p r o v e f o r r, n \in N

\underset{k = r}{\sum^{n}} (\begin{matrix} k \\ r \end{matrix}) = (\begin{matrix} n + 1 \\ r + 1 \end{matrix})

(H o c k e y - s t i c k i d e n t i t y)

Commented by mr W last updated on 25/Jan/23

Answered by mr W last updated on 25/Jan/23

(\begin{matrix} n + 1 \\ r + 1 \end{matrix})

= (\begin{matrix} n \\ r \end{matrix}) + (\begin{matrix} n \\ r + 1 \end{matrix})

= (\begin{matrix} n \\ r \end{matrix}) + (\begin{matrix} n - 1 \\ r \end{matrix}) + (\begin{matrix} n - 1 \\ r + 1 \end{matrix})

= (\begin{matrix} n \\ r \end{matrix}) + (\begin{matrix} n - 1 \\ r \end{matrix}) + (\begin{matrix} n - 2 \\ r \end{matrix}) + (\begin{matrix} n - 2 \\ r + 1 \end{matrix})

\dots \dots

= (\begin{matrix} n \\ r \end{matrix}) + (\begin{matrix} n - 1 \\ r \end{matrix}) + (\begin{matrix} n - 2 \\ r \end{matrix}) + \dots + (\begin{matrix} r + 1 \\ r \end{matrix}) + (\begin{matrix} r + 1 \\ r + 1 \end{matrix})

= (\begin{matrix} n \\ r \end{matrix}) + (\begin{matrix} n - 1 \\ r \end{matrix}) + (\begin{matrix} n - 2 \\ r \end{matrix}) + \dots + (\begin{matrix} r + 1 \\ r \end{matrix}) + (\begin{matrix} r \\ r \end{matrix})

= \underset{k = r}{\sum^{n}} (\begin{matrix} k \\ r \end{matrix})

Commented by cortano1 last updated on 25/Jan/23

y e s \dots g r e a t