Recurrence and Fibonacci sequence

Hi. I have this problem that im stuck on.

Define a sequence by the recurrence for . Subject to the initial values , . Let denote the Fibonacci sequence.

a) Write out explicitly

I think this is easy.

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

b) Prove that ,

How do I go about it?

I know and and and

So if , , so it looks like its true.But how do I prove it explicitly?\

c) Let denote the golden ratio. Show

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 counts?Draw the objects corresponding to .

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

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