Euclid proved that there are infinitely many primes. His proof doesn't exactly use induction but it is close. Rewrite the proof to use proof by induction.

Euclid's proof __Basis__
$\displaystyle S={2,3,5,7,11,13...}$

__Induction Hypothesis__
let $\displaystyle S_k={p_1, p_2, p_3,...,p_k}$ be an exhaustive list of prime numbers where k is an integer greater than 0

__Induction step__
consider $\displaystyle S_k={p_1, p_2, p_3,...,p_k}$has cardinality k

let $\displaystyle S_{k+1}={p_1, p_2, p_3,...,p_k, p_{k+1}}$

then $\displaystyle S_{k+1}={S_k, p_{k+1}}$

Therefore $\displaystyle p_{k+1} \in S_{k+1}$ but $\displaystyle P_{K+1}$ not in $\displaystyle S_k$

__Conclusion__

by the PMI there are infinitely many prime numbers