### Stacking cannonballs

James Tanton posed a wordless puzzle about stacking cannonballs. In this post, I will explain how I solved this puzzle, but I will ask you to visit the link and think about the puzzle on your own before you read further.

Since the puzzle has no words, it requires a bit of interpretation. A stack consists of one or more rows, and each ball that is not in the bottom row is supported by two balls in the row beneath. It is further required that there be no gaps in the rows. For example, the stack on the left is admissible, but the stack on the right is not.

The challenge is to find the number of ways to stack the cannonballs if there are n balls in the bottom row. As a first step, we make a table of the number of possibilities for small values of n, and we look for patterns.

 n a(n) 1 1 2 2 3 5 4 13 5 34

We recognize these numbers as the odd-index terms of the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … , and we conjecture that this continues for all n.  According to the OEIS, the odd-index terms of the Fibonacci sequence satisfy the following recurrence:

$a(n) = 3 a(n-1) - a(n-2).$

If we can prove that the cannonball sequence obeys the same recurrence, then we may conclude that the two sequences are identical.

Suppose that we have a stack with n-1 cannonballs on the bottom row. We wish to change it into another stack with n cannonballs on the bottom row.

One way to do this is to place another cannonball on the left side, as follows:

We can also place a cannonball on the right.

Finally, we can add a whole new row to the bottom of the stack, as follows:

So each stack with n-1 cannonballs on the bottom row gives birth to three different stacks with n cannonballs on the bottom row. But we have over-counted! If there are uncovered cannonballs at both ends of the bottom row, then the stack could have been formed by adding a new cannonball to either the left or the right side.

Now, the combinations which were counted twice correspond to stacks with n-2 cannonballs on the bottom row. (Simply remove the red balls from the diagram.) Subtracting the over-counts gives the equation $a(n) = 3 a(n-1) - a(n-2)$.