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

http://www.kermitrose.com/math/NewsLetter/LetterList.html

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[1]

= [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

Now follow the rule:

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