## Tuesday, March 13, 2007

### Precalculus 9.4 Mathematical Induction

9.4 Mathematical Induction
- a form of mathematical proof

Lets look at the patterns:

S4 = 1 + 2 + 3 + 4 = 10
S6 = 1 + 2 + 3 + 4 + 5 + 6 = 21
S8 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
S10 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

When n = 4, S4 = 10, what are the factors of 10? (2)(5)
When n = 6, S6 = 21, what are the factors of 21? (3)(7)
When n = 8, S8 = 36, what are the factors of 36 that fit the pattern? (4)(9)
When n = 10, S10 = 55, and again, the factors are (5)(11)
therefore we can conclude that Sn = (n/2)(n + 1)

Now lets try another one:
S1 = 1 = 12
S2 = 1 + 3 = 22
S3 = 1 + 3 + 5 = 32
S4 = 1 + 3 + 5 + 7 = 42
S5 = 1 + 3 + 5 + 7 + 9 = 52

Sn = 1 + 3 + 5 + 7 + ... + (2n - 1) = n2

Looking at the pattern we see that 2n - 1 represents consecutive odd integers and n2 represents the sum of the odd integers.

By looking at patterns, sometimes we may come up with a wrong conclusion:
Example:
Take a circle and put a dot on it. How many areas do you have? 1
Now put 2 dots on it and connect the dots. How many areas do you have? 2
Now put 3 total dots on it and connect the dots. How many areas do you have? 4
Now put 4 total dots on it and connect the dots. How many areas do you have? 8
Now put 5 total dots on it and connect the dots. How many areas do you have? 16

Lets look at what we have seen -
1 to 1
2 to 2
3 to 4
4 to 8
5 to 16
so what do you conclude 6 would go to?
Normally we would say 32, but it actually has 30 or 31 depending if the dots are equidistant from each other. So this pattern does not work.

Therefore we have to prove a formula works for all numbers, you have to do the following.

The Principle of Mathematical Induction:

Let Pn be a statement involving the positive integer n. If:
1. P1 is true AND
2. The truth of Pk implies the truth of Pk+1 , for every positive k, then Pn must be true for all positive integers n.

Example:

So Sn = 1 + 3 + 5 + 7 + ... + (2n - 1) = n2
Let n = 1

1. S1 = 2(1) - 1 = 1 and 12 = 1 both are true

2. Then Assume Sk = 1 + 3 + 5 + 7 + ... + (2k - 1) = k2

Then Sk+1 = 1 + 3 + 5 + 7 + ... + (2k - 1) + (2(k + 1) - 1 ) = (k + 1)2

Sk+1 = Sk + (2k + 2 - 1 ) = (k + 1)2

k2 + 2k + 1 = (k + 1)2
(k + 1)2 = (k + 1)2

this is what we had to prove so
Therefore this formula is valid for all positive integer values for n.

Example 2: Find Pk+1 for the given Pk
Pk = (k/2)(5k - 3)
Pk+1 = ((k + 1)/2)(5(k+1) - 3)
= ((k + 1)/2)(5k + 5 - 3)
= ((k + 1)/2)(5k + 2)
= (1/2)(k + 1)(5k + 2)
= (1/2)(5k2 + 7k + 2)

Example 3:
Sn = 1 + 5 + 9 + 13 + ... + (4n - 3) = n (2n - 1)

Let n = 1
S1 = 4(1) - 3 = 1 and (1)(2(1) - 1) = (1)(1) = 1 therefore it is true for both

Assume:
Sk = 1 + 5 + 9 + 13 + ... + (4k - 3) = k (2k - 1)

then Sk+1 = 1 + 5 + 9 + 13 + ... + (4k - 3) + (4(k + 1) - 3) = (k + 1)(2 (k + 1) - 1)
Sk+1 = Sk + (4k + 4 - 3) = (k + 1)(2 k + 2 - 1)
Sk+1 = k (2k - 1) + (4k + 1) = (k + 1)(2 k + 1)
Sk+1 = 2k2 - k + 4k + 1 = (k + 1)(2 k + 1)
Sk+1 = 2k2 + 3k + 1 = (k + 1)(2 k + 1)
Sk+1 =(k + 1)(2 k + 1) = (k + 1)(2 k + 1)

Therefore the formula is valid for all positive integer values of n.

Example 4: 2 (1 + 3 + 32 + 33 + ... + 3n -1) = 3n - 1
Sn = 2 (1 + 3 + 32 + 33 + ... + 3n -1) = 3n - 1

Let n = 1

S1 = 2 (31-1) = 2(30) = 2(1) = 2 and 31 - 1 = 3 - 1 = 2

Assume Sk = 2 (1 + 3 + 32 + 33 + ... + 3k -1) = 3k - 1

Sk+1 = 2 (1 + 3 + 32 + 33 + ... + 3k -1 + 3(k+1)-1 )= 3k+1 - 1
Sk+1 = 2 (1 + 3 + 32 + 33 + ... + 3k -1 + 3k ) = 3k+1 - 1
Sk+1 = 2 (1 + 3 + 32 + 33 + ... + 3k -1 ) + 2(3k ) = 3k+1 - 1
Sk+1 = Sk + 2(3k ) = 3k+1 - 1
Sk+1 = 3k - 1 + 2(3k ) = 3k+1 - 1
Sk+1 = 3(3k ) - 1 = 3k+1 - 1
Sk+1 = 3k+1 - 1 = 3k+1 - 1

We can conclude that this formula holds for all positive integer values of n.

Sums of Powers of Integers - find on
http://www.libraryofmath.com/summation-formulas.html

or in textbook page 652

a0 = 3, a1 = 3, a4 = 15, an = an2 + bn + c

a0 = a(0)2 + b(0) + c = 3 therefore c = 3

a1 = a(1)2 + b(1) + c = 3
= a + b + 3 = 3
= a + b = 0
a = -b

a4 = a(4)2 + b(4) + c = 15
= 16a + 4b + 3 = 15
= 16a + 4b = 12
16(-b) + 4b = 12
-12b = 12
b = -1

a = - b
a = -(-1) = 1

therefore an = n2 - n + 3

To check your answer, use the TI-83 calculator, put the data in:
L1 (0, 1, 4) and L2 (3, 3, 15)
Stat go to Quad Reg L1, L2

this gives you an = n2 - n + 3