Precalculus 9.4 Mathematical Induction

9.4 Mathematical Induction
- a form of mathematical proof

Lets look at the patterns:

S₄ = 1 + 2 + 3 + 4 = 10
S₆ = 1 + 2 + 3 + 4 + 5 + 6 = 21
S₈ = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
S₁₀ = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

When n = 4, S₄ = 10, what are the factors of 10? (2)(5)
When n = 6, S₆ = 21, what are the factors of 21? (3)(7)
When n = 8, S₈ = 36, what are the factors of 36 that fit the pattern? (4)(9)
When n = 10, S₁₀ = 55, and again, the factors are (5)(11)
therefore we can conclude that S_n = (n/2)(n + 1)

Now lets try another one:
S₁ = 1 = 1²
S₂ = 1 + 3 = 2²
S₃ = 1 + 3 + 5 = 3²
S₄ = 1 + 3 + 5 + 7 = 4²
S₅ = 1 + 3 + 5 + 7 + 9 = 5²

S_n = 1 + 3 + 5 + 7 + ... + (2n - 1) = n²

Looking at the pattern we see that 2n - 1 represents consecutive odd integers and n² 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 P_n be a statement involving the positive integer n. If:
1. P₁ is true AND
2. The truth of P_k implies the truth of P_k+1 , for every positive k, then P_n must be true for all positive integers n.

Example:

So S_n = 1 + 3 + 5 + 7 + ... + (2n - 1) = n²
Let n = 1

1. S₁ = 2(1) - 1 = 1 and 1² = 1 both are true

2. Then Assume S_k = 1 + 3 + 5 + 7 + ... + (2k - 1) = k²

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

S_k+1 = S_k + (2k + 2 - 1 ) = (k + 1)²

k² + 2k + 1 = (k + 1)²
(k + 1)² = (k + 1)²

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

Example 2: Find P_k+1 for the given P_k
P_k = (k/2)(5k - 3)
P_k+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)(5k² + 7k + 2)

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

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

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

then S_k+1 = 1 + 5 + 9 + 13 + ... + (4k - 3) + (4(k + 1) - 3) = (k + 1)(2 (k + 1) - 1)
S_k+1 = S_k + (4k + 4 - 3) = (k + 1)(2 k + 2 - 1)
S_k+1 = k (2k - 1) + (4k + 1) = (k + 1)(2 k + 1)
S_k+1 = 2k² - k + 4k + 1 = (k + 1)(2 k + 1)
S_k+1 = 2k² + 3k + 1 = (k + 1)(2 k + 1)
S_k+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 + 3² + 3³ + ... + 3^{n -1}) = 3ⁿ - 1
S_n = 2 (1 + 3 + 3² + 3³ + ... + 3^{n -1}) = 3ⁿ - 1

Let n = 1

S₁ = 2 (3^1-1) = 2(3⁰) = 2(1) = 2 and 3¹ - 1 = 3 - 1 = 2

Assume S_k = 2 (1 + 3 + 3² + 3³ + ... + 3^{k -1}) = 3^k - 1

S_k+1 = 2 (1 + 3 + 3² + 3³ + ... + 3^{k -1} + 3^(k+1)-1 )= 3^k+1 - 1
S_k+1 = 2 (1 + 3 + 3² + 3³ + ... + 3^{k -1} + 3^k ) = 3^k+1 - 1
S_k+1 = 2 (1 + 3 + 3² + 3³ + ... + 3^{k -1} ) + 2(3^k ) = 3^k+1 - 1
S_k+1 = S_k + 2(3^k ) = 3^k+1 - 1
S_k+1 = 3^k - 1 + 2(3^k ) = 3^k+1 - 1
S_k+1 = 3(3^k ) - 1 = 3^k+1 - 1
S_k+1 = 3^k+1 - 1 = 3^k+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

Finding a quadratic model

a₀ = 3, a₁ = 3, a₄ = 15, a_n = an² + bn + c

a₀ = a(0)² + b(0) + c = 3 therefore c = 3

a₁ = a(1)² + b(1) + c = 3
= a + b + 3 = 3
= a + b = 0
a = -b

a₄ = a(4)² + 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 a_n = n² - 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 = n² - n + 3
same answer!