Exempel
Ange n:te elementet i en rekursiv talföljd
Exempel
Talföljden 1,1,2,3,5,… kallas Fibonacciföljden. Varje tal bildas genom att addera de två föregående, och kan därför beskrivas av den rekursiva formeln an=an−1+an−2da¨ra1=a2=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.
n | an−2 | an−1 | an |
---|---|---|---|
6 | 3 | 5 | 3+5=8 |
7 | 5 | 8 | 5+8=13 |
8 | 8 | 13 | 8+13=21 |
9 | 13 | 21 | 13+21=34 |
10 | 21 | 34 | 21+34=55 |
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.