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}$ .