Ange nte elementet i en rekursiv talföljd

Talföljden $1, \, 1,\, 2,\, 3,\, 5,\, \ldots$ kallas Fibonacciföljden. Varje tal bildas genom att addera de två föregående, och kan därför beskrivas av den rekursiva formeln $a_n = a_{n-1} + a_{n-2} \quad \text{där} \quad a_1=a_2=1.$ Vilket är tal nr $10$ i följden? För att beräkna det tionde talet behöver vi tal nr $9$ och $8$, som kräver att vi vet tal nr $7$ och $6$, som kräver att vi vet tal nr $5$ och $4$, osv. Eftersom följden är rekursiv måste vi veta alla tal fram till det tionde talet.

De tio första talen i följden blir alltså $1, \, 1,\, 2,\, 3,\, 5,\, 8,\,13,\,21,\,34,\,55$ och det tionde talet i följden är $55$.