How do I come up with a function to count a pyramid of apples?

My algebra book has a quick practical example at the beginning of the chapter on polynomials and their functions. Unfortunately it just says "this is why polynomial functions are important" and moves on. I'd like to know how to come up with the function (the teacher considers this out of scope). Even suggesting google search terms to find out more information on this sort of thing would be helpful.

The example

Consider a stack of apples, in a pyramid shape. It starts with one apple at the top. The next layer is 2x2, then 3x3, and so on. How many apples are there, given x number of layers?

The polynomial function

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

What I do and don't understand

Thanks to @DJC, I now know this is a standard function to generate Square Pyramidal Numbers, which is part of Faulhaber's formula. Faulhaber's formula appears to be about quickly adding sequential coefficients which all have the same exponent. Very cool. But how does one get from:

$$\sum_{k=1}^{n} k^p$$

to the spiffy function above? If I'm sounding stupid, how do I make the question better?

Fwiw, I'm in intermediate algebra in the USA. The next course would be Trigonometry or Calculus. (to help people place my current knowledge level)

You can prove the formula works using induction. I'm not sure what level you're at mathematically, so don't take this the wrong way if you have heard it... but if you haven't heard it, it's the following fact. If $P(n)$ is some true/false statement based on a natural number $n$, and $P(1)$ is true, and whenever $P(k)$ is true then $P(k+1)$ is also true, then $P(n)$ is true for all natural numbers $n$.

In this example, $P(1)$ is the statement that $1=\frac{1}{3}+\frac{1}{2}+\frac{1}{6}$, obviously true. Now suppose that $P(k)$ is true, that is, that $f(k)$ is known to be $\frac{k^3}{3}+\frac{k^2}{2}+\frac{k}{6}$. Then $f(k+1)$ is just the $k$th plus $(k+1)^2=k^2+2k+1$. This is

$\displaystyle \frac{k^3}{3}+\frac{k^2}{2}+\frac{k}{6}+k^2+2k+1=\frac{2k^3+3k^2+k+6k^2+12k+6}{6}$ $\displaystyle =\frac{2k^3+9k^2+13k+6}{6}=\frac{(2k^3+6k^2+6k+2)+3k^2+6k+3)+(k+1)}{6}$ $\displaystyle =\frac{2(k+1)^3+3(k+1)^2+(k+1)}{6}=\frac{(k+1)^3}{3}+\frac{(k+1)^2}{2}+\frac{(k+1)}{6}.$

How you actually come up with a formula like this in the first place is a different matter. "Watch for patterns" is really what it boils down to, but there are a couple shortcuts. The rule is simple enough that you can guess it's a polynomial. The numbers you're adding to get from one stage to the next are squares, so you can guess that it's a cubic. One way to check this is the "method of common differences." Your sequence is

$\displaystyle 0,1,5,14,30,55,\dotsc$

so the differences between successive terms are

$\displaystyle 1,4,9,16,25,\dotsc$

and the differences between successive terms of that sequence are

$\displaystyle 3,5,7,9,\dotsc$

and finally

$\displaystyle 2,2,2,\dotsc$

The final sequence is constant, the one above that is linear, the one above that is quadratic, and the one above that is cubic. So we have $f(n)=an^3+bn^2+cn+d$. Then by substituting different values for $n$ and solving the system of equations, we can find out what $a,b,c,$ and $d$ are. (It was obvious in this case what the first difference sequence was, but in other cases it may not be so obvious.)

I was going to conclude by noting that the $n$th triangular number is $\frac{(n)(n+1)}{1\cdot 2}$, and the $n$th pyramidal number is $\frac{(n)(n+1)(n+2)}{1\cdot 2\cdot 3}$, and guessing that things worked the same in higher dimensions. But as it turns out, they don't. Take that how you will.

The first layer has $1^2$ elements; the second has $2^2$ elements; the next has $3^2$ elements, and so on.

So this is a matter of finding the formula for $$1^2 + 2^2 + 3^2 + \cdots + n^2$$ in terms of $n$.

For squares, this is a well known formula: $1^2+2^2+\cdots +n^2 = \frac{n(n+1)(2n+1)}{6}$.

