Appendix wiskundemarathon #5

Gegroet wiskundige wezens,

in deze post tonen we jullie een nieuwe manier om de vraag van wiskundemarathon #5 op te lossen:
wiskundemarathon deel 5 afbeelding

Eerst introduceren we een nieuwe functie:  \nu_p(n) is gelijk aan het aantal priemfactoren  p in de priemontbinding van  |n| met  n\in\mathbb{Z} .

Er geldt dat \nu_p(n!)=\sum_{k=1}^{\infty}\left\lfloor{\frac{n}{p^k}}\right\rfloor. We gaan deze formule in de volgende post bewijzen. Neem deze nu voorlopig gewoon aan of probeer hem zelf als oefening eens te bewijzen.

Nu zoeken we \nu _{2} \left(\frac{(2n)!}{n!}\right). Dit is gelijk aan \nu _{2} \left((2n)!\right) - \nu _{2} \left(n!\right).
Nu werken we uit:
\nu _{2} \left((2n)!\right) - \nu _{2} \left(n!\right)
 
=\sum_{k=1}^{\infty} \left \lfloor{\frac{2n}{2^k}}\right \rfloor - \sum_{k=1}^{\infty} \left \lfloor{\frac{n}{2^k}}\right \rfloor
 
=\sum_{k=1}^{\infty} \left ( \left \lfloor{\frac{n}{2^{k-1}}}\right \rfloor - \left\lfloor{\frac{n}{2^k}}\right\rfloor\right )
 
=n+\sum_{k=1}^{\infty} \left (\left\lfloor{\frac{n}{2^{k}}}\right \rfloor -\left\lfloor{\frac{n}{2^k}}\right\rfloor\right )=n
 \square
Analoog kunnen we bewijzen dat \nu _{p} \left(\frac{(pn)!}{n!}\right)=n

WiskundeJongen

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.