Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following problem:

Let $a_{n}$ be the recurrence


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

share|cite|improve this question
up vote 3 down vote accepted

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$

share|cite|improve this answer
I tried characteristic equation and get r=-1,2.However, I do not know what to do next. Thank you : ) – John Hass Oct 23 '12 at 15:54
I don't know much about characteristic equation and I found that the intro in Wikipedia seems too complicated for me. Could you please write down the details of how to found the characteristic equation? I'll accept your answer.Thank you :)@MichaelBiro – John Hass Oct 28 '12 at 6:21
Thanks! Your explanation is very clear and easy to understand. I have a question here: Can we change the order of $k_1$ and $k_2$, that is, $a_n=k_2*2^n+k_1(-1)^n$? – John Hass Nov 5 '12 at 3:45

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

share|cite|improve this answer
Thanks. I'm not familiar with banach fixed point theorem. Could you please explain why we need $|f'(x)| <1$? – John Hass Oct 22 '12 at 6:52
@PENGTENG If $|f'(x)| <1$ see that it imlpies that $f$ is a contraction map i.e. $|f(x)-f(y)|<b|x-y|$ where $b=\sup_{x\in [p,3]|f'(x)}$ I will add a link where you can see that theorem. – clark Oct 22 '12 at 18:56

Let $b_n=a_{n+1}/a_n$. Note that $b_n=1+2/b_{n-1}$. Does that help? (it should....)

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.