] >
Laat een verzameling zijn. Een rij in kan gegeven zijn door de termen rechtstreeks te definiëren. Bijvoorbeeld: . De rij is dan de rij van de kwadraten. Ook kun je een rij op recursieve wijze vastleggen: wordt dan gedefinieerd in termen van .
Een speciaal geval is de zogeheten simpele recursie. Daarbij wordt de volgende term geheel bepaald door de laatste term, behalve in het begin natuurlijk, want dan is er nog geen laatste term. Een rij in een verzameling ligt dan vast door het geven van de beginterm en een transformatie van :
4.8 Voorbeelden. De in paragraaf 2.4 gegeven definities van optellen, vermenigvuldigen en machtsverheffen van natuurlijke getallen zijn voorbeelden van simpele recursie.
4.9 Voorbeeld. Op bladzijde § zagen we dat de Toren van Hanoi oplosbaar is voor ieder aantal schijven. We zagen hoe uit een oplossing voor schijven een oplossing voor schijven kan worden gemaakt. Daarbij wordt de grootste schijf eenmaal verplaatst en daarmee is in te zien dat zo zelfs het kleinste aantal zetten voor een oplossing wordt gevonden. Geven we met het aantal zetten voor de oplossing bij schijven aan, dan krijgen we voor de rij :
Zo is de rij op recursieve wijze vastgelegd. In Hoofdstuk 1 konden we aan de grafen van de Toren van Hanoi wel zien dat er bij schijven voor de oplossing zetten nodig zijn. Is ook zonder deze context in te zien dat de rij met dezelfde is als de rij ? De rij is vastgelegd door een recursieve betrekking. Als de rij daar ook aan voldoet, dan is die rij dus dezelfde als . Daarvoor moet worden nagegaan dat
Dat is natuurlijk eenvoudig: en voor alle .
Later zullen we nog vaak ( faculteit) gebruiken. Een recursieve definitie is eenvoudig te geven:
Dus bijvoorbeeld . Minder formeel kun je ook schrijven
Het is geen simpele recursie: de -de term wordt niet bepaald door de voorgaande, maar ook door het rangnummer van de term. Toch is de definitie wel met een simpele recursie te geven. Gebruik dan niet een transformatie van , maar een transformatie van :
Er is dan een rij in met
De rij is dan de rij .
Fibonacci (Pisa(?) 1170 – Pisa(?) 1250)
4.11 Voorbeeld. De rij is gedefinieerd door:
Dus: een volgende term in de rij is de som van de laatste twee termen; zijn er geen laatste twee termen, dan is er een aparte beschrijving. De rij wordt dus gevormd door met en te beginnen en vervolgens steeds de som van de laatste twee termen te nemen. Het is makkelijk om de termen één voor één te berekenen:
: | |||||||||||||
: | |||||||||||||
Het getal noemt men het -de Fibonaccigetal. De rij is ook met een simpele recursie te maken door de transformatie van te nemen en als startwaarde :
Dan geldt dat voor alle . De rij van Fibonaccigetallen treedt op veel plaatsen op en heeft bovendien intrigerende eigenschappen. Er is zelfs een tijdschrift, The Fibonacci Quarterly, dat geheel gewijd is aan de Fibonaccigetallen.