Today we will learn about how to derive the formula for power summation $$S_k(n) = 1^k + 2^k + 3^k + \dots + n^k .$$
Our main tool is the following binomial identity
$$(x+y)^k = x^k + {k \choose 1} x^{k-1} y + {k \choose 2} x^{k-2} y^2 + {k \choose 3} x^{k-3} y^3 + \dots + {k \choose {k-1}} x y^{k-1} + y^k.$$
First, let us calculate $$S_1(n) = 1 + 2 + 3 + \dots + n .$$
Using the following binomial identity $$(m+1)^{2} = m^{2} + 2 m + 1,$$ we have $$(m+1)^{2} - m^{2} = 2 m + 1.$$
Substitute $m=1,2, \dots, n$ into the above equation and then sum them up, $$\sum_{m=1}^{n} [(m+1)^{2} - m^{2}] = \sum_{m=1}^{n} [2 m + 1],$$ we obtain $$(n+1)^{2} - 1^{2} = 2 S_1(n) + n.$$
Thus, $$2 S_1(n) = (n+1)^{2} - 1^{2} - n = n^2 + n = n(n+1)$$
From here, we derive our familiar formula $$S_1(n) = 1 + 2 + \dots + n = \frac{1}{2} n(n+1).$$
Next, we calculate $$S_2(n) = 1^2 + 2^2 + 3^2 + \dots + n^2 .$$
Using the following binomial identity $$(m+1)^{3} = m^{3} + 3 m^2 + 3 m + 1,$$ we have $$(m+1)^{3} - m^{3} = 3 m^2 + 3 m + 1.$$
Substitute $m=1,2, \dots, n$ into the above equation and then sum them up, $$\sum_{m=1}^{n} [(m+1)^{3} - m^{3}] = \sum_{m=1}^{n} [3 m^2 + 3 m + 1],$$ we obtain $$(n+1)^{3} - 1^{3} = 3 S_2(n) + 3 S_1(n) + n.$$
Thus, $$3 S_2(n) = (n+1)^{3} - 1^{3} - n - 3 S_1(n) $$ $$= (n+1)^{3} - 1^{3} - n - \frac{3}{2} n(n+1) = \frac{1}{2} n(n+1)(2n+1)$$
From here, we derive the formula $$S_2(n) = 1^2 + 2^2 + \dots + n^2 = \frac{1}{6} n(n+1)(2n+1).$$
Similarly, we determine $S_3(n)$ as follows $$(n+1)^{4} - 1^{4} = 4 S_3(n) + 6 S_2(n) + 4 S_1(n) + n$$ and $$S_3(n) = 1^3 + 2^3 + \dots + n^3 = \frac{1}{4} n^2 (n+1)^2.$$
Find $S_4(n)$: $$(n+1)^{5} - 1^{5} = 5 S_4(n) + 10 S_3(n) + 10 S_2(n) + 5 S_1(n) + n$$ and $$S_4(n) = 1^4 + 2^4 + \dots + n^4 = \frac{1}{30} (6 n^5 + 15 n^4 + 10 n^3 -n).$$
Find $S_5(n)$: $$(n+1)^{6} - 1^{6} = 6 S_5(n) + 15 S_4(n) + 20 S_3(n) + 15 S_2(n) + 6 S_1(n) + n$$ and $$S_5(n) = 1^5 + 2^5 + \dots + n^5 = \frac{1}{12} (2 n^6 + 6 n^5 + 5 n^4 -n^2).$$
In general, for arbitrary value of $k$, we use the following binomial identity $$(m+1)^{k+1} = m^{k+1} + (k+1) m^{k} + {{k+1} \choose 2} m^{k-1} + \dots + {{k+1} \choose {k-1}} m^{2} + (k+1) m + 1.$$
We obtain $$(m+1)^{k+1} - m^{k+1} = (k+1) m^{k} + {{k+1} \choose 2} m^{k-1} + \dots + {{k+1} \choose {k-1}} m^{2} + (k+1) m + 1.$$
Take the sum for $m=1,2, \dots, n$, $$\sum_{m=1}^{n}[(m+1)^{k+1} - m^{k+1}]$$ $$ = \sum_{m=1}^{n} [(k+1) m^{k} + {{k+1} \choose 2} m^{k-1} + \dots + {{k+1} \choose {k-1}} m^{2} + (k+1) m + 1]$$ we obtain the formula $$(n+1)^{k+1} - 1^{k+1}$$ $$ = (k+1) S_k(n) + {{k+1} \choose 2} S_{k-1}(n) + \dots + {{k+1} \choose {k-1}} S_2(n) + (k+1) S_1(n) + n.$$
This formula enables us to determine $S_k(n)$ from $S_{k-1}(n)$, $\dots$, $S_2(n)$, $S_1(n)$.
So we have learned how to derive formula for a general summation $S_k(n)$. Let us stop here for now. Next post, we will investigate the following summation $$S_{-k}(n) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{n^k}.$$
Hope to see you then.
Homework.
Prove that
$$1^{1000} + 2^{1000} + 3^{1000} + \dots + 2010^{1000} = 0 \pmod{2011},$$
$$1^{2012} + 2^{2012} + 3^{2012} + \dots + 2010^{2012} = 0 \pmod{2011}.$$