Induction

Sequences

2, 4, 6, 8, 10, …
1, 2, 4, 8, 16, …
1/2, 2/3, 3/4, 4/5, …

A sequence is an ordered list of terms.

2, 4, 6, 8, …
1st, 2nd, 3rd, 4th, …
12, 22, 32, 42, …

A general (or explicit) formula for the nth term.

a_n = 2n

Notation

I want to write the shorthand version of: 1/2 + 2/3 + 3/4 + 4/5 + … see note sheet #9q34

Principle of Mathematical Induction

To proove statements of the form: “For all integers n >= 1, P(n).”

If 1) P(1) is true
and 2) the statement
“for all integers k >= 1, P(k) => P(k+1)”
is true

The metaphore for this is a ladder. If I can get the next rung, then I can get the the rung after that one.

To use the principle of Mathematical Induction

Proove the statement is true for n=1 (base step or base case).
Let k >= 1 be some arbitrary integer.
Assume P(k). This is called the inductive hypothesis.
Proove P(k+1). This is called the inductive step.
Therefor, P(n) for all n >= 1.

Continued on paper notes: #zrepryt

Statement of Mathematical Induction

Let a be some fixed non-negative integer. Let P(n) be a statement define d for all integers n >= a. If P(a) is true …

Conjecture: Using 3 cent coins and 5 cent coins, any change amount n >= 8 can be made.

8 = 3 + 5 9 = 3 + 3 + 3 10 = 5 + 5 11 = 3 + 3 + 5 12 = 3 + 3 + 3

Case 1 = no 5 cent coins Case 2 = at least oe 5 cent coin

Result: For all change amounts n >= 8, you can make n cents using only 3 cent coins and 5 cent coins.

Proof by induction: Observe that 8 = 3 + 5, prooving the base case. Let k >= 8 be any arbitrary integer. Assume that k cents can be made by using only 3 cent and 5 cent coins. We claim that (k + 1) cents can be made using only 3 cent coins and at least one 5 cent coin. Case 1: at lest one 5 cent coin is used to make k cents. Trade one 5 cent coin for each 3 cent coins. The total would then be k - 5 + 2 * 3 = k + 1 cents. Case 2: no 5 cent coins are used in making k cent coins. Since k >= 8 and only 3 cent coins are used, we have at least three 3 cent coins. Trade three 3 cent coins or two 5 cent coins. The total would then be k - 3 * 3 + 2 * 5 = k + 1. Therefore, by the Principle of Mathematical Induction, any amount n >= 8 can be made.

Proof by Mathematical Induction using Factorials 1 * 1! + 2 * 2! + 3 * 3! .. + n * n! = (n + 1)! = 1 for all n >= 1. Proof: Observe that when n = 1, 1 * 1! = 1 == 2! - 1 = (1 + 1)! - 1 prooving the base case. Let k >= 1 be any arbitrary integer. Assume 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1)! - 1. We want to show that 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1) * (k + 1)! = (k + 2)! - 1 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1) * (k + 1)! = (k + 1)! - 1 + (k + 1) * (k + 1)! = (k + 1)! * (1 + k + 1) - 1 = (k + 1)! * (k + 2) - 1 = (k + 2)! - 1 By the P.M.I., Eⁿ_i=1 i * i = (n + 1)! - 1 for all n >= 1. The statement above should be formatted in the inductive notation format which wont work in markdown.

Prove that n < 2ⁿ for all n >= 1. Proof: Observe that 1 < 2¹, prooving the base case. Let k >= 1 be any arbitrary integer. Assume k < 2^{k</sub>.
We want to show that k + 1 < 2^k+1
Observe that 2^k+1 = 2^k * 2 > k * 2 = 2k = k + k >= k + 1
By the P.M.I., n < 2ⁿ for all n >= 1.}

Prove that n! is > 2ⁿ for all n >= 4. Proof: Notice that 4 ! = 24 > 16 = 2⁴. Let k >= 4 be any arbitrary integer. Assume k! > 2^k. We want to show (k + 1)! > 2^k+1 Observe (k + 1)! = (k + 1) * k! > (k + 1) * 2^k >= 5 * 2 > 2 * 2^k = 2^k+1. By P.M.I. n! > 2ⁿ for all n >= 4.