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$?

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$
