6
$\begingroup$

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<\dotsb<p_n<\dotsb$. 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!

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Jun 12, 2017 at 3:51
  • $\begingroup$ You're right, I added a sentence to clarify a little bit. $\endgroup$
    – T. Amdeberhan
    Commented Jun 12, 2017 at 4:06
  • 2
    $\begingroup$ Something like this? $\endgroup$
    – Wojowu
    Commented Jun 12, 2017 at 4:21
  • 5
    $\begingroup$ 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). $\endgroup$
    – KConrad
    Commented Jun 12, 2017 at 8:20
  • 1
    $\begingroup$ That is exactly what I meant to say. $\endgroup$
    – T. Amdeberhan
    Commented Jun 12, 2017 at 15:05

4 Answers 4

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Can I ask why you say that $p_{n+1} < 2^{2^n}$? Isn't it true that $p_n < 2^{n+1}$ (because $p_{n+1} < 2 p_n$)? $\endgroup$
    – Zach Teitler
    Commented 2 days ago
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Chebyshev said/And I say it again/There's always a prime/Between $n$ and $2n$. $\endgroup$
    – Gerry Myerson
    Commented Jun 12, 2017 at 23:37
0
$\begingroup$

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:

  1. Vaughan Pratt's certificate of prime numbers uses in Theorem 1 induction on the prime numbers.

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

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .