product van breuken

Opgave - IMO 2013 dag 1 vraag 1

Bewijs dat voor elk paar natuurlijke getallen $k$ en $n$, er $k$ natuurlijke getallen $m_1, m_2, \ldots, m_k$ bestaan (niet noodzakelijk verschillend) zodat $ 1+\frac{2^k-1}{n}=\left(1+\frac{1}{m_1}\right)\left(1+\frac{1}{m_2}\right)\dots\left(1+\frac{1}{m_k}\right). $

Oplossing

$k=1$ maakt het triviaal door $n=m_1$ te kiezen, uiteraard.

We gaan verder met inductie op $k$. Veronderstel dat we $k$ zo'n getallen $m_1,m_2, \dots m_k$ kunnen vinden voor alle $n$.

Veronderstel dat $n=2p+1$ oneven is. De volgende ontbinding geldt $$1+\frac{2^{k+1}-1}{2p+1}=\left(1+\frac{1}{2p+1}\right)\left(1+\frac{2^k-1}{p+1}\right)$$Omdat wegens inductiehypothese die laatste factor al in $k$ termen kan worden ontbonden, zijn we klaar.

Veronderstel dat $n=2p$ even is. Er geldt dat $$1+\frac{2^{k+1}-1}{2p}=\left(1+\frac{1}{2p+2^{k+1}-2}\right)\left(1+\frac{2^k-1}{p}\right)$$
Dit vervolledigt de inductie omdat per hypothese er al $k$ zo'n getallen bestaan voor de rechterterm te ontbinden.