# Proof by “infinite induction”

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.

-
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. –  Just Greg 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
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. –  Just Greg Nov 12 '12 at 14:53

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.

-
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
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
@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

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.

-

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!

-

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.

-
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

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.

-
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. –  Just Greg 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 –  Just Greg 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

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.

-
Note that if discrete calculus is admitted, the sum can be calculated directly and simply. –  Just Greg Nov 12 '12 at 14:33