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 and

Let's visualize this on the Pascal triangle for . We know that elements on the triangle are results of the binomial coefficient. For example is in , .

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

'Proof'

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

Let's say we have letters and we want to count all possible sets of letters from it. The answer to this is obviously . 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.: . Now for each we will take the -st letter and choose the remaining letters from the first letters. Let's visualize it:

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 and do the division using modulo-inverse.