Hockey Stick Identity

The hockey stick identity is an identity regarding sums of binomial coefficients.

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

$$\sum_{k=r}^{n}\binom{k}{r} = \binom{n+1}{r+1}. \ _\square$$

The hockey stick identity gets its name by how it is represented in Pascal's triangle.

In Pascal's triangle, the sum of the elements in a diagonal line starting with $1$ is equal to the next element down diagonally in the opposite direction. Circling these elements creates a "hockey stick" shape:

$$1+3+6+10=20.$$

The hockey stick identity is a special case of Vandermonde's identity. It is useful when a problem requires you to count the number of ways to select the same number of objects from different-sized groups. It is also useful in some problems involving sums of powers of natural numbers.

The hockey stick identity is often used in counting problems in which the same amount of objects is selected from different-sized groups.

Treating each of the balls in the figure below as distinct, how many ways are there to select 3 balls from the same horizontal row?

---

The smallest row has 3 balls and the largest row has 9 balls. The number of ways to select 3 balls from the same row can be expressed as a sum of binomial coefficients. This can then be computed with the hockey stick identity:

$$\sum\limits_{k=3}^{9}\binom{k}{3} = \binom{10}{4} = 210.$$

So, there are $\color{#D61F06}{210}$ ways to select 3 balls from the same row. $_\square$

You might have noticed that Pascal's triangle contains all of the positive integers in a diagonal line.

Each of these elements corresponds to the binomial coefficient $\binom{n}{1},$ where $n$ is the row of Pascal's triangle. The sum of all positive integers up to $n$ is called the $n^\text{th}$ triangular number. It can be represented as

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

These two expressions are equivalent because $k=\binom{k}{1}.$ As this sum can be expressed as the sum of binomial coefficients, it can be computed with the hockey stick identity:

The sum of the first $n$ positive integers is

$$\sum\limits_{k=1}^{n}{k}=\sum\limits_{k=1}^{n}\binom{k}{1}=\binom{n+1}{2}.\ _\square$$

This leads to the more well-known formula for triangular numbers.

The sum of the first $n$ positive integers is

$$\sum\limits_{k=1}^{n}{k}=\binom{n+1}{2}=\frac{(n+1)!}{(n-1)!(2)!}=\frac{n(n+1)}{2}.\ _\square$$

Since each triangular number can be represented with a binomial coefficient, the hockey stick identity can be used to calculate the sum of triangular numbers.

The sum of the first $n$ triangular numbers is

$$\sum\limits_{k=1}^{n}\sum\limits_{j=1}^{k}{j}=\sum\limits_{k=1}^{n}\binom{k+1}{2}=\binom{n+2}{3}.\ _\square$$

This can also be represented algebraically.

The sum of the first $n$ triangular numbers is

$$\sum\limits_{k=1}^{n}\sum\limits_{j=1}^{k}{j}=\binom{n+2}{3}=\frac{(n+2)!}{(n-1)!(3)!}=\frac{n(n+1)(n+2)}{6}.\ _\square$$

The hockey stick identity can be used to develop the identities for sums of powers of natural numbers.

The sum of the squares of the first $n$ positive integers is

$$\sum\limits_{k=1}^{n}{k^2}=\frac{n(n+1)(2n+1)}{6}=2\binom{n+2}{3}-\binom{n+1}{2}.\ _\square$$

Recall from the previous example that the identities for the sum of the first $n$ positive integers is

$$\sum\limits_{k=1}^{n}k=\binom{n+1}{2}=\frac{n(n+1)}{2}.$$

The sum of the first $n$ triangular numbers can be expressed as

$$\sum\limits_{k=1}^{n}\frac{k(k+1)}{2}=\frac{1}{2}\sum_{k=1}^{n}{k^2}+\frac{1}{2}\sum\limits_{k=1}^{n}{k}.$$

The sum of the first $n$ triangular numbers was found previously using the hockey stick identity:

$$\sum\limits_{k=1}^{n}\frac{k(k+1)}{2}=\frac{n(n+1)(n+2)}{6}.$$

Substituting these identities, the identity for the sum of squares of the first $n$ positive integers can be developed:

$$\begin{aligned} \frac{n(n+1)(n+2)}{6}&=\frac{1}{2}\sum_{k=1}^{n}{k^2}+\frac{1}{2}\left(\frac{n(n+1)}{2}\right)\\\\ \frac{1}{2}\sum_{k=1}^{n}{k^2}&=\frac{n(n+1)(n+2)}{6}-\frac{n(n+1)}{4}\\\\ \sum_{k=1}^{n}{k^2}&=\frac{n(n+1)(2n+1)}{6}. \end{aligned}$$

This can also be written in terms of the binomial coefficient:

$$\sum\limits_{k=1}^{n}{k^2}=2\binom{n+2}{3}-\binom{n+1}{2}.\ _\square$$

This method can be continued indefinitely to develop an identity for the sum of any power of natural numbers.

The sum of the cubes of the first $n$ natural numbers is

$$\sum\limits_{k=1}^{n}{k^3}=\frac{n^2(n+1)^2}{4}=6\binom{n+3}{4}-6\binom{n+2}{3}+\binom{n+1}{2}.\ _\square$$

Consider the previous identity for the sum of squares of positive integers:

$$\sum\limits_{k=1}^{n}{k^2}=\frac{n(n+1)(2n+1)}{6}=2\binom{n+2}{3}-\binom{n+1}{2}.$$

Now consider the sum of the sum of squares of positive integers:

$$\begin{aligned} \sum\limits_{k=1}^{n}\sum\limits_{j=1}^{k}{k^2} &= \sum\limits_{k=1}^{n}\frac{k(k+1)(2k+1)}{6} \\ \\ &= \frac{1}{3}\sum\limits_{k=1}^{n}{k^3}+\frac{1}{2}\sum\limits_{k=1}^{n}{k^2}+\frac{1}{6}\sum\limits_{k=1}^{n}{k}. \end{aligned}$$

This sum can be alternatively computed using binomial coefficients and the hockey stick identity:

$$\begin{aligned} \sum\limits_{k=1}^{n}\sum\limits_{j=1}^{k}{k^2} &=\sum\limits_{k=1}^{n}\left[2\binom{k+2}{3}-\binom{k+1}{2}\right] \\ \\ &= 2\binom{n+3}{4}-\binom{n+2}{3} \\ \\ &= \frac{n(n+1)(n+2)(n+3)}{12}-\frac{n(n+1)(n+2)}{6} \\ \\ &= \frac{n(n+1)^2(n+2)}{12}. \end{aligned}$$

Substituting these identities gives

$$\begin{aligned} \frac{n(n+1)^2(n+2)}{12} &=\frac{1}{3}\sum\limits_{k=1}^{n}{k^3}+\frac{n(n+1)(2n+1)}{12}+\frac{n(n+1)}{12}\\\\ &=\frac{1}{3}\sum\limits_{k=1}^{n}{k^3}+\frac{2n(n+1)^2}{12}\\\\ \sum\limits_{k=1}^{n}{k^3}&=\frac{n^2(n+1)^2}{4}. \end{aligned}$$

This can also be expressed with binomial coefficients:

$$\sum\limits_{k=1}^{n}{k^3}=6\binom{n+3}{4}-6\binom{n+2}{3}+\binom{n+1}{2}.\ _\square$$

Inductive Proof of Hockey Stick Identity:

Base Case: $r=n$

We have

$$\begin{aligned} \sum_{k=n}^{n}\binom{k}{n} = \binom{n}{n}&=1\\\\ \binom{n+1}{n+1}&=1. \end{aligned}$$

Inductive Step:

Suppose that for whole numbers $n$ and $r \ (n \ge r),$

$$\sum_{k=r}^{n}\binom{k}{r} = \binom{n+1}{r+1}.$$

Then,

$$\begin{aligned} \sum_{k=r}^{n+1}\binom{k}{r} &= \binom{n+1}{r+1}+\binom{n+1}{r} \\ \\ &= \frac{(n+1)!}{(n-r)!(r+1)!}+\frac{(n+1)!}{(n-r+1)!r!} \\ \\ &= \frac{(n-r+1)(n+1)!}{(n-r+1)!(r+1)!}+\frac{(r+1)(n+1)!}{(n-r+1)!(r+1)!} \\ \\ &= \frac{(n+2)!}{(n-r+1)!(r+1)!} \\ \\ &= \binom{n+2}{r+1}.\ _\square \end{aligned}$$

Combinatorial Proof using Identical Objects into Distinct Bins

Imagine that there are $m$ identical objects to be distributed into $q$ distinct bins such that some bins can be left empty. Using the stars and bars approach outlined on the linked wiki page above, this can be done in $\displaystyle\binom{m+q-1}{q-1}$ ways.

Now consider a slightly different approach to compute this same result. Distribute $j$ objects among the first $q-1$ bins, and then distribute the remaining $m-j$ objects into the last bin. This can be done in $\displaystyle\binom{j+q-2}{q-2}$ ways for each value of $j.$ Count all of the distributions among all possible values of $j$ up to $m$:

$$\sum\limits_{j=0}^{m}\binom{j+q-2}{q-2}.$$

These two methods for counting the distributions of $m$ identical objects into $q$ bins are equivalent, so the expressions which give the results are equal:

$$\sum\limits_{j=0}^{m}\binom{j+q-2}{q-2}=\binom{m+q-1}{q-1}.$$

Let $k=j+q-2,$ let $r=q-2,$ and let $n=m+q-2.$ Substituting these variables in the identity above gives the hockey stick identity:

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