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

Induction Hypothesis

let be an exhaustive list of prime numbers where k is an integer greater than 0

Induction step

consider has cardinality k

let

then

Therefore but not in

Conclusionby the PMI there are infinitely many prime numbers