Math Newsletter number 9;Wednesday, September 22, 2010.
If you send any part of this newsletter to a friend, please
also include this paragraph. To subscribe or unsubscribe,
send a personal email request to kermit@polaris.net
Archive is at

Sum of same power of consecutive integers.

How would we find the formula for the sum
1 + 2 + 3 + ... + n, where the value of n is not yet
specified?
One approach is to examine the first few sums and look for a
pattern.
1 = 1 = 1 * 1
1 + 2 = 3 = 1 * 3
3 + 3 = 6 = 2 * 3
4 + 6 = 10 = 2 * 5
5 + 10 = 15 = 3 * 5
6 + 15 = 21 = 3 * 7
7 + 21 = 28 = 4 * 7
8 + 28 = 36 = 4 * 9
9 + 36 = 45 = 5 * 9
10 + 45 = 55 = 5 * 11

The pattern is now clear. But how can we simplify the
pattern enough to fit a formula to it?

The trick is to double the smaller of the two factors.

2 * 1 = 1 * 2
2 * 3 = 2 * 3
2 * 6 = 3 * 4
2 * 10 = 4 * 5
2 * 15 = 5 * 6
2 * 21 = 6 * 7
2 * 28 = 7 * 8
2 * 36 = 8 * 9
2 * 45 = 9 * 10
2 * 55 = 10 * 11

Now we can fit a simple formula to the pattern.

1 + 2 + 3 + ... + n = (n * (n+1) )/2

We could have found this formula by a different way.

In the sum, 1 + 2 + 3 + ... + n, there are n terms.

Since the terms are uniformly spaced, the average of the n
terms is the average of the first and last terms.

The average of the terms in 1 + 2 + 3 + ... + n is (n+1)/2

The average is the sum divided by the number of terms.

average = (1 + 2 + 3 + ... + n)/n

(n+1)/2 = (1 + 2 + 3 + ... + n)/n

1 + 2 + 3 + ... + n = n * (n+1)/2

A third way we could have found this formula is to use the
principle that a second degree polynomial is determined by
specifying three of its values.

We write,
1 + 2 + 3 + ... + n = a2 n**2 + a1 n + a0.

Then we substitute values of
1 + 2 + 3 + ... + n, for n = 0, n = 1, and n = 2.

For n = 0, we think of the sum as
0 + 1 + 2 + 3 + ... + n.

For n = 0, the sum is 0.
For n = 1, the sum is 1.
For n = 2, the sum is 1 + 2 = 3.

a2 * 2**2 + a1 * 2 + a0 = 3
a2 * 1**2 + a1 * 1 + a0 = 1
a1 * 0**2 + a1 * 0 + a0 = 0

From the last equation, we see that a0 = 0.

Eliminating a0 from the equations, we get,

4 a2 + 2 a1 = 3
1 a2 + 1 a1 = 1

Subtracting twice second equation from first,

(4 - 2 * 1) a2 + (2 - 2 * 1) a1 = (3 - 2 * 1)

2 a2 = 1
a2 = 1/2

substiting a2 = 1/2 into

1 a2 + 1 a1 = 1

yields

1/2 + a1 = 1

a1 = 1 - 1/2 = 1/2

1 + 2 + 3 + ... + n = (1/2) n**2 + (1/2)n

1 + 2 + 3 + ... + n = n * (n+1)/2

Now I will show the most general method to have found this
formula.
We presume that the formula for
0 + 1 + 2 + 3 + ... + n is of degree 2.

0 + 1 + 2 + 3 + ... + n = a2 * n**2 + a1 * n

This formula is also valid for the next larger n.

(0 + 1 + 2 + 3 + ... + n) + (n+1)
= a2 * (n+1)**2 + a1 * (n+1)

0 + 1 + 2 + 3 + ... + n = a2 * n**2 + a1 * n

Subtracting the second equation from the first,

(n+1) = a2 * [ (n+1)**2 - n**2 ] + a1 * [ (n+1) - 1]

n + 1 = a2 * (2 n + 1) + a1

n + 1 = 2 a2 n + a2 + a1

Since n represents all non negative integers,

we can match coefficients of same powers of n.

2 a2 = 1
a2 + a1 = 1

a2 = 1/2
a1 = 1/2

1 + 2 + 3 + ... + n = (1/2) n**2 + (1/2)n

1 + 2 + 3 + ... + n = n * (n+1)/2

