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.
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!!