In matematica, il postulato di Bertrand afferma che per ogni n ≥ 2 esiste un primo p tale che n < p < 2n. La prima dimostrazione fu data da Pafnuty Chebyshev; successivamente, anche Srinivasa Ramanujan e Paul Erdős ne fornirono una dimostrazione.
Se
è una successione di reali tali che
, allora
e anche
Siano
dove
è sempre un numero primo, ora
e noto (vedi approssimazione di Stirling) che
quindi
e
adesso in base a quanto scritto nei preliminari
dalla (1) si ricava
e sostituendo nella (2) si ottiene
dove l'ultima disuguaglianza vale per tutte le
.
ora
e sostituendo nella (3) tenendo conto che
e infine
il secondo membro per
è sempre maggiore di 1 e poiché il postulato di Bertrand è verificato per tutti gli
la dimostrazione è conclusa.
Indichiamo l'insieme dei numeri primi con
e definiamo:
![{\displaystyle \theta (x)=\sum _{p\in \mathbb {P} ;p\leq x}\ln(p)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0628f03d30ae8c33d667283088b1aa6c904802d)
![{\displaystyle \theta (n)<n\cdot \ln(4)\qquad {\mbox{per tutti gli interi }}n\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d48e5da909665029d447e77e0e4c1c6bb946c9b3)
![{\displaystyle \theta (1)=0<1\cdot \ln(4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cfa53b4a361f1941138e911c2683e90cadeb78c)
![{\displaystyle \theta (2)=\ln(2)<2\cdot \ln(4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01eededfc3f6770723d13775ee8361095a30dc65)
(per induzione)
- n > 2 ed n è dispari. Sia n = 2m + 1 con m > 0:
![{\displaystyle 4^{m}={\frac {(1+1)^{2m+1}}{2}}={\frac {\sum _{k=0}^{2m+1}{2m+1 \choose k}}{2}}={\frac {x+{2m+1 \choose m}+{2m+1 \choose m+1}}{2}}\geq {2m+1 \choose m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41c8ba02b22fbcaf31ad14030ea5b89364dec741)
- Ogni primo p con
divide
dando:
![{\displaystyle \theta (2m+1)-\theta (m+1)\leq \ln(4^{m})=m\cdot \ln(4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae415b3761f22fec5305189fc4cb56893006ea96)
- Per ipotesi induttiva
, da cui segue:
![{\displaystyle \theta (n)=\theta (2m+1)<(2m+1)\cdot \ln(4)=n\cdot \ln(4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9bb641c2eef363e92bbe491c178baa4d1ecac1d)
- CVD
Detto ciò possiamo passare alla dimostrazione del postulato di Bertrand.
Supponiamo per assurdo che ci sia un controesempio: un intero n ≥ 2 tale che non ci sia nessun numero primo p tale che n < p < 2n.
Se 2 ≤ n < 2048, allora uno dei numeri primi 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 e 2503 (ognuno minore del doppio del precedente), che possiamo chiamare p, soddisferà n < p < 2n.
Dunque n ≥ 2048.
![{\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{2n \choose k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/639d6641d8f4c4e64ad6b046c36724f40cf210d0)
Poiché
è il più grande termine nella somma, abbiamo:
![{\displaystyle {\frac {4^{n}}{2n+1}}\leq {2n \choose n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f39cbcf94e80c630bcd9a55c9060e5c4fabb5774)
Definiamo
come il più grande numero x, tale che
divide
.
Poiché n! ha
fattori di p, otteniamo:
![{\displaystyle R(p,n)=\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/70c7e83f1eeba3fba7be0ecf9d35218ba3c1970b)
Dal momento che ogni termine
può essere o uguale a 0
oppure ad 1
e tutti i termini con
sono 0, otteniamo:
![{\displaystyle R(p,n)\leq \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/99a416eb13d0b38284c4ec79b88f80dd24ca7ecb)
Per
abbiamo
o
.
non ha fattori primi p tali che:
- 2n < p, poiché 2n è il fattore più grande.
, a causa della nostra assunzione iniziale.
, perché
(dato che
) che implica
.
Ogni fattore primo di
è dunque minore o uguale a
.
ha al massimo un fattore di ogni primo
. Poiché
, il prodotto di
su tutti gli altri primi vale al massimo
. Dal momento che
è il prodotto di
su tutti i primi p, otteniamo:
![{\displaystyle {\frac {4^{n}}{2n+1}}\leq {2n \choose n}\leq (2n)^{\sqrt {2n}}\prod _{p\in \mathbb {P} }^{\frac {2n}{3}}p=(2n)^{\sqrt {2n}}e^{\theta ({\frac {2n}{3}})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c40d7b84e1ba46d0c7e23309826ecf84fda6ee54)
Usando il lemma
:
![{\displaystyle {\frac {4^{n}}{2n+1}}\leq (2n)^{\sqrt {2n}}4^{\frac {2n}{3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95715b43b878d63eb4069688fdfb809e0baf6c87)
Dato che abbiamo
:
![{\displaystyle 4^{\frac {n}{3}}\leq (2n)^{2+{\sqrt {2n}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79494c261ce58272b92609ed92f2ce4045517aef)
Inoltre
(in quanto
):
![{\displaystyle 4^{\frac {n}{3}}\leq (2n)^{{\frac {4}{3}}{\sqrt {2n}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b44ecf39c02198e153cfe53f95da6d02595ab895)
Passando ai logaritmi:
![{\displaystyle {\sqrt {2n}}\ln(2)\leq 4\cdot \ln(2n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2798e272f9b9e8241df4f8dfee14bd7c2cd529da)
Sostituendo 22t al posto di 2n:
![{\displaystyle {\frac {2^{t}}{t}}\leq 8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b94b64e5a9ce42762c8a8741f037849df4bb309c)
Questo implica t<6 e la contraddizione:
![{\displaystyle n={\frac {2^{2t}}{2}}<{\frac {2^{2\cdot 6}}{2}}=2048}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7bd84e607418223c070e1f46395babf3540c5ff7)
Dunque non è possibile nessun controesempio al postulato.
- CVD