# 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!

• Fundamental theorem of arithmetic? Various statements on finite groups? Euclid's proof rearranged? What form of induction do you want? Gerhard "Can You Be More Specific?" Paseman, 2017.06.11. – Gerhard Paseman Jun 12 '17 at 3:51
• You're right, I added a sentence to clarify a little bit. – T. Amdeberhan Jun 12 '17 at 4:06
• Something like this? – Wojowu Jun 12 '17 at 4:21
• What is the motivation for this question: idle curiosity? In any case, the first proof of quadratic reciprocity by Gauss was an induction on the primes. Tate used that "ugly" proof in his calculation of $K_2(\mathbf Q)$, which is also an induction on primes (see Rosenberg's textbook on $K$-theory). – KConrad Jun 12 '17 at 8:20
• That is exactly what I meant to say. – T. Amdeberhan Jun 12 '17 at 15:05

Two examples which come to my mind are:

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

2. 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]$.

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.

• Chebyshev said/And I say it again/There's always a prime/Between $n$ and $2n$. – Gerry Myerson Jun 12 '17 at 23:37

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:

• 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.

• I don't imagine this is the kind of answer the OP was looking for. – Todd Trimble Jun 12 '17 at 13:06
• My point is that the question is rather odd, since one uses induction to prove basically everything. What kind of answer could one want? To give any particular example of a proof using primes and induction would be silly, like one is missing the main fact. – Joel David Hamkins Jun 12 '17 at 13:36
• That may very well be, but nevertheless, I imagine T. Amdeberhan may be looking for something like what appears in KConrad's comment. Actually, some more clarification may be needed here. – Todd Trimble Jun 12 '17 at 13:39

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$.