1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Traviata Oct 23 '14 at 0:12
  • $\begingroup$ this is because the sum telescopes. Just sum from x=1 to x=n the last equation. $\endgroup$ – mookid Oct 23 '14 at 0:23
1
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ Thank you, Patrick. Regarding telescoping sums - could you explain a little more how you got to that expression for $P_k(N)$? $\endgroup$ – Traviata Oct 23 '14 at 0:22
  • 1
    $\begingroup$ @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$. $\endgroup$ – Patrick Da Silva Oct 23 '14 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.