Opgave 4, versie klas 6, finale 2019

De rij van Fibonaccigetallen $F_0, F_1, F_2, \ldots$ wordt gedefinieerd door $F_0 = F_1 = 1$ en $F_{n+2} = F_n + F_{n+1}$ voor alle $n \ge 0$.

De getallenrij $a_0, a_1, a_2, \ldots$ wordt vervolgens gedefinieerd door

$$a_n=\frac{1}{F_nF_{n+2}}$$
voor alle $n \ge 0$.

Bewijs dat voor alle $m \ge 0$ geldt: $a_0 + a_1 + a_2 + … + a_m < 1$.

Daar zit je dan, bij de finale, en dan lees je deze finaleopgave. Er worden veel nieuwe dingen geïntroduceerd, zoals de Fibonaccigetallen, een rij $a_0, a_1, a_2, \ldots$ en een som van een beginstuk van deze rij, die kleiner dan $1$ zou moeten zijn, hoeveel termen je ook neemt. Hoe zou je zoiets kunnen aanpakken?

Misschien heb je wel eens van de Fibonaccigetallen gehoord, maar misschien ook niet. In ieder geval is het een goed idee om te bekijken wat dit voor getallen zijn; misschien kan je dit later gebruiken. Laten we daarom een paar getallen van die rij uitrekenen:

Fibonaccigetal		Berekening		Waarde
$F_0$		Gegeven		$1$
$F_1$		Gegeven		$1$
$F_2$		$F_0 + F_1$		$1 + 1 = 2$
$F_3$		$F_1 + F_2$		$1 + 2 = 3$
$F_4$		$F_2 + F_3$		$2 + 3 = 5$
$F_5$		$F_3 + F_4$		$3 + 5 = 8$
$F_6$		$F_4 + F_5$		$5 + 8 = 13$
$F_7$		$F_5 + F_6$		$8 + 13 = 21$
$\vdots$		$\vdots$		$\vdots$

We hebben deze Fibonaccigetallen nodig om de rij $a_0, a_1, a_2, \ldots $ te maken. We rekenen van deze rij $a_0, a_1, a_2, \ldots$ ook de eerste termen uit:

$a_n$		Berekening		Waarde
$a_0$		$\frac{1}{F_0F_2}$		$\frac{1}{1\cdot2}=\frac{1}{2}$
$a_1$		$\frac{1}{F_1F_3}$		$\frac{1}{1\cdot3}=\frac{1}{3}$
$a_2$		$\frac{1}{F_2F_4}$		$\frac{1}{2\cdot5}=\frac{1}{10}$
$a_3$		$\frac{1}{F_3F_5}$		$\frac{1}{3\cdot8}=\frac{1}{24}$
$a_4$		$\frac{1}{F_4F_6}$		$\frac{1}{5\cdot13}=\frac{1}{65}$

Nog even volhouden

Nadat je dit allemaal hebt uitgerekend, vraag je je misschien af of dit wel allemaal nodig was. Op de finale heb je immers maar een beperkte hoeveelheid tijd en het uitrekenen van deze getallen duurt wel eventjes. Toch is het berekenen van een paar getallen altijd een goed idee, want meestal kom je dan een mooi patroon tegen. Zo’n patroon kun je dan gebruiken om de opgave op te lossen.

Wat de opgave vraagt, is om te bewijzen dat de som van de eerste zoveel termen van de rij $a_0, a_1, a_2, \ldots$ altijd kleiner dan $1$ is, hoeveel we er ook samen nemen. We noemen $S_m$ de som van de eerste $m + 1$ termen, dus $S_m = a_0 + a_1 + a_2 + \ldots + a_m$. Ook nu berekenen we weer de eerste paar termen van deze nieuwe rij:

$$S_0 = a_0 = \frac12\\S_1 = a_0 + a_1 = \frac12 + \frac13 = \frac56.$$

Voor het berekenen van $S_2 = a_0 + a_1  + a_2 = \frac12 +\frac13+\frac{1}{10}$ kunnen we gebruikmaken van de eerdere berekening $S_1 = \frac12 + \frac13 = \frac56$. Zo vinden we:

$$S_2=\frac56+\frac{1}{10}=\frac{25}{30}+\frac{3}{30}=\frac{28}{30}=\frac{14}{15}.$$

