Postulaat van Bertrand
Opgave - PUMA 2010 vraag 4
Pál Erdös bewees in 1932 het zogenaamde postulaat van Bertrand, dit is de volgende bewering:
"voor ieder natuurlijk getal $n>1$ ligt er minstens één priemgetal tussen $n$ en $2n$".
Je mag deze stelling zonder bewijs aannemen. Gebruik nu het postulaat van Bertrand om volgende stelling te bewijzen: "Voor elke $k \in \mathbb{N}$ kan de verzameling $\left\{1,2,\ldots, 2k-1, 2k \right\}$ opgedeeld worden in $k$ paren, waarvan de som telkens een priemgetal is."
Voor $k=4$ krijgen we bijvoorbeeld $\left\{1,6\right\}, \ \left\{2,3\right\},\ \left\{4,7 \right\}$ en $\left\{5,8 \right\}$.
- login om te reageren
Oplossing
De stelling geldt duidelijk voor $k=1$. Stel dat we de stelling reeds bewezen voor alle waarden van $k$ kleiner dan een zekere waarde $n$, dan bewijzen we ze ook voor $k=n$.
Wegens het postulaat van Bertrand is er een priemgetal $p$ zodat $2n < p < 4n$. Wegens de inductiehypothese kan $\left\{1,\ldots,p-2n-1\right\}$ opgedeeld worden zoals gevraagd, waarbij we opmerken dat $p-2n-1$ even is, gezien $p$ een priemgetal is groter dan $2$. Aangevuld met de paren $\left\{p-2n, 2n\right\}, \left\{p-2n+1, 2n-1\right\}, \ldots, \left\{\frac{p-1}{2},\frac{p+1}{2}\right\}$ geeft dit ons de gevraagde opdeling. De stelling volgt nu via volledige inductie.