# Solution

A pyramid of balls consisting of five "layers" is shown below. Find a formula for the number of balls needed to make a pyramid of $n$ layers and prove your result.

Suppose we let $f(n)$ denote the number of balls in a pyramid of $n$ layers. Looking at a few small cases, we find:

$$\begin{array}{rcl} f(1) &=& 1\\ f(2) &=& 4\\ f(3) &=& 10\\ f(4) &=& 20\\ f(5) &=& 35\\ f(6) &=& 56 \end{array}$$

We might guess $f(n)$ is cubic, and thus of the form $f(n) = an^3 + bn^2 + cn + d$. Under this assumption, we can use the above values to set up a system of equations to solve for $a$, $b$, $c$, and $d$:

$$\begin{array}{rcl} 1 &=& a + b + c + d\\ 4 &=& 8a + 4b + 2c + d\\ 10 &=& 27a + 9b + 3c + d\\ 20 &=& 64a + 16b + 4c + d \end{array}$$

Solving, we find $a=1/6, \quad b=1/2, \quad c=1/3, \quad \textrm{ and } d=0$. This suggests that

$$\begin{array}{rcl} f(n) &=& \frac{n^3}{6} + \frac{n^2}{2} + \frac{n}{3}\\\\ &=& \frac{n^3 + 3n^2 + 2n}{6} \end{array}$$

Of course, this is still just a guess at this point. We might check $f(5)$ and $f(6)$ to see if we are on the right track...

$$\begin{array}{rcl} f(5) = 35 &\textrm{ and }& \frac{5^3 + 3 \cdot 5^2 + 2 \cdot 5}{6} = \frac{125 + 75 + 10}{6} = \frac{210}{6} = 35\\\\ f(6) = 56 &\textrm{ and }& \frac{6^3 + 3 \cdot 6^2 + 2 \cdot 6}{6} = 6^2 + 3 \cdot 6 + 2 = 36 + 18 + 2 = 56 \end{array}$$

Since these check out, we are much more confident that this is the formula we seek, but it remains to prove it...

We proceed by induction...

The table above establishes the basis step, so all that remains is the inductive step.

We need to show that if $f(k) = (k^3 + 3k^2 + 2k) / 6$ balls, then

$$f(k+1) = \frac{(k+1)^3 + 3(k+1)^2 +2(k+1)}{6}$$

To show this, first note that a pyramid of $k+1$ layers (with $f(k+1)$ balls) can be split into two pieces -- one consisting of the top $k$ layers, and the other consisting of the bottom layer alone. The first piece, by the inductive hypothesis, contains $f(k) = (k^3 + 3k^2 + 2k) / 6$ balls. The second piece (i.e., the bottom layer) is a triangular arrangement with $1 + 2 + 3 + \cdots + (k+1)$ balls.

Further, we know that

$$1 + 2 + 3 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}$$

Thus,

$$\begin{array}{rcl} f(k+1) &=& f(k) + \left[ 1+2+3+\cdots+(k+1) \right]\\\\ &=& \frac{k^3 + 3k^2 + 2k}{6} + \frac{(k+1)(k+2)}{2}\\\\ &=& \frac{k^3+3k^2+2k+3k^2+9k+6}{6}\\\\ &=& \frac{(k^3+3k^2+3k+1)+(3k^2+6k+3)+(2k+2)}{6}\\\\ &=& \frac{(k^3+3k^2+3k+1)+3(k^2+2k+1)+2(k+1)}{6}\\\\ &=& \frac{(k+1)^3 + 3(k+1)^2 + 2(k+1)}{6} \end{array}$$

This completes the inductive step, so by the principle of mathematical induction, a pyramid of $n$ layers has $f(n)$ balls where

$$f(n) = \frac{n^3 + 3n^2 + 2n}{6}$$ QED.