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.

Prove that $\sum_{i=1}^{n} i^3 = \left( \frac{n(n+1)}{2} \right)^2$.

We can check this is true for n=0,1,2,3,4. Since the right side is a polynomial of degree 4, and the left side is a sum of monomials whose degree is <= 4, then if both polynomials coincide for five points, they must be the same.

My question: is this proof rigorous? I'm concerned about the left side sum.

share|improve this question
1  
I think that even if you prove this, you will have to use theorems based on the continuity of polynomials. Unless you already have a specific theorem about the points, which I'm not familiar with. You're honestly better off working with the Δ of the sum. Oh, by the way, what you're doing isn't infinite induction. That's something else. You might want to change the topic. –  Greg Ros Nov 12 '12 at 14:32
    
It's not clear what your subject means, btw. Why do you call this "infinite induction?" –  Thomas Andrews Nov 12 '12 at 14:43
    
@GregRos Why does he need continuity? This is a discrete values problem. –  Thomas Andrews Nov 12 '12 at 14:43
2  
I called it infinite induction because it looks like a strange finite induction, I'm proving it for induction basis i=0,1,2,3,4 and then magically it's proved for all n. I welcome a proper name for this kind of proof though. –  Ricbit Nov 12 '12 at 14:52
    
When I was in school, I wasn't familiar with a theorem that talked about the equality of two polynomials based on their points. It can be proven using theorems related to the derivative and continuity of the polynomial. As for a name, it's not induction at all. It's just a proof. –  Greg Ros Nov 12 '12 at 14:53
show 2 more comments

6 Answers

up vote 6 down vote accepted

No, your proof is not rigorous. It is actually wrong. The point is that you don't know a priori that the left-hand-side is a polynomial of degree $4$ on $n$.

