What is the sum of 1*2 + 2*3 + ... + (n-1)n?
Write out a bunch of the sums:
1*2 = 2
1*2 + 2*3 = 2 + 6 = 8
1*2 + 2*3 + 3*4 = 8 + 12 = 20
1*2 + 2*3 + 3*4 + 4*5 = 20 + 20 = 40
1*2 + 2*3 + 3*4 + 4*5 + 5*6 = 40 + 30 = 70
1*2 + 2*3 + 3*4 + 4*5 + 5*6 + 6*7 = 70 + 42 = 112
Make a difference table:
List those partial sum in a column. Subtract each number
from the number just below it, and write that number to
the right of that number. To get the 6 at the top of the 2nd
column we subtract the 2 from the 8 in the 1st column and
wrote it just right of the 2. To get the 42 at the bottome
of the 2nd column we subtracted the 70 from the 112 below it
2 6 6 2
8 12 8 2
20 20 10 2
40 30 12
70 42
112
We continue to make the chart until we get a column with
all the same numbers in it. Since it took three columns
to get a column all the same number we know to assume that
the formula for the nth term is a 3rd degree polynomial
in n:
S(n) = An³ + Bn² + Cn² + D
There are four unknown constants so we will substitute the
first 4 terms of the sequence:
S(1) = A(1)³ + B(1)² + C(1)² + D = A + B + C + D = 2
S(2) = A(2)³ + B(2)² + C(2)² + D = 8A + 4B + 2C + D = 8
S(3) = A(3)³ + B(3)² + C(3)² + D = 27A + 9B + 3C + D = 20
S(4) = A(4)³ + B(4)² + C(4)² + D = 64A + 16B + 4C + D = 40
A + B + C + D = 2
8A + 4B + 2C + D = 8
27A + 9B + 3C + D = 20
64A + 16B + 4C + D = 40
Subtracting the 1st equation from the 2nd:
7A + 3B + C = 6
Subtracting the 2nd equation from the 3rd:
19A + 5B + C = 12
Subtracting the 3rd equation from the 4th:
37A + 7B + C = 20
So now we have the system
7A + 3B + C = 6
19A + 5B + C = 12
37A + 7B + C = 20
Subtracting the 1st equation from the 2nd:
12A + 2B = 6, dividing thru by 2, 6A + B = 3
Subtracting the 2nd equation from the 3rd:
18A + 2B = 8, dividing thru by 2, 9A + B = 4
So now we have the system
6A + B = 3
9A + B = 4
Subtracting the 1st equation from the 2nd:
3A = 1
A =
Substitute in
6A + B = 3
6( + B = 3
2 + B = 3
B = 1
Substitute in
7A + 3B + C = 6
7( + 3 + C = 6
Multiply thru by 3
7 + 9 + 3C = 18
16 + 3C = 18
3C = 2
C =
Substitute in
A + B + C + D = 2
+ 1 + + D = 2
Multiply thru by 3
1 + 3 + 2 + 3D = 6
6 + 3D = 6
3D = 0
D = 0
So the formula is
S(n) = An³ + Bn² + Cn² + D
S(n) = n³ + 1n² + n + 0
Multiply thru by 3
3S(n) = n³ + 3n² + 2n
3S(n) = n(n² + 3n + 2)
3S(n) = n(n+1)(n+2)
S(n) = n(n+1)(n+2)
Edwin