in wiskundemarathon

Getaltheorie met inductie (wiskundemarathon #5)

Hallo wiskundefreaks,

in korte vijfde deel van de wiskundemarathon los ik één opgave op van getaltheorie (ik vond deze vraag in de bundel getaltheorie van de Nederlandse training voor de International Mathematical Olympiad). De opgave luidt: wiskundemarathon deel 5 afbeelding
We definiëren de functie  p(n) als het aantal priemfactoren 2 in  (n+1)(n+2)...(2n) . Eerst observeren we enkele gevallen:
 p(1)=1
 p(2)=2
 p(5)=5
 p(13)=13

We krijgen het vermoeden dat \forall n\in \mathbb{N}: p(n)=n .
Nu gaan we dit bewijzen met onze welbekende techniek: volledige inductie (zie wiskundemarathon #4).

Inductiebasis: Voor  n=0 is het duidelijk dat  p(0)=0 .
Inductiestap: We stellen dat  (n+1)(n+2)...(2n)=2^n \cdot k met  k=2m+1  (m \in \mathbb{N}). Dit is gelijk aan stellen dat  p(n)=n .

Nu moeten we bewijzen dat  p(n+1)=n+1 :

 (n+2)(n+3)...(2n)(2n+1)(2n+2)
= (n+2)(n+3)...(2n)(2n+1)\cdot 2 \cdot (n+1)
 = 2\cdot 2^n\cdot k\cdot (2n+1)
 = 2^{n+1}\cdot k\cdot (2n+1)
\Rightarrow p(n+1)=n+1
 \square

WiskundeJongen

PS: Trouwe lezers zullen opgemerkt hebben dat ik mijn archaïsh “q.e.d.” heb ingewisseld door het modernere  \square om het einde van een bewijs aan te duiden. Dit symbool is indertijd voorgesteld door Paul Halmos.

Leave a Reply