Hi. I have this problem that im stuck on.

Define a sequence $\displaystyle (G_n)_{n \ge0} $ by the recurrence $\displaystyle G_n = G_{n-1}+G_{n-2}$ for $\displaystyle n \ge2$. Subject to the initial values $\displaystyle G_0=2$, $\displaystyle G_1=1$. Let $\displaystyle (F_n)_{n \ge0} $ denote the Fibonacci sequence.

a) Write out explicitly $\displaystyle (G_n)_{n=0,...,10} $

I think this is easy.

{2,1,3,4,7,11,18,29,47,76}

b) Prove that $\displaystyle G_n=F_{n-1}+F_{n+1}$, $\displaystyle n\ge1$

How do I go about it?

I know $\displaystyle F_0=0$ and $\displaystyle F_1=1$ and $\displaystyle F_2=1$ and $\displaystyle F_3=2$

So if $\displaystyle n=1$, $\displaystyle G_1=F_0+F_3=1+2=3$, so it looks like its true.But how do I prove it explicitly?\

c) Let $\displaystyle \tau= \frac{1+ \sqrt{5}}{2}$ denote the golden ratio. Show $\displaystyle G_n= \tau^n+(-\tau)^{-n}$

I'm just a bit lost in this one...

d) The Fibonacci sequence counts pavings by monomers and dimers of an n-board. Conjecture what sort of pavings the sequence $\displaystyle (G_n)_{n \ge1} $ counts?Draw the objects corresponding to $\displaystyle G_3$.

$\displaystyle G_3=G_2+G_1$

$\displaystyle G_3=3+1=4$

But I'm not quite sure what it counts...

Any help would be great. Thank-you so much!!