# Thread:

1. ## Recurrence and Fibonacci sequence

Hi. I have this problem that im stuck on.

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

a) Write out explicitly $(G_n)_{n=0,...,10}$
I think this is easy.
{2,1,3,4,7,11,18,29,47,76}

b) Prove that $G_n=F_{n-1}+F_{n+1}$, $n\ge1$
How do I go about it?
I know $F_0=0$ and $F_1=1$ and $F_2=1$ and $F_3=2$
So if $n=1$, $G_1=F_0+F_3=1+2=3$, so it looks like its true.But how do I prove it explicitly?\

c) Let $\tau= \frac{1+ \sqrt{5}}{2}$ denote the golden ratio. Show $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 $(G_n)_{n \ge1}$ counts?Draw the objects corresponding to $G_3$.
$G_3=G_2+G_1$
$G_3=3+1=4$
But I'm not quite sure what it counts...

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

2. In...

http://www.mathhelpforum.com/math-he...ce-154056.html

... it has been demonstrated that the general solution of the difference equation...

$x_{n} = x_{n-1} + x_{n-2}$ (1)

... is...

$\displaystyle x_{n}= c_{1} (\frac{1-\sqrt{5}}{2})^{n} + c_{2} (\frac{1+\sqrt{5}}{2})^{n}$ (2)

If You start setting $x_{0}= 0$ and $x_{1}=1$ You obtain the 'Fibonacci sequence'. If You set $x_{0}=2$ and $x_{1}=1$ and You obtain the 'G sequence'...

Kind regards

$\chi$ $\sigma$
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 29, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8425154089927673, "perplexity_flag": "middle"}