Ange nte elementet i en rekursiv talföljd

Exempel

Ange n:te elementet i en rekursiv talföljd

Talföljden $1, 1, 2, 3, 5, \dots$ 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} d \ddot{a} r 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.

$n$	$a_{n - 2}$	$a_{n - 1}$	$a_{n}$
$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$ .