Simplifying a sum of consecutive cubes

May 20, 2011

If you were asked to find the sum of the first four cubes, you would easily be able to do so:

1^3 + 2^3 + 3^3 + 4^3 = 100

But here you may notice something interesting:

1^3 + 2^3 + 3^3 + 4^3 = (1+2+3+4)^2

It turns out that this holds for the sum of the first n cubes for any n — an identity. This identity can be written also as:

\displaystyle \sum_{i=1}^n i^3 = \left( \displaystyle \sum_{i=1}^n i \right)^2

A second way of expressing the same identity simplifies the right side and expresses it as a combination:

\displaystyle \sum_{i=1}^n i^3 = \binom{n+1}{2}^2

A proof by bijection

This identity can be proven combinatorially by noticing that \binom{n+1}{2} is the number of ways to choose 2 elements with repetition from the set {1..n} — the following is a proof by Benjamin and Orrison.

In this proof, we prove the third form of the identity

\displaystyle \sum_{i=1}^n i^3 = \binom{n+1}{2}^2

by constructing one set of size \displaystyle \sum_{i=1}^n i^3 and constructing another set of size \binom{n+1}{2}^2, then constructing a bijection between the two sets.

Let S be the set of ordered 4-pairs (a,b,c,d) such that 1 \leq a,b,c \leq d \leq n — that is, the fourth integer of the pair is greater or equal to each of the other three. If we fix d, the number of possibilities for the variables a,b,c is d^3. As d ranges from 1 to n, the total number of elements in S is equal to \displaystyle \sum_{i=1}^n i^3.

Also, since \binom{n+1}{2} is the number of ways to choose 2 elements with repetition from the set {1..n}, there are \binom{n+1}{2} pairs of integers (h,i) satisfying 1 \leq h \leq i \leq n. So let T be the set of pairs of such pairs ((h,i),(j,k)) where 1 \leq h \leq i \leq n and 1 \leq j \leq k \leq n. The number of elements in T is then \binom{n+1}{2}^2.

We further partition the sets as follows: let S_1 be the subset of S where a \leq b and let S_2 be the subset of S where a > b. Similarly, let T_1 be the subset of T where i \leq k and let T_2 be the subset of T where i > k. We can construct a bijection between S and T by constructing two bijections:

S_1 \leftrightarrow T_1

S_2 \leftrightarrow T_2

The following is trivially a bijection from S_1 to T_1 — the case where a \leq b:

(a,b,c,d) \rightarrow ((a,b),(c,d))

The equivalent bijection from S_2 to T_2 — the case where a > b:

(a,b,c,d) \rightarrow ((c,d),(b,a-1))

We can confirm that the two operations we defined are indeed bijections. This proves the identity.


Stepping Stones: solution with Young tableaux

September 3, 2010

About a year ago or so, I created a math problem and submitted it to CsTutoringCenter. Titled Stepping Stones, my problem statement went like this:

In a certain river, there are a bunch of stepping stones arranged from one side to the other. A very athletic person can cross the river by jumping on these stepping stones, one at a time.

A stepping stone is big enough for only one person, and the gap between two stepping stones is small enough that it is possible to jump between two adjacent stepping stones.

You are an army commander trying to get a group of soldiers across this river (using these stepping stones). Initially your n soldiers are placed on the first n stepping stones. Your task is to get all of them onto the last n stepping stones.

For example, here are the five possible ways to get a group of two soldiers across a river with five stepping stones:

1) ##---  #-#--  -##--  -#-#-  --##-  --#-#  ---##
2) ##---  #-#--  -##--  -#-#-  -#--#  --#-#  ---##
3) ##---  #-#--  #--#-  -#-#-  --##-  --#-#  ---##
4) ##---  #-#--  #--#-  -#-#-  -#--#  --#-#  ---##
5) ##---  #-#--  #--#-  #---#  -#--#  --#-#  ---##

Let C(k,n) be the number of ways of which n soldiers can cross a river with k stepping stones. In the example, C(5,2) = 5.

Find C(50,12) mod 987654321.

Of course, small values of C(k,n) may be bruteforced by a computer. But C(50,12) is well out of reach of brute force, and substantial mathematics is needed. Or for the lazy, it is possible to find small values by brute force, then look the sequence up on OEIS to find the formula.

Bijection to a matrix representation

We find that any instance of the problem can be represented, or bijected to a special matrix, one where each row and column is increasing.

