1
$\begingroup$

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.

  • 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.2012-11-12
  • 0
    It's not clear what your subject means, btw. Why do you call this "infinite induction?"2012-11-12
  • 0
    @GregRos Why does he need continuity? This is a discrete values problem.2012-11-12
  • 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.2012-11-12
  • 0
    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.2012-11-12
  • 0
    @GregRos It follows from long division of polynomials, and the fact that in $\mathbb R$ a product is zero if and only if one term is zero. No Analysis is required.2012-11-12
  • 0
    Yeah you're right. After I posted my comment I realized that as long as you have some basic statements on polynomials it is easy to prove. E.g. If $P$ and $Q$ are polynomials and $M = \max{(\deg{P}, \deg{Q})}+1$ if you prove that $P-Q$ has at least M roots, it must be the zero polynome. I just immediately go to analysis of that sort when I see a problem like this. Still, the answer lacks a lot.2012-11-12

6 Answers 6

7

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.

  • 0
    I fixed the indices, I meant $n$ instead of $i$.2012-11-12
  • 0
    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.2012-11-12
  • 0
    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?2012-11-12
  • 0
    Yes, but I'm fairly sure that proving that is exactly as hard as proving the equality right away.2012-11-12
  • 0
    I do not think this is a serious counterexample. If I tell you that the left hand side is a polynomial of degree *exactly* 2, and not just at most 2, then it goes away.2012-11-12
  • 0
    The theorem itself should say that you need to find at least $M$ points where the two polynomes are equal, where $P,Q$ are the polynomes and $M=\max{(\deg{P},\deg{Q})} + 1$. If these conditions hold (this counter-example doesn't) then $P=Q$. This is because $P-Q$ cannot have $M$ roots, as an atmost $M-1$ degree polynome unless it is $0$.2012-11-12
  • 0
    @TonyHuynh: do you know how to prove that $\sum_i^ni$ is a polynomial of degree $2$ on $n$ without using induction? Because if you will use induction, you might as well prove the equality right away.2012-11-12
  • 0
    Sure, there is a proof by picture of that [here](http://mathoverflow.net/questions/8846/proofs-without-words). But that's not my point. I already said in my answer that the polynomial route is not the most efficient route to go. However, I can imagine some situations where it would be more efficient. For example, if we had to say verify the formulas for the first $n$ $k$th powers (for $k=1, \dots, 10$), then it is probably more efficient to go for the polynomial route and do the induction *once*, rather than perform 10 different inductions.2012-11-12
  • 1
    Thanks for all the answers, it was nice to see such a diverse set of opinions in one question.2012-11-12
  • 0
    @MartinArgerami, "you don't know a priori that the left-hand-side is a polynomial of degree 4 on n." is just like saying you don't know the sum of two even numbers is even. Of course it is, this is such a basic result you don't need to re-prove it every time.2012-11-12
  • 0
    your "counterexample" is not a counterexample, it just illustrates a mistake a beginner might make. since it's the discrete integral of a degree 1 polynomial (therefore a degree 2 polynomial) on the LHS. But a degree 1 polynomial on the RHS. You can only prove equality by testing values when they have the same degree.2012-11-12
  • 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.2012-11-12
3

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.

1

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!

0

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.

  • 0
    Yup, $\sum_n f(x)=g(n)$ is the same as $g(n+1)-g(n)=f(n)$.2012-11-12
  • 0
    Mm, that I know, I meant that specific equation is true at a glance but might not be.2012-11-12
  • 0
    Mathematica says it's actually $(1+n)^3$, so we're off by one.2012-11-12
  • 0
    Might be. You can calculate it directly using discrete calculus but I didn't bother :P2012-11-12
  • 0
    It's $(n+1)^3$. That's what allows the induction step.2012-11-12
0

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.

  • 1
    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.2012-11-12
  • 0
    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.2012-11-12
-1

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.

  • 4
    Note that if discrete calculus is admitted, the sum can be calculated directly and simply.2012-11-12