This question is seven years old, but since I wanted to ask the same question and provide those examples for induction on prime numbers, I found this question and saw that the first example is missing:
Vaughan Pratt's certificate of prime numbers uses in Theorem 1 induction on the prime numbers.
This is not a proof but an inductive definition of polynomials $f_p(x)$ given by: $f_2(x) := x, f_p(x) := 1+\prod_{q|p-1}f_q(x)^{v_q(p-1)}$ for prime numbers $p>2$.
The proof of the irreducibility of $f_p(x)$ by @JonathanLove where $p$ is a prime and $f_n(x)$ are some unique polynomials indexed by natural numbers $n$, such that $f_{mn}(x) = f_m(x) f_n(x) \forall m,n$, $f_2(x)=x$ and $f_p(x) = 1+f_{p-1}(x)$ for all primes $p>2$. (This definition is due to @WillSawin.) The proof of the irreducibility uses induction on the prime numbers $p$.
Please if someone knows of other examples, it would be nice to share in a comment with a link, since I did not want to open a new question, when one already exists.