Confusion on intuition for guessing a summation is a cubic

Question

A lecturer simply states that: $\sum_{i=0}^n i^2 =$ some cubic: $an^3 + bn^2 +cn +d$ and then goes on to solve for these variables to try and get an intuition to get the closed form expression of this sum. However I am not seeing the intuition whatsoever for picking a general cubic as a guess to this sum. I am having trouble wording this question because I understand the reasoning so little. Why does he guess to use a cubic? Does using a cubic here only work for very specific cases? Is he guessing a very close upper bound? Why can't the guess be to the 4th power(one more degree than cubic)?

Answer 1

The general statement is: $\sum_{i=0}^n i^k$ is a polynomial in $n$ of degree $k+1$ for any natural number $k$.

EDIT: Why should it be $k+1$? It's easy to show that if $P(x)$ is a polynomial of degree $d \ge 1$, $P(x)-P(x-1)$ is a polynomial of degree $d-1$. This is because when you expand $(x-1)^d$ you get $x^d - d x^{d-1} + \ldots$, and the $x^d$ term from $P(x)$ cancels the $x^d$ term from $P(x-1)$. But if $P(n) = \sum_{i=0}^n i^k$ you must have $P(n) - P(n-1) = n^k$, which is of degree $k$. So if any polynomial is going to work, it will need to have degree $k+1$.

Answer 2

$\sum_k k$ is a second-order polynomial ($I = \sum_{k=0}^{n} = \frac{(n)(n+1)}{2}$.

$\sum_k k^3 = I^2$ is a forth order polynomial. It seems reasonable to guess that it's a third order one.

Answer 3

So $n^3-(n-1)^3=3n^2-3n+1$

So $$\sum 3n^2=\sum \left(n^3-(n-1)^3+3n-1\right)$$

The cubic terms cancel by telescoping leaving $n^3$, and the lower order terms $3n+1$ can be summed using formulae already known to give a quadratic.

The key observation is that the difference equation for a cubic is a quadratic expression (first line), so if we want to sum quadratics we get cubics.

Obviously this can be generalised to higher orders.