Inductive proof of the degree of a polynomial

Question

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!

Answer 1

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$

Answer 2

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,