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.

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

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

  • 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