# Recurrence Relations

1. solution Find the limiting ratio $\lim_{n\rightarrow\infty} \frac{x_{n+1}}{x_n}\,$ for the recurrence relation $x_n=x_{n-1}+x_{n-2}\,$.

2. solution Let $x_n := \left\{\begin{matrix} x_{n-1} + x_{n-2} & \mbox{if } n>1 \\ x_1 \in \mathbb{N} & \mbox{if } n=1 \\ x_0 \in \mathbb{N} & \mbox{if } n=0 \\ 0 & \mbox{if } n<0 \end{matrix}\right.$     Show that $x_n = x_{1}F_{n-1} + x_{0}F_{n-2} \,\!$ where $F_n\,\!$ is the n-th Fibonacci number   (F0 = F1 = 1)

3. solution Let $x_n := \left\{\begin{matrix} 1+\frac{1}{x_{n-1}} & \mbox{if } n>0 \\ x_0 \in \mathbb{N} & \mbox{if } n=0 \\ 0 & \mbox{if } n<0 \end{matrix}\right.$     Show that $x_n = \frac{x_{0}F_{n} + F_{n-1}}{x_{0}F_{n-1} + F_{n-2}} \,\!$ where $F_n\,\!$ is the n-th Fibonacci number   (F0 = F1 = 1 and F(n < 0) = 0)

4. solution Let $x_n := \left\{\begin{matrix} x_{n-1}*x_{n-2} & \mbox{if } n>1 \\ x_1 \in \mathbb{N} & \mbox{if } n=1 \\ x_0 \in \mathbb{N} & \mbox{if } n=0 \\ 0 & \mbox{if } n<0 \end{matrix}\right.$     Show that $x_n = x_{1}^{F_{n}}*x_{2}^{F_{n-1}} \,\!$ where $F_n\,\!$ is the n-th Fibonacci number   (F0 = F1 = 1 and F(n < 0) = 0)

##### Toolbox

 Get A Wifi Network Switcher Widget for Android