Sequences and Induction Proofs
ICS 6D Chapter 8.5-8.6
8.5: More Inductive Proofs
Divisibility Proof by Induction
- Proof that attempts to prove the theorem that a number evenly divides some statement
- Example:
Using induction to prove an assertion about a recurrence relation
- Induction is useful to prove facts about sequence defined by recurrence relations, as you can define each term as an expression of the previous one
- Can be used to prove explicit formulas as shown below:
More examples
- Proof of closed form for an arithmetic sequence:
- Proof of closed form for a geometric sequence:
- Proof of the DeMorgan’s Law applying to multiple sets:
8.6: Strong induction and well-ordering
- The principle of strong induction stipulates that a theorem holds for every value less than or equal to k and attempts to prove that it holds for k+1
- Weak induction instead states that a theorem holds for k and attempts to prove it holds for k+1
- Strong induction is better for use in recurrence relations or any proof where multiple previous terms are necessary to prove the theorem
- Example of a proof by strong induction:
- Often times, a strong induction will require multiple base cases in order to prove that a theorem holds
- Figure of the inductive step with multiple base cases:
- Figure of the inductive step with multiple base cases:
More examples of proof by induction
Well-ordering principle
- The well-ordering principle states that a non-empty subset of non-negative integers will always have a smallest element
- Example of a proof using the principle:
