An example of a proof by the second principle of mathematical induction
Show that if n?2, then n can be written as a product of primes.
Basis step: 2 can be written as a product of primes - it is the product
Inductive step: Assume that 2,3,…,n can be written as products of
primes. Show that then n+1 can also be written as a product of primes.
Indeed: If n+1 is prime, we are done. Otherwise, n+1 is the product
of 2 integers a and b, both between 2 and n.
By the induction hypothesis, a and b have prime factorizations. Then
the product of those factorizations would be a prime factorization of n+1.