Note that $$\frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} = \frac{2n^3 + 3n^2 + n}{6} = \frac{n(2n^2+3n+1)}{6} = \frac{n(2n+1)(n+1)}{6}$$ same formula.

Of course, you might be more interested in how to figure out the formulas in the first place. How does one express $1^k + 2^k + 3^k + \cdots + n^k$?

This is known as Faulhaber's formula. For the general case, $$1^p + 2^p + \cdots + n^p = \frac{1}{p+1}\sum_{j=0}^p(-1)^jB_j\binom{p+1}{j} n^{p+1-j}$$ where $B_m$ is the $m$th Bernoulli number.

For $p=2$, you get the spiffy formula with: \begin{align*} 1^2+\cdots+n^2 &= \frac{1}{3}\left(\binom{3}{0}B_0n^3 - \binom{3}{1}B_1n^2 + \binom{3}{2}B_2n - \binom{3}{3}B_3\right)\\ &= \frac{1}{3}\left(B_0n^3 - 3B_1n^2 + 3B_2n - B_3\right)\\ &= \frac{1}{3}\left(n^3 - 3\left(-\frac{1}{2}\right)n^2 + 3\left(\frac{1}{6}\right)n - 0\right)\\ &= \frac{1}{3}n^3 +\frac{1}{2}n^2 + \frac{1}{6}n\\ &= \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}, \end{align*} using the fact that $B_0 = 1$ $B_1 = -\frac{1}{2}$, $B_2 = \frac{1}{6}$, and $B_3=0$ (in fact, $B_n = 0$ for all odd $n\gt 1$).

This formula is derived in many different ways in the book Concrete Mathematics. For example, one method which hasn't been mentioned yet here is to use "discrete calculus", which easily lets you compute sums of "falling factorial powers" $k^{\underline{m}} = k(k-1)(k-2) \dots (k-m+1)$ almost as when you integrate ordinary powers $x^m$. Upon writing $k^2 = k(k-1)+k = k^{\underline{2}} + k^{\underline{1}}$, your sum becomes $$ \sum_{0 \le k < n+1} (k^{\underline{2}} + k^{\underline{1}}) = \left[ \frac{k^{\underline{3}}}{3} + \frac{k^{\underline{2}}}{2} \right]_{k=0}^{n+1} = \frac{(n+1)n(n-1)}{3} + \frac{(n+1)n}{2} = \frac{(n+1)n(2n+1)}{6}, $$ which is your polynomial $f(n)$. (See the book for explanation of why it this works.)

The binomial coefficient identities $$\sum_{k=0}^n\binom k1=\binom{n+1}2,$$ $$\sum_{k=0}^n\binom k2=\binom{n+1}3,$$ $$\sum_{k=0}^n\binom k3=\binom{n+1}4,$$ etc. are simple and natural. To derive the sum-of-squares formula you asked about, observe that $$\binom{n+1}3=\sum_{k=0}^n\binom k2=\sum_{k=0}^n\frac{k^2-k}2=\frac12\sum_{k=0}^nk^2-\frac12\sum_{k=0}^nk=\frac12\sum_{k=0}^nk^2-\frac12\binom{n+1}2,$$ whence $$\sum_{k=0}^nk^2=2\binom{n+1}3+\binom{n+1}2=\frac{n(n+1)(2n+1)}6.$$

You can prove it works by induction. It works for $x=1$, as $f(x)=1$. So assume it works for $x: f(x) = \frac{x^3}{3} + \frac{x^2}{2} + \frac{x}{6}$ and we want to show it works for $x+1$: $$\begin{align} f(x+1)&=f(x)+(x+1)^2 \\ &=\frac{x^3}{3} + \frac{x^2}{2} + \frac{x}{6} + (x+1)^2 \\ &=\frac{x^3}{3} + \frac{x^2}{2} + \frac{x}{6} +\frac{3x^2+3x+1}{3}+\frac{2x+1}{2}+\frac{1}{6} \\& =\frac{(x+1)^3}{3} + \frac{(x+1)^2}{2} + \frac{x+1}{6}\end{align}$$