Let us number the soldiers in the following fashion. Let the rightmost soldier, that is, the soldier first to move, be labelled 1. The soldier behind him is labelled 2, and so on, until the last soldier to move is labelled n. Since the order of soldiers cannot change, each soldier moves exactly k-n times.

Consider a very simple case, with 4 stones and 2 soldiers. One possible way is the first soldier moving twice, followed by the second moving twice.

This move sequence can be represented by [1,1,2,2]. The other sequence, and the only other sequence is [1,2,1,2].

Firstly a sequence like [1,1,1,2] is invalid because in a valid sequence, each soldier has to move the same number of times. Another invalid case is something like [2,1,1,2], since obviously 2 cannot move the first turn. But how can you tell whether [1,2,1,1,2,1,3,2,3,3,2,3] is valid or not?

It isn’t very easy to tell in sequence form. Instead we represent the sequence as a matrix form.

Let’s try some examples first, The sequence [1,1,2,2] in matrix form is:

\begin{array}{cc} 1&2 \\ 3&4 \end{array}

The other sequence, [1,2,1,2], is:

\begin{array}{cc} 1&3 \\ 2&4 \end{array}

Try a more complex example, [1,2,1,1,2,1,3,2,3,3,2,3]:

\begin{array}{cccc} 1&3&4&6 \\ 2&5&8&11 \\ 7&9&10&12 \end{array}

To create the matrix, first have a counter and initialize it to 1; when the first soldier moves, place the counter in the first cell that’s unfilled in the first row, and increment the counter. Now if the second soldier moves, we place the counter in the second row (first unfilled cell), and increment it again, and so on. By the time we’re through all of the soldier moves, the matrix should be nice and rectangular.

Perhaps a different explanation is more intuitive. If A_{3,2} = 7 (where A is the matrix, A_{3,2} means row 3, column 2), that means on move 7, soldier number 3 makes his move number 2.

From this interpretation, several important facts surface. The rows must be increasing, obviously, since if the row is not increasing, say 7 comes before 5, move 7 happened before move 5, which can’t be!

Less obviously, the column has to be increasing. Suppose that in some matrix, A_{2,7}=20, and the cell directly underneath, A_{3,7} = 19. In that case soldier 3 made his move 7 before soldier 2 made his move 7. This results in soldier 3 ahead of soldier 2 (or at least on the same stone)!

So with k stones and n soldiers, the matrix should have n rows and k-n columns. The m \times n cells contain the numbers 1 \ldots mn, while each row and each column is increasing. Our job is to enumerate these matrices, since such a matrix forms a 1-to-1 correspondence to a valid move sequence.

Enumerating matrices with the hook length formula

A Young tableau is an interesting combinatorial object, based on the Ferrers diagram. From a Ferrers diagram of size n, a Young tableau is one where every number from 1 \ldots n is filled in it and all rows and all columns are increasing:

From any cell of a Young tableau, a hook is formed by extending all the way down, and all the way to the right:

The hook length of a cell is the length of its hook (including itself). In the above picture, the hook length is 5. Each cell in the tableau has a hook and a hook length.

The number of valid Young tableaux with a given shape \lambda and with n cells is given by the hook length formula:

N = \frac{n!}{\prod_{x \in \lambda} \mathrm{hook}_x}

A special case of the hook length formula can be used to enumerate rectangular Young tableaux. For instance, we have a 3*4 Young tableau. If we fill each cell with its hook length we get:

The count would then be

\frac{12!}{6 \cdot 5 \cdot 4 \cdot 5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}

Or alternatively,

\frac{12!}{\frac{6!}{3!} \cdot \frac{5!}{2!} \cdot \frac{4!}{1!} \cdot \frac{3!}{0!}}

Simplifying:

\frac{12! \cdot 0! \cdot 1! \cdot 2! \cdot 3!}{3! \cdot 4! \cdot 5! \cdot 6!}

This can be generalized to a formula. If we have x rows and y columns:

\frac{(xy)! \prod_{i=1}^{y-1}i!}{\prod_{j=x}^{x+y-1} j!}

For C(k,n), we have n rows and k-n columns, thus by substitution we arrive at our formula:

C(k,n) = \frac{[n(k-n)]! \prod_{i=0}^{k-n-1}i!}{\prod_{j=n}^{k-1}j!}

This can be used to compute C(50,12), trivial to implement in Haskell or any other language.


Follow

Get every new post delivered to your Inbox.

Join 61 other followers