Recursie

Een rij van getallen kan je geven met behulp van een recursief  voorschrift zoals bijvoorbeeld : a_1=1 en a_n= 2a_{n-1}+1. Soms kan je uit dit recursief voorschrift een expliciete formule afleiden voor de algemene term van de rij. Soms kan dat niet, maar is het mogelijk, via recursie, de parameters te herleiden tot waarden waarvoor je het probleem wel kan oplossen.

Een eerlijk muntstuk wordt n keer opgeworpen. Wat is de kans op twee opeenvolgende keren kop ergens in de rij worpen?

  • Noteer met P_n de kans dat er nergens twee keer kop na elkaar voorkomt is de rij van n worpen.
  • Het is duidelijk dat P_1=1 en P_2=\frac{3}{4}.
  • Stel n>2. Dan zijn er twee mogelijkheden naargelang de eerste worp kop of munt is.
  • Als je eerst munt gooit, dan is de kans dat je nergens twee keer kop na elkaar hebt in de volgende n-1 worpen gelijk aan P_{n-1}.
  • Gooi je eerst kop, dan moet de tweede worp munt zijn, want anders zou je twee keer kop na elkaar hebben. De kans dat je nergens twee keer kop na elkaar hebt in de volgende n-2 worpen gelijk aan P_{n-2}.
  • Uit de vorige twee punten vinden we tenslotte dat

        \[P_n=\frac{1}{2}P_{n-1}+\frac{1}{4}P_{n-2}\]

  • Dit kan je herleiden tot 2^nP_n=2^{n-1}}P_{n-1}+2^{n-2}P_{n-2}. Of via S_n=2^nP_n:

        \[S_n=S_{n-1}+S_{n-2}\]

  • Dit is de rij van Fibonacci, waarbij S_n het n+2 de getal in de rij van Fibonacci is. Dus S_n=F_{n+2}. De gezochte kans op twee opeenvolgende keren kop ergens in de rij van n worpen, met n>2 is dan X=1-P_n=1-\frac{F_{n+2}}{2^n}.