Mathematical induction vis-a-vis primes One of the most used proof-techniques is mathematical induction, and one of the oldest subjects is the study of prime numbers. Thanks to Euclid, we can consider the primes as a infinite monotone sequence $2=p_1<p_2<\cdots<p_n<\cdots$. But, knowing the prime $p_n$ does not tell us the exact location of the next.
My inquiry here is this:

Question. What theorems/results do you know where induction is done on a formula/statement involving primes? In the sense that you move from one prime to the next, inductively. Please include reference.

UPDATE. It seems that the question has confused more people that I thought it would. For this reason, I don't mind if the editors decide to close it. Thanks to all who put effort!
 A: Two examples which come to my mind are:


*

*$(\forall n \in \mathbb{N})$ $\, \,$ $p_{n+1}<2^{2^{n}}$.

*For every $n \in \mathbb{N}_{\geq 12}$, $\,$ $p_{n}>3n$.
By the way, Erdös's proof of Bertrand's postulate is not by induction (it depends on some results which can be proven via mathematical induction, but that's a different thing): what Erdös actually does in his proof is compare lower bounds for the central binomial coefficients $\binom{2n}{n}$ with some upper ones which he obtains by means of Legendre's formula, the Erdös-Kalmár inequality, and the assumption that there are no primes in $(n,2n]$.
A: 
A comment (rather than an Answer).

(I have elementary examples of an induction $n\rightarrow n+1$ over all integers but the theorem $T(n)$ is about the set of primes $\le n$).
@მამუკა ჯიბლაძე, the simplest and easiest example would be a slight strengthening of the Euclid Theorem:
THEOREM (Euclid++) For every natural number (i.e. positive integer)
$\ n,\ $ the product of primes $\le\ n\ $ is $\ \ge\ n$.
A: I believe Bertrand's postulate can be thought of in this way: for each prime $p$, there is a prime in the range $(p,2p]$. This was the subject of Erdös's first paper BTW. 
A: From the point of view of the logical development of number theory as a mathematical theory, the principle of induction is used to prove essentially every nontrivial elementary statement in number theory. Basically, you can hardly get started without induction.
For example, if one defines the natural numbers in Peano's manner, as the unique inductive structure $\langle \mathbb{N},S,0\rangle$, where $S$ is the injective successor function and so on, then one typically defines addition as repeated application of the successor: $x+0=x$, $x+S(y)=S(x+y)$, and multiplication as repeated addition: $x\cdot 0=0$, $x\cdot S(y)=x\cdot y+x$. In this development, one uses induction to prove that:


*

*addition is commutative

*multiplication is commutive

*distributivity of multiplication over addition

*every fraction can be placed in lowest terms

*Euclidean algorithm

*$\sqrt{2}$ is irrational

*every number is a unique product of primes


And on and on with all the basic facts. 
If instead of the second-order Peano characterization of the natural numbers, one works rather in the first-order theory PA, then the induction axiom is the central axiom, used in essentially every nontrival argument, since the theory stated without any induction axiom is extremely weak and is not able to prove much
Meanwhile, the logicians study the theories that arise when one restricts the induction principle. For example, PA proves the consistency of $\Sigma_n$-induction, for any particular finite $n$, and one can use this to show that PA is not finitely axiomatizable, if consistent, for then it would prove its own consistency, contrary to the incompleteness theorem.   
