Partial Sums

In a loose sense, summation is related to integration, and using this intuition we can expect the nth partial sum formula for this sum to be in the form of a third degree polynomial. A third degree polynomial is uniquely defined by four points. So we construct a polynomial $p(x) = ax^3+bx^2+cx+d$ and we compute various partial sums. Doing this gives us $p(0)=1$ , $p(1)=2$ , $p(2)=5$ , $p(3)=12$ . We can then construct the following system of linear equations

$\begin{aligned} 0a + 0b + 0c + d = & 1\\ a + b + c + d =& 2 \\ 8a+4b+2c+d=& 5 \\ 27a + 9b + 3c + d =& 12 \end{aligned}$

Which can easily be solved by putting it into a matrix and computing the RREF of that matrix, or with whatever method one uses.

$\begin{bmatrix} 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 2 \\ 8 & 4 & 2 & 1 & 5 \\ 27 & 9 & 3 & 1 & 12 \end{bmatrix} \to \begin{bmatrix} 1 & 0 & 0 & 0 & \frac{1}{3} \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & \frac{2}{3} \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}$

Which of course gives us $a= \frac{1}{3}$ , $b = 0$ , $c = \frac{2}{3}$ , $d = 1$ . Therefore the $\textit{unique}$ polynomial that passes through the four summation points is $p(x) = \frac{1}{3}x^3 + \frac{2}{3}x +1$ , then restricting the argument to positive integers gives us the partial sum formula:

$p(n) = \frac{1}{3}n^3 + \frac{2}{3}n + 1 = \boxed{\frac{1}{3}(n+1)(n^2-n+3)}$ Alternatively if one recognizes the three sums making up $k^2-k+1$ then this problem is easier. $\begin{aligned} \sum_{k=0}^n k^2 & = \frac{1}{6}n(n+1)(2n+1) \\ \sum_{k=0}^n k & = \frac{1}{2}n(n+1)\\ \sum_{k=0}^n 1 & = n+1\\ \end{aligned}$ Combining all of these formulas yields us the correct result: $\begin{aligned} \sum_{k=0}^n k^2 - k + 1& = \frac{1}{6}n(n+1)(2n+1) - \Big[ \frac{1}{2}n(n+1)\Big] + n+1\\ \sum_{k=0}^n k^2 - k + 1 & = \boxed{\frac{1}{3}(n+1)(n^2-n+3)} \end{aligned}$