© h.hofstede (h.hofstede@hogeland.nl)
Recursieformules.
Zin in een spelletje?
Het puzzeltje hiernaast heet de `Torens van Hanoi`.
Het bestaat uit drie houten pinnen met een aantal (in de figuur 8) schijven met een gat in het midden die op de pinnen gelegd kunnen worden. De schijven variëren van groot naar klein. De bedoeling van de puzzel is de hele toren van pin1  naar pin 3 te verplaatsen. Dat moet schijf voor schijf gebeuren, en daarbij is de enige regel: "Er mag nooit een grotere schijf bovenop een kleinere liggen" .

De vraag is: in hoeveel zetten (verplaatsingen van één schijf) kun je dat?
Oefen het eerst een paar keer met steeds meer schijven; in deze applet moet je de schijven naar de rechterpin verplaatsen:
Als het goed is kun je zo'n soort tabel gaan invullen:
aantal schijven 1 2 3 4 5
minimaal aantal zetten 1 3 7 15 ...
Laten we er wat wiskundige notatie in aanbrengen.
Noem u(n) het minimaal aantal benodigde zetten om een toren van n schijven te verplaatsen.
Dus in de tabel zie je dat u(1) = 1 en  u(4) = 15.
De grote wiskunde-prijsvraag is nu natuurlijk:
Kunnen we een formule maken?

En dat kan, maar het wordt wel een aparte formule. De redenering om de formule te vinden is als volgt:
Stel dat ik weet hoe groot un-1 is.
Dan weet ik óók hoe groot un is, kijk maar:
• Ik heb dus een toren met n schijven die van de linker naar de rechterpin moet worden verplaatst
• Verplaats eerst alle schijven behalve de onderste van de linker naar de middelste pin. Dat kost un-1 zetten.
• Verplaats nu de onderste schijf van links naar rechts:  kost 1 zet
• Verplaats tenslotte de toren van n schijven van de middelste naar de rechterpin. Kost weer un-1 zetten
Samen kost dat dus    un-1 + 1 + un-1  = 2un-1 + 1  zetten.
Conclusie: 

un = 2 • un-1 + 1
Daar is onze formule al. Maar het is wel een ander soort formule dan we tot nu toe gewend zijn.
We waren altijd gewend om in een formule een getal (meestal x) in te vullen en direct een uitkomst (meestal y) te krijgen. 
Hier is dat niet zo: als we willen weten hoe groot u10 is kunnen we niet gewoon n = 10 invullen, immers dan staat er u10 = 2 • u9 + 1  en we weten niet hoe groot u9 is!!!! En voor u9 moeten we weer u8 weten.....
Er is maar één oplossing:  om een u-waarde uit te rekenen moeten we stap voor stap alle vorige uitrekenen.
Dat komt natuurlijk omdat de formule alleen aangeeft hoe een u uit de vorige u kan worden berekend. Een formule die dat doet heet een recursieformule:

In een recursieformule wordt aangegeven hoe een getal uit de vorigen kan worden berekend
BELANGRIJK GEVOLG
Gevolg is dat je het eerste getal u1 wel moet weten!! Dat moet erbij worden gegeven. Immers als je alleen maar weet dat un = 2 • un-1 + 1 en niet met welk getal de rij begint, dan kun je niet beginnen te rekenen! 

Oh ja.....nog even iets over de notatie......

We schreven tot nu toe steeds een getal uit de rij als un,  met die n daar onder de u hangend.
Soms zie je ook wel de notatie  u(n).

We noemden het eerste getal uit de rij altijd u1  (of  u(1) natuurlijk).
Vaak wordt het eerste getal ook wel nummer 0 genoemd, dus  u0  of  u(0). Je mag natuurlijk zelf weten hoe je hem noemt, voor mijn part begin je jouw rij met u1250 of zo, maar we zullen later zien dat het wel gevolgen heeft voor formules die we gaan opstellen. Meestal wordt de eerste u0 of u1 genoemd.

Tot slot zijn er nog wel eens mensen die het grappig vinden om een recursieformule te beginnen met un + 1 in plaats van met un. Dat kan natuurlijk. Zo is de formule  un = 2 • un-1 + 1  precies dezelfde als  un + 1 = 2 • un + 1,  immers bij un is  un-1 de vorige en bij un+ 1 is un de vorige.
   
   
 
 
  OPGAVEN
   
1. Bereken u5 van de volgende recursieformules:
         
  a. un = 2 • un - 1  + 5   met  u0 = 3.
       
  b. un = 2un - 12 + 1  met  u0 = 3.  
       
  c. un = 24/u(n - 1)   met  u1 = 8.  
         
2. Stel een recursieformule op bij de volgende rijen getallen.
         
  a. 1 - 5 - 9 - 13 - 17 - 21 - ...  
       
  b. 420 - 42 - 4,2 - 0,42 - 0,042 - ...  
       
  c. 2 - 8 - 38 - 188 - 938 - ...  
       
  d. 3 - 9 - 81 - 6561 - 43046721 - ...  
         
3. Stel een recursieformule op bij de volgende verhaaltjes.
         
  a. Elke maand geef ik  65% van het geld op mijn lopende rekening uit. Vervolgens krijg ik er aan het eind van de maand weer  3800 salaris bijgestort.
In maand 1 heb ik aan het begin  5600 op de lopende rekening staan.
       
  b. Een radioactieve stof vervalt langzaam naar een stabiele stof die niet meer radioactief is. Elk jaar blijkt 12% van de hoeveelheid radioactieve stof te vervallen. Dus wordt de straling ook 12% minder.
Op tijdstip t = 0 is de hoeveelheid straling gelijk aan  400 Curie  (de Curie is een oude eenheid voor stralingssterkte)
       
  c. De hoeveelheid plastic afval in de Grote Ocean neemt , als niemand actie onderneemt, elk jaar met 2% toe.
Gelukkig verwijdert het Ocean-Clea-Up project per jaar 2,2 miljoen kilo plastic afval uit de oceaan. Op t = 0 (2024)  werd de aanwezige hoeveelheid afval in de Grote Oceaan geschat op 75 miljoen kilo.
         
4. un =  4 •  un - 1 + 2  en  het blijkt dat  u4 = 234.  Bereken u1.
         
5. Een lineaire recursievergelijking van de vorm  un = a • un - 1 + b  levert de volgende waarden op:
         
 
n 0 1 2 3 4
u(n) 2 10 82 730 6562
         
  Bepaal u(5).
         
 

© h.hofstede (h.hofstede@hogeland.nl)