The conjecture is that the sum of the numbers from 1 to n, each raised to some power k is a polynomial of the form:
(5) $\displaystyle \sum_{i=1}^{n} i^k= a_{k+1}n^{k+1} + a_{k}n^{k} + a_{k-1}n^{k-1} + \dots + a_{2}n^{2} + a_{1}n$
If this is so, then adding the $n_{th}+1$ term would equivalent to:
(5a) $\displaystyle \sum_{i=1}^{n} i^k + (n+1)^k = $
$\ $
$\qquad \qquad a_{k+1}(n+1)^{k+1} + a_{k}(n+1)^{k}+ a_{k-1}(n+1)^{k-1} + \dots + a_{2}(n+1)^{2} + a_{1}(n+1)$
Adding the $n_{th}+1$ term to equation 5 yields
(5b) $\displaystyle \sum_{i=1}^{n} i^k + (n+1)^k =$
$\ $
$\qquad \qquad \displaystyle a_{k+1}n^{k+1} + a_{k}n^{k} + a_{k-1}n^{k-1} + \dots + a_{2}n^{2} + a_{1}n+(n+1)^k$
Expanding the last term of 5b with the Binomial Theorem gives:
(5c) $\displaystyle \quad a_{k+1}n^{k+1} + a_{k}n^{k} + a_{k-1}n^{k-1} + \dots + a_{2}n^{2} + a_{1}n + \sum_{i=0}^k \binom{k}{i} n^{k-i}$
$\qquad \qquad = a_{k+1}n^{k+1} + a_{k}n^{k} + a_{k-1}n^{k-1} + \dots + a_{2}n^{2} + a_{1}n$
$\ $
$\qquad \qquad \quad + \binom{k}{0}n^k + \binom{k}{1}n^{k-1} + \dots \binom{k}{k-1}n + 1$
$\ $
$\qquad \qquad = a_{k+1}n^{k+1} + (a_k + \binom{k}{0})n^k + (a_{k-1} + \binom{k}{1})n^{k-1} +\dots (a_1 + \binom{k}{k-1})n + 1$
Now we expand the right side of 5a, also using the Binomial Theorem:
(5d) $\displaystyle a_{k+1} \sum_{i=0}^{k+1} \binom{k+1}{i} n^{k-i+1} + a_{k} \sum_{i=0}^{k} \binom{k}{i} n^{k-i} + a_{k-1} \sum_{i=0}^{k-1} \binom{k-1}{i} n^{k-i-1} + \dots + a_1n + a_1$
$\ $
$\qquad \qquad = a_{k+1}(\binom{k+1}{0} n^{k+1} + \binom{k+1}{1} n^{k} + \binom{k+1}{2} n^{k-1} + \dots + \binom{k+1}{k} n + 1)$
$\ $
$\qquad \qquad \quad + \ a_{k}(\binom{k}{0} n^{k} + \binom{k}{1} n^{k-1} + \binom{k}{2} n^{k-2} + \dots + \binom{k}{k-1} n + 1)$
$\ $
$\qquad \qquad \quad + \ a_{k-1}(\binom{k-1}{0} n^{k-1} + \binom{k-1}{1} n^{k-2} + \binom{k-1}{2} n^{k-3} + \dots + \binom{k-1}{k-2} n + 1)$
$\ $
$\qquad \qquad \quad + \ a_{1}n + a_{1}$
Collecting the coefficients of 5d in table form for easy reference:
(5e)
$$
\begin{array}{ccc}
n^{k+1} & n^k & n^{k-1} & n^{k-2} & \dots & n^1 & n^0 \\
a_{k+1}\binom{k+1}{0} & a_{k+1}\binom{k+1}{1} & a_{k+1}\binom{k+1}{2} & a_{k+1}\binom{k+1}{3} & \dots & a_{k+1}\binom{k+1}{k} & a_{k+1}\binom{k+1}{k+1} \\
& a_{k}\binom{k}{0} & a_{k}\binom{k}{1} & a_{k}\binom{k}{2} & \dots & a_{k}\binom{k}{k-1} & a_{k}\binom{k}{k} \\
& & a_{k-1}\binom{k-1}{0} & a_{k-1}\binom{k-1}{1} & \dots & a_{k-1}\binom{k-1}{k-2} & a_{k-1}\binom{k-1}{k-1} \\
& & & a_{k-2}\binom{k-2}{0} & \dots & a_{k-2}\binom{k-2}{k-3} & a_{k-2}\binom{k-2}{k-2} \\
& & & & \dots & a_{1}\binom{1}{0} & a_{1}\binom{1}{1} \\
\end{array}
$$
For two polynomials of equal order to be equal, the coefficients must be equal. Therefore, the coefficients of 5c must equal the coefficients of 5e. Aligning the coefficients:
(5f.1) $a_{k+1}=a_{k+1} \binom{k+1}{0}$
(5f.2) $a_k+ \binom{k}{0}=a_{k+1} \binom{k+1}{1}+a_k \binom{k}{0}$
(5f.3) $a_{k-1}+ \binom{k}{1}=a_{k+1} \binom{k+1}{2}+a_k \binom{k}{1}+a_{k-1} \binom{k-1}{0}$
(5f.4) $a_{k-2}+ \binom{k}{2}=a_{k+1} \binom{k+1}{3}+a_k \binom{k}{2}+a_{k-1} \binom{k-1}{1}+a_{k-2} \binom{k-2}{0}$
(5f.5) $a_{1}+ \binom{k}{k-1}=a_{k+1} \binom{k+1}{k}+a_k \binom{k}{k-1}+a_{k-1} \binom{k-1}{k-2}+a_{k-2} \binom{k-2}{k-3} +\dots +a_{1} \binom{1}{0}$
(5f.6) $1=a_{k+1} \binom{k+1}{k+1}+a_k \binom{k}{k}+a_{k-1} \binom{k-1}{k-1}+a_{k-2} \binom{k-2}{k-2} +\dots +a_{1} \binom{1}{1}$
Since k things taken 0 at a time is 1, the last coefficient to the right of the equals sign of 5f.1 through 5f.5 is equal to the first coefficient to the left of the equals sign, so it can be subtracted out. k things taken k at a time is also 1, and k things taken 1 at a time is k, 5f.1 through 5f.6 can be re-written as:
(5f.1a) $a_{k+1}=a_{k+1}$
(5f.2a) $\binom{k}{0} = a_{k+1}(k+1)$
(5f.3a) $\binom{k}{1} = a_{k+1}\binom{k+1}{2}+a_{k}(k)$
(5f.4a) $\binom{k}{2} = a_{k+1}\binom{k+1}{3}+a_{k}\binom{k}{2}+a_{k-1}(k-1)$
(5f.5a) $\binom{k}{k-1} = a_{k+1}\binom{k+1}{k}+a_{k}\binom{k}{k-1}+a_{k-1}\binom{k-1}{k-2} + a_{k-2}\binom{k-2}{k-3} + \dots + a_{2}(2)$
(5f.6a) $1=a_{k+1} + a_{k} + a_{k-1} + a_{k-2} + \dots a_{1}$
5f.1a adds no useful information, but 5f.2a shows that
5f.2b $a_{k+1}= \frac{1}{k+1}$
Observation of the general pattern for 5f.2a through 5f.6a leads to the solution, equation 6.
