Take the 2-minute tour ×

I have the following problem:

Let $a_{n}$ be the recurrence


with $a_{0}=0$ and $a_{1}=1$. Can you help me find


for $n\geq 1$?

share|improve this question

4 Answers 4

up vote 2 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|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|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|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|improve this answer

Your Answer


