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

-
What is the question? – Ross Millikan Mar 2 '11 at 1:48
How to derive the formula (or at least how to prove that it works). – Yuval Filmus Mar 2 '11 at 2:18
You get the spiffy formula by using the general one for Faulhaber's with $p=2$, with the values of the Bernoulli numbers. See my answer. – Arturo Magidin Mar 2 '11 at 4:50
here is an interesting way of doing it. try using the hockey stick formation in pascals triangle on the 3rd diagonal. artofproblemsolving.com/Wiki/index.php/Combinatorial_identity – John Joy Aug 19 '14 at 16:34

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 answer provides a lot of things for me to research. I'm trying to understand Bernoulli's numbers and Faulhaber's formula, and binomial coefficients (first encounter with those..). While your and Paul's answers I think are good, I'd feel wrong marking one of them as The Answer until I actually understand it, even though it has more to do with my lack of knowledge. – djeikyb Mar 3 '11 at 10:40

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.

-
Hmm. I think this answers my question, but it's taking me a while to understand the p(n) and p(k+1) stuff. Although I've some appreciation now for why it's considered outside the class's scope. – djeikyb Mar 3 '11 at 10:32
Hmm, perhaps I stated it too formally. The basic principle is this. You can easily see that your formula holds for $n=1$. What I proved above is that, if we know it holds for a specific value of $n$, it also holds for the next value. So since it holds for $1$, it holds for $2$... and since it holds for $2$, it holds for $3$... and so on, until it "proves itself" for every value of $n$. (This is intuitive, but be warned that it isn't very formal.) – Paul VanKoughnett Mar 3 '11 at 18:04

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

-
Intriguing. I don't expect you to dispense a course's worth of info, but what is the thing that looks like a minus sign next to the k, underneath the elevated two (and one, and three)? – djeikyb Mar 3 '11 at 10:49
@djeikyb: The exponent is underlined, to show that it's not an ordinary power like $17^4 = 17 \cdot 17 \cdot 17 \cdot 17$, but instead a "falling power" like $17^{\underline{4}} = 17 \cdot 16 \cdot 15 \cdot 14$. Overlined exponents denote "rising powers" like $17^{\overline{4}} = 17 \cdot 18 \cdot 19 \cdot 20$. There are also other notations in use for this. See for example this Wikipedia article: en.wikipedia.org/wiki/Pochhammer_symbol. – Hans Lundmark Mar 3 '11 at 15:37

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*} f(0)=0\quad&\Longrightarrow\quad u=0\\ f(1)=1\quad&\Longrightarrow\quad t+u=1\quad\Longrightarrow\quad t=1\\ f(2)=5\quad&\Longrightarrow\quad 2s+2t+u=5\quad\Longrightarrow\quad s=\frac32\\ f(3)=14\quad&\Longrightarrow\quad 6r+6s+3t+u=14\quad\Longrightarrow\quad r=\frac13\\ \end{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$.

I hope that this was at a level accessible to you.

-