# 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 2×2, then 3×3, 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)

#### Solutions Collecting From Web of "How do I come up with a function to count a pyramid of apples?"

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$).

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.

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.)

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}

Ok so let me so something similar to Carsten.

Consider expanding $(k+1)^3 – k^3 = 3k^2 + 3k + 1$.

Now if we were to sum both sides over $k=1,2,…,n$ then we would find that on the left most of the terms cancel, e.g. $(5^3 – 4^3) + (4^3 – 3^3) + … + (2^3 – 1^3) = 5^3 – 1^3$. On the right you have sums you already have a formula for along with the one you are after.

So:

$(n+1)^3 – 1 = 3\sum_{k=1}^{n} k^2 + 3\sum_{k=1}^{n} k + \sum_{k=1}^{n} 1$

i.e. $\sum_{k=1}^{n} k^2 = \frac{1}{3}((n+1)^3 – 3(\sum_{k=1}^{n} k) – n – 1) = \frac{1}{3}((n+1)^3 – 3\frac{(n)(n+1)}{2} – n-1) = … = \frac{n(n+1)(2n+1)}{6}$

We can also solve this problem by finding a recurrence formula. First assume your solution is going to be a polynomial in the following form $$An^4 +Bn^3+Cn^2+Dn+En^0$$ where $A,B,C,D,E$ are the coefficients for which we are solving. We will solve it using linear algebra by setting up the matrix below.

\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 \\[0.3em]
16 & 8 & 4&2&1&5 \\[0.3em]
81&27&9&3&1&14 \\[0.3em]
256&64&16&4&1&30 \\[0.3em]
625&125&25&5&1&55
\end{bmatrix}

Label each row as $a_1, a_2, a_3, a_4,a_5$ where each subscript corresponds to $n$ in the polynomial and each column, except for column six, corresponds to the exponents in the polynomial. So you can see that the first column is $1^4, 2^4, 3^4, 4^4, 5^4$. The second column is $1^3, 2^3, 3^3, 4^3, 5^3$, The third column is $1^2, 2^2, 3^2, 4^2, 5^2$. The fourth column is $1^1, 2^1, 3^1, 4^1, 5^1$. The fifth column is $1^0, 2^0, 3^0, 4^0, 5^0$. Column six represents the cumulative amounts in each row through five rows of the square pyramid. Solving the matrix will result in the following matrix

\begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 \\[0.3em]
0 & 1 & 0&0&0&\frac{1}{3} \\[0.3em]
0&0&1&0&0&\frac{1}{2} \\[0.3em]
0&0&0&1&0&\frac{1}{6} \\[0.3em]
0&0&0&0&1&0
\end{bmatrix}

Based on the solution to the matrix our final polynomial is $$a(n) = 0n^4 + \frac{1}{3}n^3 + \frac{1}{2}n^2 +\frac{1}{6}n +0n^0$$ where $A=0, B =\frac{1}{3}, C=\frac{1}{2}, D=\frac{1}{6}, E=0$

It is evident from the result that we did not need to start with the polynomial we started with an a $5$ x $6$ matrix. We could have started with $An^3 +Bn^3 +Cn^2 +Dn^1+ En^0$ and a $4$ x $5$ matrix. The final result let us know that when the coefficient $A$ turned out to be $0$.

If you wanted the formula for the tetrahedral pyramid of apples just replace the last column in the original matrix with $1, 4, 10, 20, 35$, the cumulative number of apples for row one through row five and solve.

You have gotten lots of good answers here. I’d say that you’d profit very much from trying to understand Hans’ answer, and maybe even check out the book he mentions from the library to see if there are things in it that you can understand at your level. Let me just add a very brief summary of Paul’s answer.

First convince yourself that claiming that
$$\sum_{k=1}^n k^2=f(n)\quad\text{for all n\in\mathbb N}$$
is actually the same as claiming
$$f(0)=0\qquad\text{and}\qquad f(n+1)-f(n)=(n+1)^2\quad\text{for all n\in\mathbb N.}$$
I hope that this makes sense after you have thought about it for a while. Now as soon as it does, you do at least know how to check the formula given by your book: Just compute $f(0)$ and $f(n+1)-f(n)$.

Now how do you come up with such a formula? Well, if you already know or suspect that $f(n)$ is a polynomial of degree three (which is not unreasonable, since it is related to the volume of the pyramid, you can set
$$f(x)=ax^3+bx^2+cx+d$$
and then figure out what $a,b,c,d$ have to be for $f(0)=0$ and $f(n+1)-f(n)=(n+1)^2$ to hold. If you know systems of linear equations then it should not be to difficult. Otherwise, here is another approach. Instead set
$$f(x)=rx(x-1)(x-2)+sx(x-1)+tx+u.$$
(Compare with Hans’ answer.)
We know that we must have $f(0)=1$, $f(1)=1$, $f(2)=5$, $f(3)=14$. Now we get
\begin{align*}
(I hope my calculations are correct.) Of course, if you do want to take on faith that a polynomial of degree $3$ works, you will still have to verify that $f(n+1)-f(n)=(n+1)^2$.
$$\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,$$
$$\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,$$
$$\sum_{k=0}^nk^2=2\binom{n+1}3+\binom{n+1}2=\frac{n(n+1)(2n+1)}6.$$