# Inductive proof of the degree of a polynomial

Here is the problem:

Assume that there is a polynomial $P(x)$ of degree 4 such that for all $N \in \mathbb{N}$,

$$P(N) = \sum\limits_{n=0}^N n^3$$

Find the polynomial. Use induction to prove that the formula is correct.

...............

Not sure where to start on this, but for the base case, I did $n=0$ results in $0^3=0$. How can I prove this has degree $4$, since $0^5=0$, for example? Also, how can I prove it for N in the inductive step?

Also... before I even get there, I'm puzzled about the polynomial. I know it's something like:

$$ax^4+bx^3+cx^2+dx+e = x^3 + (x-1)^3 + (x-2)^3 + \cdots + 1$$

and you get an $x^4$ term on the RHS because you have $x$ number of times $x^3$, but I don't know where to go from there to find the polynomial.

Thank you!

Hint: compute $$P(x+1) - P(x)$$ with $P(x) = ax^4 + bx^3 + cx^2 + dx$

and try to find $a,b,c,d$ so that $P(x+1) - P(x) = x^3$

• Thanks so much. How did you know to do $P(x+1) - P(x)$? and is it ok to just do $x^3$ on the RHS, not $x^3 + (x-1)^3 + ... + 1$? Oct 23, 2014 at 0:12
• this is because the sum telescopes. Just sum from x=1 to x=n the last equation. Oct 23, 2014 at 0:23

To compute the polynomial using a brute force approach, you can always use this : http://en.wikipedia.org/wiki/Lagrange_polynomial

Your polynomial has degree $4$, so it will be a bit painful but you can expand it using a computer program if you're not up for it.

Alternatively, the standard approach to compute this polynomial is using telescopic sums. Denote by $$P_k(N) = \sum_{n=0}^N n^k.$$ Note that $P_0(N) = N+1$ and $P_1(N) = \frac{N(N+1)}2$. For $P_2(N)$, you can notice that $$(N+1)^3 - 1 = \sum_{n=1}^N (n+1)^3 - n^3 = \sum_{n=0}^N (3n^2 + 3n+1) = 3 P_2(N) + 3 P_1(N) + P_0(N)$$ which after isolating and substituting the previous formulas for $P_1$ and $P_0$, gives you the formula $$P_2(N) = \frac{(N+1)^3 - 1 - 3P_1(N) - P_0(N)}3 = \frac{N(N+1)(2N+1)}6.$$ Note that this is a polynomial of degree $3$ in $N$ (not in $n$) which gives the values of $P_2$. You are asked to find a polynomial of degree $4$ in $N$ which gives the values of $P_3$. Starting with the expression $(N+1)^4 - 1$, can you get a similar expression for $P_3(N)$?

Hope that helps,

• Thank you, Patrick. Regarding telescoping sums - could you explain a little more how you got to that expression for $P_k(N)$? Oct 23, 2014 at 0:22
• @Kris : I got an expression for $P_2(N)$, not for $P_k(N)$. Do you mean my definition of $P_k(N)$? I just took your definition of your $P(N)$ and substituted $k$ for $3$. Oct 23, 2014 at 12:19