Finding closed formula for recurrence relation

Question

So I'm having some problems finding the closed formula for the following recurrence relation:

$ D_n = D_{n-1} + D_{n-2} $ for $ n >= 2 $
where
$ D_0 = 2 $ and $ D_1 = 1 $

I can see that this is the fibonacci sequence but the initial values are throwing me off.

Answer 1

The chracteristic equation is

$$x^2-x-1=0$$

the roots are

$$a=\frac{1-\sqrt{5}}{2}$$ and $$b=\frac{1+\sqrt{5}}{2}$$

thus

$$D_n=Aa^n+Bb^n$$.

with

$$D_0=A+B=2$$ and $$D_1=Aa+Bb=1$$

which gives

$$A=\frac{1-2b}{a-b}=1$$ and $$B=\frac{1-2a}{b-a}=1$$

Finally $$D_n=a^n+b^n$$