Op dezelfde manier zien we ook:

$$S_3=\frac{14}{15}+\frac{1}{24}=\frac{117}{120}=\frac{39}{40}.$$

Zoek het patroon

We zien dat al deze sommen inderdaad kleiner zijn dan $1$. Wat verder opvalt, is dat de teller na vereenvoudiging telkens precies eentje kleiner is dan de bijbehorende noemer. Dat kan geen toeval zijn! Is er misschien nog iets met deze tellers en noemers aan de hand? We kunnen altijd kijken of we iets kunnen vinden, want niets geprobeerd is altijd mis!

We kijken eerst maar eens naar de noemers. Om een leuk patroon te zoeken, is het altijd een goed idee om de priemontbinding van de noemers te bekijken:

$$2 = 2, 6 = 2 \cdot 3, 15 = 3 \cdot 5, 40 = 23 \cdot 5 = 5 \cdot 8$$

Maar wacht eens even, deze cijfers komen ons bekend voor, dit zijn namelijk Fibonaccigetallen! Het lijkt dus dat de noemers altijd het product zijn van twee opeenvolgende Fibonaccigetallen; voor deze eerste vier termen van de rij is het in ieder geval waar. We komen hiermee op het vermoeden dat de som $S_m$ voldoet aan de formule:

$$S_m=\frac{F_{m+1}F_{m+2}-1}{F_{m+1}F_{m+2}}.$$

Als dit vermoeden klopt, dan hebben we meteen de opgave opgelost. Het is dan namelijk duidelijk dat Sm $S_m< 1$ voor alle $m$. Dus nu moeten we deze formule nog bewijzen.

De formule klopt voor $S_0$ tot en met $S_3;$ aan de hand van die waarden hadden we de formule immers opgesteld. Geldt hij ook voor $S_4?$ In plaats van expliciete waarden in te vullen, kijken we of we het kunnen bewijzen door simpelweg de Fibbonaccigetallen te laten staan en te gebruiken wat we al weten. We weten al dat:

$$S_3=\frac{F_4F_5-1}{F_4F_5}$$

en dat $S_4 = S_3 + a_4$. Wanneer we dit invullen, vinden we dat:

$$\begin{array}{rcl}
S_4&=&\frac{F_4F_5-1}{F_4F_5}+\frac{1}{F_4F_6}\\
&=&\frac{F_6(F_4F_5-1)}{F_4F_5F_6}+\frac{F_5}{F_4F_5F_6}\\
&=&\frac{F_4F_5F_6-F_6+F_5}{F_4F_5F_6}
\end{array}.$$

Maar $F_6 = F_4 + F_5$, want dat is gegeven in de opgave. Daarom geldt $F_6 - F_5 = F_4$. Als we dit invullen, zien we:

$$\begin{array}{rcl}
S_4&=&\frac{F_4F_5F_6-F_4}{F_4F_5F_6} \\
&=&\frac{F_5F_6-1}{F_5F_6}
\end{array}.$$

De formule geldt dus ook voor $S_4$. Mooi, maar de volgende vraag is natuurlijk of deze ook voor $S_5$ geldt. En hier is het antwoord verassend genoeg direct “Ja!”: voor $S_5$ kunnen we weer precies dezelfde redenatie gebruiken als we voor $S_4$ deden. Maar dan moet hij op dezelfde manier óók voor $S_6$ gelden, óók voor $S_7$, óók voor $S_8, $ en ga zo maar door. De formule moet dus kloppen voor alle $S_m$ en daarmee hebben we de opgave opgelost.

Terugblik

Bij deze opgave kon je op twee manieren dingen proberen. De eerste was dat je wat termen van de rij $S_m$ ging uitrekenen; de tweede was dat je ging zoeken naar een leuk patroon om dit vervolgens te bewijzen. Met dit leuke patroon konden we de opgave uiteindelijk oplossen. De strategie van een paar waardes “uitproberen” is een methode die bij de Wiskunde Olympiade het proberen van kleine gevallen wordt genoemd. Dit werkt vaak erg goed en is daarom meestal een van de eerste dingen die je doet als je een wiskundeopgave wilt oplossen.