There are many methods of proving or deriving the formulae for the sum, with m from 1 to n, of the integers m to a fixed natural-number power p. Each method has its advantages and disadvantages. It also provides its own insight. Since matrix inversion is required for some methods, all methods must involve (perhaps inconspicuously) matrix inversion. The easiest manual method of verifying these formulae, for any fixed p, is by means of Mathematical Induction on n. Since we know that, for a given p, the formula is a polynomial of degree (p + 1), the easiest computational method is to extrapolate the summations from their values at n = 1 to n = p + 2. Here we will present several methods.
This method proves that each formula is a polynomial of degree (p + 1). This method lends itself to relatively easy hand calculation; because, the matrix is generated as a triangular-matrix.
Notation: Let the summation, with m running from 1 to n, of the function f(m) be designated by S(f(m), n). Let the binomial coefficient C(p, q) be C(p, q) = p! / (q! (p - q)!). Then, the binomial theorem may be written as
This formula may be established by Mathematical Induction upon q, nested within Mathematical Induction upon p. Now, write
Sum it, with m running from 1 to n. All except two terms on the left-hand side cancel. We obtain
This is a recursive -- upon p -- expression.
For p = 0, we have (n + 1) - 1 = S(1, n). Hence, immediately, we obtain the obvious formula
For p = 1, we have
(n + 1)^2 - 1 = 2 S(m, n) + S(1, n).
Employ the binomial theorem on the left-hand side and substitute for S(1, n) on the right-hand side, to obtain
(n^2 + 2 n + 1) - 1 = 2 S(m, n) + n.
Solve for S(m, n), to obtain the familiar formula
For p = 2, we have
(n + 1)^3 - 1 = 3 S(m^2, n) + 3 S(m, n) + S(1, n).
Employ the binomial theorem on the left-hand side and substitute for each -- except the highest -- S on the right-hand side, to obtain
(n^3 + 3 n^2 + 3 n + 1) - 1 = 3 S(m^2, n) + 3 ((n^2 + n) / 2) + n.
Solve for S(m^2, n), to obtain
For p = 3, we have
(n + 1)^4 - 1 = 4 S(m^3, n) + 6 S(m^2, n) + 4 S(m, n) + S(1, n).
As previously, it simplifies to
(n^4 + 4 n^3 + 6 n^2 + 4 n + 1) - 1 = 4 S(m^3, n) + 6 ((2 n^3 + 3 n^2 + n) / 6) + 4 ((n^2 + n) / 2) + n.
Solve for S(m^3, n), to obtain
For p = 4, we have
(n + 1)^5 - 1 = 5 S(m^4, n) + 10 S(m^3, n) + 10 S(m^2, n) + 5 S(m, n) + S(1, n).
As previously, it simplifies to
(n^5 + 5 n^4 + 10 n^3 + 10 n^2 + 5 n + 1) - 1 = 5 S(m^4, n) + 10 ((n^4 + 2 n^3 + n^2) / 4) + 10 ((2 n^3 + 3 n^2 + n) / 6) + 5 ((n^2 + n) / 2) + n.
Multiply through by the common denominator of 6, to obtain
6 n^5 + 30 n^4 + 60 n^3 + 60 n^2 + 30 n = 30 S(m^4, n) + 15 (n^4 + 2 n^3 + n^2) + 10 (2 n^3 + 3 n^2 + n) + 15 (n^2 + n) + 6 n.
On the right-hand side, consolidate like terms, to obtain
= 30 S(m^4, n) + (15 n^4 + 50 n^3 + 60 n^2 + 31 n.
Solve for S(m^4, n), to obtain
For p = 5, we have
(n + 1)^6 - 1 = 6 S(m^5, n) + 15 S(m^4, n) + 20 S(m^3, n) + 15 S(m^2, n) + 6 S(m, n) + S(1, n).
As previously, it simplifies to
(n^6 + 6 n^5 + 15 n^4 + 20 n^3 + 15 n^2 + 6 n + 1) - 1 =
= 6 S(m^5, n) + 15 ((6 n^5 + 15 n^4 + 10 n^3 - n) / 30) + 20 ((n^4 + 2 n^3 + n^2) / 4) + 15 ((2 n^3 + 3 n^2 + n) / 6) + 6 ((n^2 + n) / 2) + n.
Multiply through by the common denominator of 2, to obtain
2 n^6 + 12 n^5 + 30 n^4 + 40 n^3 + 30 n^2 + 12 n =
= 12 S(m^5, n) + (6 n^5 + 15 n^4 + 10 n^3 - n) + 10 (n^4 + 2 n^3 + n^2) + 5 (2 n^3 + 3 n^2 + n) + 6 (n^2 + n) + 2 n.
On the right-hand side, consolidate like terms, to obtain
= 12 S(m^5, n) + (6 n^5 + 25 n^4 + 40 n^3 + 31 n^2 + 12 n).
Solve for S(m^5, n), to obtain
Summary
If we can guess the formula, this method is the easiest hand method for verification for a specific value of p.
For each of the foregoing values of p, it is easy to see that S(m^p, 1) = 1. Thus, we have performed the first step of Mathematical Induction.
For the second step of Mathematical Induction, we have to establish that S(m^p, n) - S(m^p , n - 1) = m^p, for each value of p for which we desire this proof. (Conventionally, one goes from n to n+1; but, here it is much easier to go from n-1 to n.) Since the summations are polynomials in m, we employ Horner's method to find S(m^p, n - 1) from the given S(m^p, n). Then, we subtract from S(m^p, n) to obtain m^p.
For p = 0, we have
| 1 | 0 | |
| -1 | ||
| -1) | 0 | -1 |
| 0 | 1 |
We have subtracted the last row of the Horner's method -- the next to the last row of the table -- from the first row, to obtain the bottom row of the table. It should give us 0 1 0 0 0 .... It does so. Ok
For p = 1, to clear of fractions, first multiply the polynomial by 2. Then, we have
| 1 | 1 | 0 | |
| -1 | 0 | ||
| -1) | 1 | 0 | 0 |
| -1 | |||
| 1 | -1 | ||
| 0 | 2 | 0 |
We have subtracted the last row of the Horner's method -- the next to the last row of the table -- from the first row, to obtain the bottom row of the table. It should give us 0 2 0 0 0 .... It does so. Ok
For p = 2, first multiply the polynomial by 6. Then, we have
| 2 | 3 | 1 | 0 | |
| -2 | -1 | 0 | ||
| -1) | 2 | 1 | 0 | 0 |
| -2 | 1 | |||
| 2 | -1 | 1 | ||
| -2 | ||||
| 2 | -3 | |||
| 0 | 6 | 0 | 0 |
We have subtracted the last row of the Horner's method -- the next to the last row of the table -- from the first row, to obtain the bottom row of the table. It should give us 0 6 0 0 0 .... It does so. Ok
For p = 3, first multiply the polynomial by 4. Then, we have
| 1 | 2 | 1 | 0 | 0 | |
| -1 | -1 | 0 | 0 | ||
| -1) | 1 | 1 | 0 | 0 | 0 |
| -1 | 0 | 0 | |||
| 1 | 0 | 0 | 0 | ||
| -1 | 1 | ||||
| 1 | -1 | 1 | |||
| -1 | |||||
| 1 | -2 | ||||
| 1 | 4 | 0 | 0 | 0 |
We have subtracted the last row of the Horner's method -- the next to the last row of the table -- from the first row, to obtain the bottom row of the table. It should give us 0 4 0 0 0 .... It does so. Ok
For p = 4, first multiply the polynomial by 30. Then, we have
| 6 | 15 | 10 | 0 | -1 | 0 | |
| -6 | -9 | -1 | 1 | 0 | ||
| -1) | 6 | 9 | 1 | -1 | 0 | 0 |
| -6 | -3 | 2 | -1 | |||
| 6 | 3 | -2 | 1 | -1 | ||
| -6 | 3 | -1 | ||||
| 6 | -3 | 1 | 0 | |||
| -6 | 9 | |||||
| 6 | -9 | 10 | ||||
| -6 | ||||||
| 6 | -15 | |||||
| 0 | 30 | 0 | 0 | 0 | 0 |
We have subtracted the last row of the Horner's method -- the next to the last row of the table -- from the first row, to obtain the bottom row of the table. It should give us 0 30 0 0 0 .... It does so. Ok
For p = 5, first multiply the polynomial by 12. Then, we have
| 2 | 6 | 5 | 0 | -1 | 0 | 0 | |
| -2 | -4 | -1 | 1 | 0 | 0 | ||
| -1) | 2 | 4 | 1 | -1 | 0 | 0 | 0 |
| -2 | -2 | 1 | 1 | 0 | |||
| 2 | 2 | -1 | 0 | 0 | 0 | ||
| -2 | 0 | 1 | -1 | ||||
| 2 | 0 | -1 | 1 | -1 | |||
| -2 | 2 | -1 | |||||
| 2 | -2 | 1 | 0 | ||||
| -2 | 4 | ||||||
| 2 | -4 | 5 | |||||
| -2 | |||||||
| 2 | 6 | ||||||
| 0 | 12 | 0 | 0 | 0 | 0 | 0 |
We have subtracted the last row of the Horner's method -- the next to the last row of the table -- from the first row, to obtain the bottom row of the table. It should give us 0 12 0 0 0 .... It does so. Ok
Since these formulae are polynomials of degree (p + 1), it suffices to check them for (p + 2) points. I have checked them for n on [1, 20], on an Excel spread-sheet.
Copyright (c) 2002 by R.I. 'Scibor-Marchocki. Last modified on Wednesday 24-th April 2002. mailto:webmaster@rism.com