Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In example to get formula for $1^2+2^2+3^2+...+n^2$ they express $f(n)$ as: $$f(n)=an^3+bn^2+cn+d$$ also known that $f(0)=0$, $f(1)=1$, $f(2)=5$ and $f(3)=14$

Then this values are inserted into function, we get system of equations solve them and get a,b,c,d coefficients and we get that $$f(n)=\frac{n}{6}(2n+1)(n+1)$$

Then it's proven with mathematical induction that it's true for any n.

And question is, why they take 4 coefficients at the beginning, why not $f(n)=an^2+bn+c$ or even more? How they know that 4 will be enough to get correct formula?

share|improve this question
1  
Using integral estimates, for instance, you can easily see that $f(n)$ should grow asymptotically like $n^3/3$. –  Rasmus Aug 23 '11 at 9:47
    
@Rasmus I know that $x^2 dx=\frac{x^3}{3}$ but it doesn't say anything to me, only that you can calculate plot of area –  Templar Aug 23 '11 at 10:01
2  
$(n+1)^3 - n^3 = 3n^2+3n+1$ - so it is clear that the $n^2$ terms can be added (with some lower-order terms attached) by adding the differences of cubes, giving a leading term in $n^3$. The factor 1/3 attached to the $n^3$ term is also obvious from this observation. You can use induction to show that the lower-order terms can be dealt with using lower order expressions (so assume that the natural numbers and units have already been summed using expressions of degree 2 and 1 respectively). –  Mark Bennet Aug 23 '11 at 10:03
4  
Does any of these suit you? math.stackexchange.com/questions/48080/… –  t.b. Aug 23 '11 at 10:05
1  
@Templar: A polynomial in one variable is a sum of multiples of powers of the variable; e.g. your $f(n)$ is a (cubic) polynomial in $n$. –  joriki Aug 23 '11 at 10:06

4 Answers 4

up vote 5 down vote accepted

There are several ways to see this:

  • As Rasmus pointed one out in a comment, you can estimate the sum by an integral.
  • Imagine the numbers being added as cross sections of a quadratic pyramid. Its volume is cubic in its linear dimensions.
  • Apply the difference operator $\Delta g(n)=g(n+1)-g(n)$ to $f$ repeatedly. Then apply it to a polynomial and compare the results.

[Edit in response to the comment:]

An integral can be thought of as a limit of a sum. If you sum over $k^2$, you can look at this as adding up the areas of rectangles with width $1$ and height $k^2$, where each rectangle extends from $k-1$ to $k$ in the $x$ direction. (If that's not clear from the words, try drawing it.) Now if you connect the points $(k,k^2)$ by the continuous graph of the function $f(x)=x^2$, the area under that graph is an approximation of the area of the rectangles (and vice versa). So we have

$$1^2+\dotso+n^2\approx\int_0^nk^2\mathrm dk=\frac13n^3\;.$$

share|improve this answer
    
maybe you could say more about integral way, why you need to integrate n^2 –  Templar Aug 23 '11 at 12:36

It comes from that fact that the difference operator $$\Delta f(n) = f(n+1)-f(n)$$ acting on polynomials $f(x)$ of degree $d$ will result in polynomials in degree $d-1$ (check this!) - the difference between $f(n)=1^2+2^2+\cdots+n^2$ and $f(n+1)=1^2+\cdots+(n+1)^2$ is simply $(n+1)^2$, which is a quadratic in $n$, hence we should expect $f$ to be cubic.


More rigorously, we can reason by induction, though this is might be too advanced for the OP to follow along. Suppose we have the antidifference $\Delta^{-1}n^p$ for exponents $p=0,1,\dots,k-1$ (there will be arbitrary additive constants, but these cancel when we put definite bounds on the implicit sum so we'll ignore them). Then note that $\Delta n^{k+1}$ can be expanded (via the Binomial theorem) into powers of $n$ from $l=0$ to $k$. If we subtract out all of the powers from $l=0$ to $l=k-1$ and put them side by side with $\Delta n^{k+1}$, then we have all terms we know the antidifference of on one side of an equation and $n^k$ on the other. Apply the antidifference and we now have a formula for $\Delta^{-1} n^k$.

share|improve this answer
    
I don't know what's polynoms and those Sigmas (I just know that it's sum sign) –  Templar Aug 23 '11 at 10:04

As the comments indicate, there are many possibilities. One first assumes that it's a polynomial (perhaps for no good reason, you know?). One might consider that the polynomial grows asymptotically like a cubic from the integral.

Or one might repeatedly apply the difference operator. For example, the first few values are 0, 1, 5, 14, 30, 55... Then the first set of differences is 1, 4, 9, 16, 25... The second set of differences is 3, 5, 7, 9... The third set of differences is 2, 2, 2, 2, 2...

Thus we suspect a cubic polynomial will do.

share|improve this answer

It is a consequence of the following algebraic identity

$$1+2^{2}+3^{2}+\ldots +n^{2}=\frac{1}{3}\left( n^{3}+3n^{2}+3n+1\right) - \frac{1}{3}n-\frac{1}{2}(n^2+n)-\frac{1}{3}.$$ $$\tag{1}$$

The RHS is a cubic function of $n$: $\frac{1}{3}n^{3}+\frac{1}{2}n^{2}+\frac{1}{6}n$.

Proof. From the algebraic identity

$$\left( 1+k\right) ^{3}=1+3k+3k^{2}+k^{3}$$

we get the following $n$ identities:

$$\begin{eqnarray*} \left( 1+1\right) ^{3} &=&1+3+3+1 \\ \left( 1+2\right) ^{3} &=&1+3\cdot 2+3\cdot 2^{2}+2^{3} \\ \left( 1+3\right) ^{3} &=&1+3\cdot 3+3\cdot 3^{2}+3^{3} \\ &&\ldots \\ \left( 1+n\right) ^{3} &=&1+3n+3n^{2}+n^{3}. \end{eqnarray*}$$

Now if we sum these equalities and cancel the common terms, $\left( 1+1\right) ^{3}$ on the LHS of the first and $2^{3}$ on the RHS of the second, $\left( 1+2\right) ^{3}$ on the LHS of the second and $3^{3}$ on the RHS of the third, etc., and $(1+n-1)^3$ on the LHS of the second last and $n^3$ on the RHS of the last, we get:

$$\left( 1+n\right) ^{3}=n+3(1+2+3+\ldots +n)+3(1+2^{2}+3^{2}+\ldots +n^{2})+1,\tag{2}$$

and $(1)$ follows from $(2)$ and the sum formula for the arithmetic progression $$1+2+3+\ldots +n=\frac{\left( n+1\right) n}{2}.$$

(Adapted from Proof 1 in this answer to the question Proof that $\sum_{k=1}^n k^2$ = $\frac{n(n+1)(2n+1)}{6}$? ; see the above Theo Buehler's comment.)


Note: This is a particular case of the sum $1+2^{p}+3^{p}+\ldots +n^{p}$, which is a polynomial of degree $p+1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.