Strong Induction

Definition

• Recall weak induction -- to prove &forall n∈N, P(n), show
  • Base case: P(0)
  • Inductive case: P(i) → P(i+1), for arbitrary i
• Strong induction allows you to assume more in the inductive case --
  • Base case: P(0)
  • Inductive case: (∀ j≤i P(j)) → P(i+1), for arbitrary i
  • Alternate presentation -- don't actually need the base case, because the inductive case subsumes it.

Examples

• Division algorithm: ∀ natural numbers n,m, where m>0, there are natural numbers q,r such that n=mq+r and r<m.
  • for arbitrary positive m, prove ∀n.P(n), where P(n) = "∃q.∃r.(m=mq+r ∧ r<m)"
• Fibonacci number closed form:
  • Start with recursive definition:
    • F₀ = 0
    • F₁ = 1
    • F_n = F_n-2 + F_n-1, if n≥2
  • Prove closed form is F_n = ((aⁿ-(bⁿ)/√5, where
    • a = (1+√5)/2 = golden ratio
    • b = (1-√5)/2 = golden ratio conjugate = silver ratio
  • In the proof, the following lemmas are helpful:
    • a² = 1 + a
    • b² = 1 + b