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.
Counting Problems
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{red}{210}\) ways to select 3 balls from the same row. \(_\square\)
Mabel is playing a carnival game in which she throws balls into a triangular array of cups.
She will throw three balls, and she will win the game if the three balls are in a straight line (not necessarily adjacent) and in different cups.
Disregarding the order the balls go into the cups, how many ways can she win the game?
In how many different ways can 4 squares be chosen on a chessboard such that the 4 squares lie in a diagonal line?
\(\)
Image Credit: Wikipedia Commons
Triangular Numbers
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 oranges are arranged such that there is 1 top orange; the second top layer has 2 more oranges than the top; the third has 3 more oranges than the second, and so on. Forming a tetrahedron of oranges, these "tetrahedral" numbers of oranges run as a series, as shown above.
What is the value of the \(100^{\text{th}}\) term of this series?
I drew rectangular grids with one more row than their column. The number of dots in the first four grids are 2, 6, 12, and 20, as shown in the diagram below:
What is the total number of dots used in the first eleven grids?
Sums of Powers of Natural Numbers
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{align} \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{align}\]
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{align} \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{align}\]
This sum can be alternatively computed using binomial coefficients and the hockey stick identity:
\[\begin{align} \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{align}\]
Substituting these identities gives
\[\begin{align} \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{align}\]
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\]
For the past decade, the king of Mathlandia has forced his subjects to build a pyramid in his honor. The king decreed the pyramid to be constructed with cubic stone slabs. The king also decreed the pyramid to be built in 100 square levels, with each subsequent level 2 units less on a side than the previous level. The top level was to be constructed with a single cube. (See the picture for an example of a pyramid 3 levels high constructed in the same way).
Moments after the final cube was placed, the king changed his mind. He ordered the pyramid to be taken down, and in its place, a cubic monolith was to be built. He ordered the monolith to be built as large as possible with the same stone slabs the pyramid was made of.
The king would tolerate no waste, so he ordered one of his subjects to be sacrificed for each leftover slab of stone.
How many of the king's subjects will be sacrificed?
Proofs
Inductive Proof of Hockey Stick Identity:
Base Case: \(r=n\)
We have
\[\begin{align} \sum_{k=n}^{n}\binom{k}{n} = \binom{n}{n}&=1\\\\ \binom{n+1}{n+1}&=1. \end{align}\]
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{align} \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{align}\]
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\]