Recurrence Relations

From Exampleproblems

Jump to: navigation, search

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)

5. solution Let x_n := \begin{cases} a + x_{n/c} & \mbox{if } n>1 \\ b & \mbox{if } n\le1\end{cases}\mbox{ }c>1,\mbox{ }n,c \in \mathbb{R}
Evaluate x_n\,\!.

6. solution Let x_n := \begin{cases} \frac{1 + n! * x_{n-1}}{n*n!} & \mbox{if } n > 0 \\ 0 & \mbox{otherwise}\end{cases} \,\!
Show that x_n = \frac{1}{n!}\sum_{i=1}^{n} \frac{1}{i}\,\!.

Main Page

Retrieved from "http://www.exampleproblems.com/wiki/index.php/Recurrence_Relations"
Personal tools