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!
 A: 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$
A: 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,
