Sequence: $1, 1, 2, 3, 5, 8, 13, 21$
1) Give the recurrence relation and initial values
2) Find the explicit formula for $F_n$
Here's my answer for 1), correct me if I'm wrong.
Recurrence relation: $F_n = F_{n-1} + F_{n-2}$
Initial Values: $F_1=F_2=1$
I do not understand 2), isn't it the same formula as 1)?
$F_n = F_{n-1} + F_{n-2}$ ???
Best Answer
This is just the Fibonacci sequence and the solution is given explicitly by Binet's formula,
$$F_n=\frac{\varphi^n-\psi^n}{\varphi-\psi}$$
where
$$\varphi,\psi=\frac{1\pm\sqrt{5}}{2}$$