As an example of your "reasoning", consider the equality $$ \sum_{i=1}^n i = 2n-1. $$ This is of course false (the actual formula on the right should be $n(n+1)/2$. But, for $n=1$ and $n=2$, both sides agree ($1$ and $3$ respectively), and the right hand side is a polynomial of degree $1$, so two points would suffice to determine it, if we were allowed to reason as you did.

share|improve this answer
    
I fixed the indices, I meant $n$ instead of $i$. –  Ricbit Nov 12 '12 at 15:00
    
Yes, but then you don't know that the left-hand-side is a polynomial on $n$; that's precisely what you are trying to prove. –  Martin Argerami Nov 12 '12 at 15:02
    
So will it be correct if I assume that I know beforehand the answer is a 4-degree polynomial, and I just don't know which 4-degree poly? –  Ricbit Nov 12 '12 at 15:05
1  
Thanks for all the answers, it was nice to see such a diverse set of opinions in one question. –  Ricbit Nov 12 '12 at 18:36
1  
@spernerslemma I agree with your conclusion, but the question as I asked was wrong. I assumed that if RHS has degree X, and the LHS is a sum of monomials with degree <= X, then the result follows. The counterexample presented shows that my assumption is false. –  Ricbit Nov 12 '12 at 22:53
show 7 more comments

Yes this is rigorous because the a basic fact about polynomials is that the discrete integral of a degree $d$ polynomial is a degree $d+1$ polynomial.

share|improve this answer
4  
Note that if discrete calculus is admitted, the sum can be calculated directly and simply. –  Greg Ros Nov 12 '12 at 14:33
add comment

The proof is not rigorous because it skips a lot of the necessary steps. You need to prove that $∑i^{3}$ is a polynomial of degree $4$. Then, you need to prove that if two polynomials of degrees $m$ and $n$ match on $max\{m,n\}+1$ points, then they must be the same polynomial. If you know that a polynomial $P$ has at most a number of roots equal to its degree, this is not hard to prove.

I don't recommend going by this route, however. There is a significantly easier way to prove the equation. Note the following:

$$\left(\frac{(n+1)(n+2)}{2}\right)^{2}-\left(\frac{n(n+1)}{2}\right)^{2}≟n^{3}$$

If you show this (I don't know if it's true; I haven't calculated. It does seem so at a glance.), then you're right. Try to understand yourself why. If this is not true, you're not right. This is the core of a rigorous proof but you'll need to explain why it's rigorous.

share|improve this answer
    
Yup, $\sum_n f(x)=g(n)$ is the same as $g(n+1)-g(n)=f(n)$. –  Ricbit Nov 12 '12 at 15:23
    
Mm, that I know, I meant that specific equation is true at a glance but might not be. –  Greg Ros Nov 12 '12 at 15:28
    
Mathematica says it's actually $(1+n)^3$, so we're off by one. –  Ricbit Nov 12 '12 at 15:31
    
Might be. You can calculate it directly using discrete calculus but I didn't bother :P –  Greg Ros Nov 12 '12 at 15:32
    
It's $(n+1)^3$. That's what allows the induction step. –  Cameron Buie Nov 12 '12 at 15:59
add comment

This can of course be proven quite easily using a standard induction, but if we want to follow the OP's line of thought we may proceed as follows. Note that assuming $\sum_{i=1}^n i^3$ is a degree 4 polynomial (in $n$), then the strategy is actually correct. We just have to check that the right hand side is the right polynomial, and we can do that by checking 5 values of $n$. So, how do we prove that $\sum_{i=1}^n i^3$ is a degree 4 polynomial? The trick is to introduce a new parameter $k$, and ask what the sum of the first $n$ $k$th powers is? By proceeding by induction on $k$ (instead of $n$), we can prove that this is always a degree $k+1$ polynomial. See my answer here for how this works. In this way we only have to do a single induction argument, and then we can always answer any such exercise by checking a finite number of values. Presumably the exercise will give us the right polynomial!

share|improve this answer
add comment

More simply: both sides are functions (on $\Bbb N)$ satisfying the recurrence $\rm\:f(n\!+\!1)-f(n) = (n\!+\!1)^3\:$ with initial condition $\rm\:f(0) = 0,\:$ hence they agree by the uniqueness theorem for such recurrences (which has a very simple inductive proof only a couple lines long -- try it!)

The proposed solution works somewhat similarly. If $\rm\:p(n)\:$ is a polynomial in $\rm\:n\:$ of degree $\rm\:d\:$ then one easily checks by undetermined coefficients that there exists a polynomial of degree $\rm\:d+1\:$ satisfying $\rm\:f(n+1) - f(n) = p(n),\:$ because the resulting system of equations has triangular form with nonzero diagonal entries $\rm\:a_{i,i} = i.\:$ Solving we obtain a solution $\rm\:f(n),\:$ so $\rm\:p(n) = f(n)-f(0)\:$ is a solution satisfying our initial condition $\rm\:p(0) = 0.\:$ Therefore, by the above uniqueness theorem, this polynomial function solution is unique (as a function on $\,\Bbb N).$

Thus, since we know that the solution has polynomial form, to verify that a particular polynomial is a solution, it suffices to check that it is a solution at sufficiently many points, since a polynomial over a field (or domain) of degree $\rm\:n\:$ is determined uniquely by its values at $\rm\:n+1\:$ distinct points.

Remark $\ $ Although it plays no role here, it is worth remarking that over finite rings there may be subtleties in similar problems due to the fact that there may not be a one-to-one correspondence between formal polynomials and polynomial functions, e.g. over $\rm\,\Bbb Z/p = $ integers mod $\rm p,\:$ we have $\rm\:x^p = x\:$ as functions but not as formal polynomials.

share|improve this answer
add comment

If $f$ and $g$ are polynomials of degree at most $n$ and if $f = g$ at $n + 1$ distinct points, you have $f = g$. This is a purely algebraic phenomenon, which is established via the Vandermonde Determinant.

To invoke this principle in your case , you must first show $\sum_{k=1}^n k^r$ is a polynomial of degree at most $r + 2$ (for you $r = 3$). Then you have a full proof.

share|improve this answer
    
To be precise, one must show the sum is equal to a polynomial when considered as functions on $\,\Bbb N.$ Also, since the statement in the first paragraph is true iff the coefficient ring is a domain, I wouldn't call it a purely algebraic phenomenon but, rather, a field-theoretic (or domain-theoretic) one. –  Bill Dubuque Nov 12 '12 at 16:15
    
Correct, Bill. And therein lies the sticky wicket that this poser of this question is trying to avoid. But he cannot avoid it this way. –  ncmathsadist Nov 12 '12 at 16:19
add comment

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.