This last method can be used to find the formula for
0**2 + 1**2 + 2**2 + 3**2 + ... + n**2.

0**2 + 1**2 + 2**2 + 3**2 + ... + n**2
= a3 * n**3 + a2 * n**2 + a1 * n

(0**2 + 1**2 + 2**2 + 3**2 + ... + n**2) + (n+1)**2
= a3 * (n+1)**3 + a2 * (n+1)**2 + a1 * (n+1)

0**2 + 1**2 + 2**2 + 3**2 + ... + n**2
= a3 * n**3 + a2 * n**2 + a1 * n

Subtracting equations, we get

(n+1)**2
= a3*[(n+1)**3 - n**3] + a2*[(n+1)**2 - n**2] + a1*[(n+1)-n]
= a3*[3*n**2+3*n+1]+a2*[2*n+1]+a1
= [3*a3]*n**2 + [3*a3+2*a2]*n + [a3+a2+a1]

n**2 + 2*n + 1 = [3*a3]*n**2 + [3*a3+2*a2]*n + [a3+a2+a1]

3 * a3 = 1
3*a3 + 2 * a2 = 2
a3 + a2 + a1 = 1

a3 = 1/3
a2 = 1/2
a1 = 1/6

0**2 + 1**2 + 2**2 + 3**2 + ... + n**2
= (1/3) n**3 + (1/2) n**2 + (1/6) n
= (2 n**3 + 3 n**2 + n)/6

= n * (2 n**2 + 3 n + 1)/6
= n * (n + 1) * (2 n + 1)/6

n = 1: 1*2*3/6 = 1
n = 2: 2*3*5/6 = 5
n = 3: 3*4*7/6 = 14
n = 4: 4*5*9/6 = 30

Confirm:

1 + 2**2 = 1 + 4 = 5
5 + 3**2 = 5 + 9 = 14
14 + 4**2 = 14 + 16 = 30

Formula is known to be of degree 3,and holds for 4 different
values of n.
This proves that the formula holds for
all values of n.

Notice the relationship between the formula for
1 + 2 + 3 + ... + n and
the formula for
1**2 + 2**2 + 3**2 + ... + n**2

1 + 2 + 3 + ... + n
= (1/2) n**2 + (1/2)n

1**2 + 2**2 + 3**2 + ... + n**2
= (1/3) n**3 + (1/2) n**2 + (1/6)n

If we divide the formula for
1 + 2 + 3 + ... + n
by its coefficient of the higest power of n,
we get
n**2 + n

Increase the degree of each term by 1, and
get the new coefficient by dividing current coefficient by
the new degree.

Following this rule, we get

(1/3)n**3 + (1/2)n**2

The coefficient of n is missing.
Find the coefficient of n by pluging n = 1 into the formula.

(1/3) + (1/2) + a1 = 1
a1 = 1/6

1**2 + 2**2 + 3**2 + ... + n**2
= (1/3) n**3 + (1/2) n**2 + (1/6)n

This observation enables us to quickly find the formula for

1**3 + 2**3 + 3**3 + ... + n**3.

Multiplying

(1/3) n**3 + (1/2) n**2 + (1/6)n

by 3, which is the same as dividing by (1/3),

we get,

n**3 + (3/2) n**2 + (1/2) n

Next step:

Increase each degree by 1, and
calculate new coefficient by dividing by new degree.

(1/4) n**4 + (1/2) n**3 + (1/4) n**2

Calculate a1 from

(1/4) + (1/2) + (1/4) + a1 = 1
a1 = 0

1**3 + 2**3 + 3**3 + ... + n**3
= (1/4) n**4 + (1/2) n**3 + (1/4) n**2
= (n**4 + 2 n**3 + n**2)/4
= n**2 (n**2 + 2 n + 1)/4
= n**2 (n+1)**2 / 4
= (n * (n+1)/2 )**2

Confirm:

(1*2/2)**2 = 1
1**3 = 1

(2*3/2)**2 = 9
1**3 + 2**3 = 9

(3*4/2)**2 = 36
9 + 3**3 = 9 + 27 = 36

(4*5/2)**2 = 100
36 + 4**3 = 36 + 64 = 100

(5*6/2)**2 = 225
100 + 5**3 = 100 + 125 = 225

The formula is known to be of degree 4, and we have confirmed
it for 5 different values of n.

Therefore it holds for all values of n.

1**3 + 2**3 + 3**3 + ... + n**3
= (n * (n+1)/2 )**2