Home › Archief › Internationale Olympiades › APMO › 2006 › gulden snede

gulden snede

Tags:

Opgave - APMO 2006 vraag 2

Bewijs dat ieder natuurlijk getal geschreven kan worden als een eindige som van verschillende gehele (niet noodzakelijk positieve) machten van de gulden snede $\displaystyle{\frac{1+\sqrt5}2}$.

Oplossing

Ingediend door Peter

Voor $n=1$ is het statement triviaal, stel dat $k$ te schrijven is als een eindige som $v_k$ van verschillende machten. Begin nu van bij de hoogste macht, en pas overal waar er twee machten elkaar opvolgen $a^m+a^{m+1}=a^{m+2}$ toe. Zo kun je zorgen dat er nergens twee opeenvolgende machten gebruikt worden in $v_k$.

Nu construeren we bij wijze van inductie een $v_{k+1}$. Als $a^0$ niet voorkomt in $v_k$ is er geen probleem, als dat wel zo is weten we dat $a^{-1}$ er niet in voorkomt. Als $a^{-2}$ ook niet voorkomt dan geeft $1=a^{-1}+a^{-2}$ toepassen een goeie voorstelling voor $k+1$, als $a^{-2}$ wel voorkomt krijg je een voorstelling waar $a^{-2}$ twee keer op staat. De machten lager dan $a^{-2}$ hebben nog steeds de eigenschap dat er geen twee opeenvolgende enen inkomen, zodat je dit kunt blijven herhalen. Omdat er maar eindig veel enen zijn moet je ooit op een dubbele nul komen en krijg je zo dus ook een goeie voorstelling.