k-dx's blog

By k-dx, history, 7 weeks ago,

Hockey Stick Identity — easy explanation

In this post I explain what Hockey Stick Identity (also reffered to as parallel summing) is, visualize it and present an intuitive 'proof'.

What is Hockey Stick Identity?

For whole numbers $n$ and $r$ $(n \geq r),$

$\displaystyle \sum\limits_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1} .$

Let's visualize this on the Pascal triangle for $n = 6, r = 2$. We know that elements on the triangle are results of the binomial coefficient. For example $\binom{6}{2} = 15$ is in $\color{blue}{\text{row}}$ $6$, $\color{orange}{\text{column}}$ $2$.

Do you see it? It resembles a hockey stick! Hence the name.

\begin{align} \color{green}{ \sum\limits_{k=2}^{6} \binom{k}{2} } &= \color{red}{ \binom{6+1}{2+1} } \\ \color{green}{ \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} + \binom{6}{2} } &= \color{red}{ \binom{7}{3} } \\ \color{green}{ 1 + 3 + 6 + 10 + 15 } &= \color{red}{ 35 } \end{align}

'Proof'

Idea for this part has been very kindly suggested by my friend hugo4CF.

Let's say we have $n + 1 = 7$ letters $(A, B, C, D, E, F, G)$ and we want to count all possible sets of $r + 1 = 3$ letters from it. The answer to this is obviously $\displaystyle \binom{7}{3} = 35$. That is the right side of our equation. But we can count it differently. Let's put our letters in a row (the order doesn't matter), e. g.: $(E, G, A, D, F, B, C)$. Now for each $k \in \lbrace r, r + 1, \dots, n \rbrace = \lbrace 2, 3, 4, 5, 6 \rbrace$ we will take the $\color{magenta}{k+1}$-st letter and choose the remaining $r = 2$ letters from the first $k$ letters. Let's visualize it:

k row of letters result
2 ($\underbrace{\textbf{E, G}}_{\binom{2}{2}}, \color{magenta}{\textbf{A}}$, D, F, B, C) $\displaystyle\color{green}{\binom{2}{2}}$
3 ($\underbrace{\textbf{E, G, A}}_{\binom{3}{2}}, \color{magenta}{\textbf{D}}$, F, B, C) $\displaystyle\color{green}{\binom{3}{2}}$
4 ($\underbrace{\textbf{E, G, A, D}}_{\binom{4}{2}}, \color{magenta}{\textbf{F}}$, B, C) $\displaystyle\color{green}{\binom{4}{2}}$
5 ($\underbrace{\textbf{E, G, A, D, F}}_{\binom{5}{2}}, \color{magenta}{\textbf{B}}$, C) $\displaystyle\color{green}{\binom{5}{2}}$
6 ($\underbrace{\textbf{E, G, A, D, F, B}}_{\binom{6}{2}}, \color{magenta}{\textbf{C}}$) $\displaystyle\color{green}{\binom{6}{2}}$

This way we get our left side of the equation.

Application

This identity is used in problem 660E - Different Subsets For All Tuples. Leave a comment if you know other problems for it.

In practice

Naturally, if we want to calculate the binomial, we can for example use the formula $\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$ and do the division using modulo-inverse.

• +74

 » 6 weeks ago, # |   0 Nice explanation.
 » 6 weeks ago, # |   0 A possible solution of 1549E — The Three Little Pigs also uses this ;p
 » 5 weeks ago, # |   +9 A recent problem that uses this identity.
 » 5 weeks ago, # |   +6 Mr Chesca would be proud!
 » 5 weeks ago, # |   0 Helpful