Last updated April 10, 2022

Status: Tags: #archivedCards/macm101/induction Links: Discrete Mathematics

Mathematical Induction

Principles

Well Ordering Principle

Definition

? To prove a statement that asserts some property P(n) is true for all positive integers n

• if p(k) is true then p(k+1) is true
• Symbolically
  • (P(1) ∧ ∀k (P(k) → P(k + 1))) → ∀n P(n)

Steps

?

• Two steps:
  • Verify base case (usually P(1)) is true
  • Assume n=k, k>=1
    • Rewrite formula in terms of k
  • Rewrite original formula with addition of k+1 case on left side
    • On right side replace n with k+1
  • Inductive step: Show that conditional statement P(k) → P(k + 1) is true for all positive integers k
    • Replace the solved left part using the base case, them mix like terms to make both sides equal

Proving

?

• P(n) denotes statement
  • Prove it is true
• Suppose P(k) is true, that is statement but any var
  • Prove P(k+1)

Types

• Mathematical Summation
• Strong Induction
• Structural Induction

Examples

Give a recursive definition of f(n) = $2^n$ ? Basis step: f(0) = 1 Inductive step: f(k + 1) = 2 ⋅ f(k).

Factorial induction ?

• f(n) = n!
• Basis step: 0! = 1
• Inductive step: (k + 1)! = k! ⋅ (k + 1)

Trimonio can fill square missing a tile ?

• Prove the first case of a 2x2 grid
• For a larger case, place the trimonio so all squares have a covered tile
  • Since last step was proved, it is possible

Backlinks

1

list from Mathematical Induction AND !outgoing(Mathematical Induction)

References:

Created:: 2021-10-28 09:56