Express $\sum_{i=0}^n (3^3 − 6 + 2)$ as a polynomial $p(n)$

Question

How would I express $\sum_{i=0}^n (3^3 − 6 + 2)$ as a polynomial $p(n)$ and also prove that the sum equals $p(n)$ using induction?

Answer 1

There are formulas for the summation of powers, to find for example here: Sum of $n$, $n^2$, or $n^3$

\begin{align} p(n) = \sum_{i=0}^n \left(3i^3 - 6i + 2\right) &= 2 + \sum_{i=1}^n \left(3i^3 - 6i + 2\right) \\ &= 2 + 3 \sum_{i=1}^n i^3 - 6 \sum_{i=1}^n i + 2 \sum_{i=1}^n 1 \\ &= 2 + 3 \frac{n^2 (n+1)^2}{4} - 6\frac{n(n+1)}{2} + 2n \\ &= \frac{3}{4} n^4 + \frac{3}{2} n^3 + \frac{9}{4} n^2 - n + 2 \end{align}

For the proof by induction, you have to show that the left hand side (LHS) equals everytime to the right hand side (RHS).

Lets assume, it is true for all $p(m)$ with $m < n$. Lets look at the step from $n-1$ to $n$.

Step difference on RHS:

$$ \begin{align} p(n) - p(n-1) &= \frac{3}{4} n^4 + \frac{3}{2} n^3 + \frac{9}{4} n^2 - n + 2 \\ &- \frac{3}{4} (n-1)^4 - \frac{3}{2} (n-1)^3 - \frac{9}{4} (n-1)^2 + (n-1) - 2 \\ &= 3 n^3 -6n + 2 \end{align} $$

Step difference on the LHS:

\begin{align} p(n) - p(n-1) &= \sum_{i=0}^n \left(3i^3 - 6i + 2\right) - \sum_{i=0}^{n-1} \left(3i^3 - 6i + 2\right) \\ &= 3n^3 - 6n + 2 \end{align}

So, the all step differences are the same on LHS and RHS.

Now, lets research the base case $p(0)$. And as you will see, they are the same on LHS and RHS, too.

So, if the start is the same and the difference at each step is the same, then each step is the same.

Ergo: LHS $=$ RHS.

\begin{align} p(n) = \sum_{i=0}^n \left(3i^3 - 6i + 2\right) &= \frac{3}{4} n^4 + \frac{3}{2} n^3 + \frac{9}{4} n^2 - n + 2 \end{align}