Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

4 Answers

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 : ) –  J.A.F 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 –  J.A.F 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$? –  J.A.F Nov 5 '12 at 3:45
add comment

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
add comment

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$? –  J.A.F 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
add comment

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
add comment

Your Answer

 
discard

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.