Recurrence relation for fibonacci sequence

Question

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

Answer 1

Yes, this is just the fibonacci sequence.

To compute the $n$-th term, the formula in part $(a)$ requires $(n-1)$-th and $(n-2)$-th term. To solve for the $(n-1)$-th term, the formula requires $(n-2)$-th and $(n-3)$-th term, hence the complexity of the formula is $O(n)$.

As mentioned by Frpzzd, Part $(b)$ asks for a more efficeint formula that doesn't requires the computation of previous terms.

The formula is known as Binet's formula.

$$F_n=F_{n-1}+F_{n-2}$$

The characteristic polynomial is

$$x^2=x+1$$

Solve for the roots, call it $r_1$ and $r_2$.

The formula is $F_n=ar_1^n+br_2^n$.

Can you solve for $a$ and $b$?

Answer 2

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