How to find limit of a sequence defined by recurrence formula I have the following problem:
Let $a_{n}$ be the recurrence
$$a_{n+1}=a_{n}+2a_{n-1}$$
with $a_{0}=0$ and $a_{1}=1$. Can you help me find
$$\lim_{n\to\infty} \frac{a_{n+1}}{a_{n}}$$
for $n\geq 1$?
 A: You can solve this recurrence fairly easily using the characteristic equation, to get $a_n = \frac{1}{3}(2^n - (-1)^n)$. Then, as $n \rightarrow \infty$, $a_{n+1}/a_n \rightarrow 2$.
Edit: Given a linear homogeneous recurrence relation with constant coefficients $a_n = \sum_i c_i a_{n-i}$, assume $a_n = \alpha^n$ satisfies the recurrence. Then we get the characteristic equation $\alpha^n = \sum_i c_i \alpha^{n-i}$. The characteristic equation is a polynomial whose roots (the possible values of $\alpha$ that satisfy the recurrence) define the solution to the recurrence. If the roots $\alpha_1,\alpha_2,\dots,\alpha_m$ are unique (like in this example), then the solution is a linear combination of the roots to the $n$th power, i.e. $a_n = k_1 \alpha_1^n + k_2\alpha_2^n + \dots + k_m \alpha_m^n$, where the values of $k_1,k_2,\dots,k_m$ are defined by the initial conditions. If there are repeated roots, the combination includes powers of $n$ as well, but in this example the roots are unique, so I'll skip that.
For us, we have $a_n = a_{n-1} + 2a_{n-2}$ with $a_0 = 0$ and $a_1 = 1$. Then, the characteristic equation is $\alpha^n = \alpha^{n-1} + 2\alpha^{n-2}$, which simplifies to $\alpha^2 = \alpha + 2$. The quadratic solutions give $\alpha_1 = 2$ and $\alpha_2 = -1$. Then, the theorem states that $a_n = k_1 2^n + k_2 (-1)^n$. Using the initial conditions, we have $a_0 = k_1 2^0 + k_2 (-1)^0 = k_1 + k_2 = 0$ and $a_1 = k_12^1 + k_2(-1)^1 = 2k_1 - k_2 = 1$. That means that $k_1 = \frac{1}{3}$ and $k_2 = - \frac{1}{3}$, so $a_n = \frac{1}{3}(2^n - (-1)^n)$.
Now, $\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = \lim_{n \to \infty} \frac{1/3(2^{n+1}-(-1)^{n+1})}{1/3(2^n - (-1)^n)} = \lim_{n \to \infty}\frac{2^{n+1}-(-1)^{n+1}}{2^n - (-1)^n} = \lim_{n \to \infty} \frac{2-(-1^{n+1}/2^n)}{1 - (-1/2)^n} = \frac{2}{1} = 2$
A: Define $b_{n} = \frac{a_{n+1}}{a_{n}}$ for $n \geq 1$ so $b_1=1$ and $b_{n+1}=1 +\frac{2}{b_n}$ This is straigthforward if you divide your recursion with $a_n$.
We will solve this using banach fixed point theorem. The function which we will apply it is $f(x)= 1 +\frac{2}{x}$ in order to be able to apply we need to define this function in an interval such that 
$|f'(x)| <1 \Leftrightarrow \frac{2}{x^2} <1 \Leftrightarrow x>\sqrt{2}, x>-\sqrt{2}$.
Now we will show by induction that $3>b_n\geq \frac{5}{3}, \text{ for } n\geq 3$ 
$$b_3=\frac{5}{3}$$
Assume $$\frac{5}{3} \leq b_n < 3$$
$$\frac{6}{5} > \frac{2}{b_n} \geq \frac{2}{3}$$
$$3>\frac{11}{5} >1+ \frac{2}{b_n} \geq \frac{5}{3}$$
Observe $b_n\geq \frac{5}{3} > \sqrt{2}$
Take $p \in (\sqrt{2}, \frac{5}{3})$
and define $f$ on $[p,3]$
the recursion is now given by $f(b_n)=b_{n+1}.$ 
$f$ is a contraction ( $|f(x)-f(y)|\leq \sup_{x\in [p,3]|f'(x)}|x-y|$). The only fixed on that $f$ is $2$
So $$b_n \rightarrow 2$$
A: Let $b_n=a_{n+1}/a_n$. Note that $b_n=1+2/b_{n-1}$. Does that help? (it should....)
A: The answer is the real positive root of characteristic polynomial of the recurrence. For the given sequence the characteristic polynomial is x^2=x+2. The roots {-1,2}. So the answer is 2. It works for any recurrence $$a_{n}=\sum c_{i}a_{i}, \ i<n$$ if $$\lim_{n\to\infty} \frac{a_{n+1}}{a_{n}}$$ exists.
