© h.hofstede (h.hofstede@hogeland.nl)

Hoe Erdös het postulaat van Bertrand bewees.
       
Als je alle binomiaalcoëfficiënten op een rij van de driehoek van Pascal bij elkaar optelt dan geeft dat  2n , immers je krijgt ze als je (1 + 1)n uit gaat schrijven.
Dus:

De grootste van al die (2n + 1) termen is de middelste, dus  als je ze allemaal vervangt door de middelste krijg je een som die groter is dan 4n:

       
Bekijk nu  np(n!);
Dat is het aantal keer dat priemgetal p voorkomt in de priemfactorontbinding van  n!

Met ⌊x⌋  bedoel ik vanaf nu het getal x naar beneden afgerond; dus alleen het gehele deel van x.
⌊n/p⌋ is het aantal veelvouden van p dat niet groter is dan n en elk van die veelvouden zal bijdrage 1 aan np(n!) leveren, want in al die veelvouden zit p minstens één keer.
⌊n/p2⌋ is het aantal veelvouden van p2 dat niet groter is dan n en elk van die veelvouden zal nog een extra bijdrage 1 aan np(n!) leveren, want in al die veelvouden zit p minstens twee keer (dus één keer extra)
⌊n/p3⌋  is het aantal veelvouden van p3 dat niet groter is dan n en elk van die veelvouden zal nog een extra bijdrage 1 aan np(n!) leveren.

voorbeeld:
100! = 100 • 99 • 98 • ... • 1
⌊100/3⌋ = 33 dus het getal 3 zal 33 keer in de 100! voorkomen   (namelijk  in 3, 6, 9, ..., 96, 99)
⌊100/9⌋ = 11 dus het getal 32  zal 11 keer in 100! voorkomen  (namelijk in 9, 18, 27, ..., 90, 99)
⌊100/27⌋ = 3  dus het getal 33 zal 3 keer in 100! voorkomen (namelijk in 27, 54 en 81)
34  wordt groter dan 100
in totaal komt het priemgetal 3 dus  33 + 11 + 3 = 47 keer in de priemfactorontbinding van 100!  voorkomen.

In formulevorm:
       

(Je kunt k rustig tot oneindig laten lopen, want vanaf pk > n worden al die termen toch nul).
       
Je kunt heel eenvoudig beredeneren dat np(ab) = np(a) + np(b)  en  ook dat    np(a/b) = np(a) - np(b).

Hulpstelling 1.

Er geldt echter altijd  dat  0 ≤  ⌊2x⌋ - 2⌊x⌋ ≤ 1  (ga dat zelf maar even snel na, het was opgave 1 uit deze les)
Dat stuk daar tussen haakjes rechts is dus altijd kleiner of gelijk aan 1.
Dus die hele som is altijd kleiner of gelijk aan het aantal termen dat niet nul is,
Neem aan dat dat de temen k = 1 t.m. r zijn, dus dat  pr < 2n < pr + 1 
Dan is die som rechts kleiner of gelijk aan r
Conclusie:

  
       
Neem nu de logaritme beide kanten:

       
Hulpstelling 2.
Voor alle n  ≥ 2  geldt:

Het product van alle priemgetallen tot en met n is kleiner of gelijk aan 4n  
       
Bewijs  
  Met volledige inductie:
Voor n = 2 klopt de stelling van  2 ≤ 42
Stel dat de stelling tot en met een bepaalde n - 1 voor alle getallen klopt.

Voor even n is het makkelijk in te zien dat de stelling dan ook klopt, immers n is dan nooit een priemgetal, dus er komt niets extra's bij het product vergeleken met n - 1, en 4n - 1 ≤ 4n

Voor oneven n is het wat lastiger.  Neem n = 2m + 1.
Splits het product van al die priemgetallen in twee delen:
Deel 1:   p ≤ m + 1   volgens de inductie-aanname is dit product kleiner dan 4m + 1
Deel 2:   m + 2 ≤  p  ≤  2m + 1
 

  (dat kun je vrij eenvoudig zien door  de faculteiten uit te schrijven, en dat staat hier)
 

  Als je alle combinaties optelt komt er 2n uit, dus dat geeft
 

  Maar die twee roden daar in het midden zijn gelijk.
Den hele som is  22m + 1  = 2 • 22m   dus elk is hoogstens gelijk aan 22m .
     
Deel 1 en Deel 2 samen geeft nu dat het hele product kleiner of gelijk aan   4m + 1 • 22m  is, en dat is 42m + 1 = 4n
q.e.d.  
       
Met deze twee hulpstelling achter de hand gaan we terug naar het postulaat van Bertrand.

Stel dat er voor een bepaalde n géén priemgetal bestaat zodat  n < p ≤  2n.............

Die splitsen we in twee delen:  priemfactoren die kleiner of gelijk zijn aan  √(2n)  en priemfactoren die groter zijn dan √(2n).
       
1.  priemfactoren kleiner of gelijk aan  √(2n)
  Daarvan zijn er maximaal √(2n)    (duh)
Elk van die priemfactoren  is hoogstens gelijk aan 2n    (hulpstelling 1)
Samen met elkaar vermenigvuldigd  is dat maximaal  (2n)√(2n)
       
2.  priemfactoren groter dan √(2n).
  Die komen allemaal maar 1 keer voor, en ze zijn allemaal kleiner dan 2/3n
Waarom? 
Nou, een priemfactor van n is hoogstens gelijk aan √n, en 2/3n is groter dan √n als  n ≥ 3 (Ga dat zelf maar na)

Dus die priemfactoren zijn samen met elkaar vermenigvuldigd maximaal gelijk aan  42n/3  (hulpstelling 2)
       
Beide soorten samengenomen geeft:

samen met (1) geeft dat:

       
Bedenk goed wat we nu hebben ontdekt:  ALS en geen priemgetal tussen  n en 2n ligt, dan moet deze laatste ongelijkheid gelden.
Maar als n naar oneindig gaat, dan wordt de linkerkant zeker groter dan de rechterkant. De linkerkant groeit ongeveer als 4n en de rechterkant als 42n/3 .  Dus vanaf bepaalde n kan deze ongelijkheid zeker niet gelden.
Het blijkt (rekenprogramma Mathematica) dat voor n > 467 dat deze ongelijkheid niet meer geldt. Dus hebben we nu bewezen dat voor n > 467 er zeker altijd een priemgetal tussen n en 2n zal liggen.
       
Nu nog even n ≤ 467

Nou, die kun je makkeljik allemaal gewoon "met de hand"  (met een computer)  nalopen.
Echte slimmeriken (of luiaards) kunnen dat sneller doen door te zien dat:

2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631

een serie priemgetallen is waarvan elk getal minder is dan tweemaal de vorige. Dus dan bevat elk interval  {n +1, 2n} altijd één van deze elf priemgetallen.

Daarmee is het postulaat van Bertrand bewezen.
       

       

© h.hofstede (h.hofstede@hogeland.nl)