Mathematical Induction

• Strategy for proving P on natural numbers.

  • Induction basis: Show that P(0) holds
  • Induction Hypothesis: assume P(i)
  • Induction Step: prove P(i+1)
  • 
    Proposition: There exist exactly n! permutations of n objects.
    Proof: By Induction

Previous slide

Next slide

Back to first slide

View graphic version