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

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

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

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

Prove that n! is > 2^{n} for all n >= 4.
Proof: Notice that 4 ! = 24 > 16 = 2^{4}.
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^{n} for all n >= 4.