# Find the limit of the recursive sequence

Definition of the sequence :

$$a_1=a;\\a_2=b;\\$$ and $$\ \ \ a_{n+2}={{a_n+a_{n+1}}\over2}$$ for $n\geq 1$.

Find the limit of this sequence in terms of $a$ and $b$.

Now in this case , taking $\lim_{n\rightarrow \infty}$ on both sides does not help at all . So what I did was try to find the $n$-th term in therms of $a$ and $b$ and then take $n$ to $\infty.$

So , using the given recursion formula I wrote down like $7$-$8$ terms, grouped them in various ways but still could not get the pattern of the $n$-th term.

Terribly sorry for the lack of work/context in this post of mine but I tried for like an hour to figure things out but can't really put those scribbles down here.

Please give me some hints as to how to find the answer . Thank you.

• Do you know how to solve linear recursions? The characteristic equation for this system has two distinct real roots, so you can "easily" write down a closed form. – lulu Dec 8 '15 at 21:05
• @lulu : I don't understand anything you said so I guess not. Could you please help me a little more or , say post an answer $?$ – user118494 Dec 8 '15 at 21:08
• Try a hint first. Linear recursions, like this one or like the Fibonacci sequence, can best be solved by "guessing" that the answer is of the form $a_n=\lambda^n$ and trying to find $\lambda$. Sometimes, but not here, some additional steps are needed. Here you just get a quadratic with two distinct real roots $(\lambda_1,\lambda_2)$ so the general form is $a_n=A\lambda_1^n+B\lambda_2^n$ – lulu Dec 8 '15 at 21:11
• Here is a good reference for solving linear recursions: cs.columbia.edu/~cs4205/files/CM2.pdf – lulu Dec 8 '15 at 21:14
• @lulu : I don't understand anything even now . Whatever linear algebra I have learnt till date does not include any such thing . Could you tell me what book or what topic/chapter of a standard linear algebra book I should read to know these things,please $?$ – user118494 Dec 8 '15 at 21:15

Different solution:

\begin{align} 2a_{n+2}&=a_{n+1}+a_n\\ 2(a_{n+2}-a_{n+1})&=-\left(a_{n+1}-a_n\right)\\ a_n-a_{n-1}&=-\frac12\left(a_{n-1}-a_{n-2}\right)\\ &=\frac14\left(a_{n-2}-a_{n-3}\right)=\cdots=\left(-\frac12\right)^{n-2}\left(a_2-a_1\right)\\ \therefore a_n&=a_{n-1}+\left(-\frac12\right)^{n-2}\left(b-a\right)\\ a_{n-1}&=a_{n-2}+\left(-\frac12\right)^{n-3}\left(b-a\right)\\ &\cdots\\ a_2&=a_1+\left(-\frac12\right)^{0}\left(b-a\right)\\ \end{align} Adding side by side, \begin{align} a_n&=a_1+(b-a)\sum_{k=0}^{n-2}\left(-\frac12\right)^{k}\\ &=a+(b-a)\frac{1-\left(-\frac12\right)^{n-1}}{1-\left(-\frac12\right)}\\ &=a+\frac23(b-a)\left(1-\left(-\frac12\right)^{n-1}\right)\\ &=\frac{a+2b}{3}+\frac{2(a-b)}{3}\left(-\frac12\right)^{n-1} \end{align} You can see the outcome is exactly same as other solutions.

But hopefully you'll be able to find where the $\left(-\frac12\right)^{n-1}$ is coming from.

• Nice, elementary, and no magic involved. – marty cohen Dec 8 '15 at 22:29
• @martycohen Thanks, marty. – Kay K. Dec 8 '15 at 22:31
• Very slick solution. I like this method a lot. – Joel Dec 8 '15 at 22:41
• I generalized this for $ca_{n-1}+(1-c)a_{n-2}$. – marty cohen Dec 8 '15 at 23:04

$$a_n=\frac{1}{3}a+\frac{2}{3}b+\left(\frac{4}{3}b-\frac{4}{3}a\right)\times\left(-\frac{1}{2}\right)^{n}$$

• And how do I decide that $?$ – user118494 Dec 8 '15 at 21:15
• This is obvious to anyone for whom it is obvious. – marty cohen Dec 8 '15 at 23:16

• How did you come up with that $2\alpha ^2 -\alpha -1=0$ after the first step $?$ – user118494 Dec 8 '15 at 21:45
• I got two roots ($1$, $-\frac12$) and then made up the expression for $a_n$ that is $a_n = c_0\cdot \alpha_0^n + c_1\cdot \alpha_1^n$ ($\alpha_0=1$ and $\alpha_1=-\frac12$ in our case). In my answer I used $n-1$ instead of $n$ to make later calculations easier. You can google "generating function for sequence" and can find information. – Kay K. Dec 8 '15 at 21:49

If you would like to have a closed form for the individual terms of the recurrence, you can use the method of generating functions. This first step places your sequence as the terms of a power series $G(x) = \sum_{n=1}^\infty a_n x^n$, and then you generate a separate representation using the recursion. It's a long process but very powerful. It's real strength comes from combinatorics, but it can solve linear recurrences well.

$$G(x) = \sum_{n=1}^\infty a_n x^n = ax + bx^2 + \sum_{n=3}^\infty a_n x^n$$ $$= ax + bx^2 + \sum_{n=1}^\infty a_{n+2} x^{n+2}$$ $$= ax + bx^2 + \frac x2 \sum_{n=1}^\infty a_{n+1} x^{n+1} + \frac{x^2}2 \sum_{n=1}^\infty a_{n} x^{n}$$ $$= ax + bx^2 + \frac x2 \left(\sum_{n=1}^\infty a_{n} x^{n} - ax\right) + \frac{x^2}2 \sum_{n=1}^\infty a_{n} x^{n}.$$

Thus recognizing $G(x)$ as the series on the right, we have $$G(x)= ax + bx^2 + \frac x2 \left(G(x) - ax\right) + \frac{x^2}2 G(x).$$ Thus solving for $G(x)$ we find:

$$G(x)(1-\frac{x}{2}-\frac{x^2}{2})=ax + (b-\frac{a}{2})x^2$$

and

$$G(x) = \frac{2ax}{2-x-x^2} + \frac{(2b-a)x^2}{2-x-x^2}.$$

Using partial fraction decomposition we get:

$$G(x) = (2ax + (2b-a)x^2) \left( \frac{1}{6} \frac{1}{1-\left(-\frac x 2\right)} + \frac13 \frac{1}{1-x} \right)$$

Now applying geometric series identities:

$$G(x) = (2ax + (2b-a)x^2) \sum_{n=0}^\infty\left( \frac{1}{6} \frac{(-1)^n}{2^n} + \frac13\right) x^n$$

Manipulating series:

$$G(x) = \sum_{n=0}^\infty 2a \left( \frac{1}{6} \frac{(-1)^n}{2^n} + \frac13\right) x^{n+1} + \sum_{n=0}^\infty (2b-a)\left( \frac{1}{6} \frac{(-1)^n}{2^n} + \frac13\right) x^{n+2}$$

$$=\sum_{n=1}^\infty 2a \left( \frac{1}{6} \frac{(-1)^{n-1}}{2^{n-1}} + \frac13\right) x^{n} + \sum_{n=2}^\infty (2b-a)\left( \frac{1}{6} \frac{(-1)^{n-2}}{2^{n-2}} + \frac13\right) x^{n}$$

$$=a + \sum_{n=2}^\infty \left[ 2a \left( \frac{1}{6} \frac{(-1)^{n-1}}{2^{n-1}} + \frac13\right) + (2b-a)\left( \frac{1}{6} \frac{(-1)^{n-2}}{2^{n-2}} + \frac13\right) \right] x^n$$

Thus since $G$ is a power series centered about zero, its coefficients are uniquely determined. For $n \ge 2$ we have: $$a_n = \left[ 2a \left( \frac{1}{6} \frac{(-1)^{n-1}}{2^{n-1}} + \frac13\right) + (2b-a)\left( \frac{1}{6} \frac{(-1)^{n-2}}{2^{n-2}} + \frac13\right) \right]$$

now as $n \to \infty$ we are left with $L = \lim_{n\to\infty} a_n = 2a \cdot \frac13 + (2b-a) \cdot \frac13 = \frac{1}{3}a + \frac{2}{3} b$.

• @user118494 Your comments posed to the other answers are addressed in this answer. The appearance of the characteristic equation $2x^2-x-1=0$ is important in factoring the denominator before applying the partial fraction decomposition. – Joel Dec 8 '15 at 22:03
• This method will always work for linear recurrences. It just take a bit of time. With practice and observation, you will realize how to move from the long winded generating function derivation to the quicker answers others gave. – Joel Dec 8 '15 at 22:05
• Certainly, though, generating functions aren't the only way to go about it. There are many linear algebraic methods that can solve the problem. The nice approach of generating functions only require some knowledge of power series obtained in Calculus 2. It is fairly tedious. – Joel Dec 8 '15 at 22:07

We will try a form for the solution with some unknown parameters, and then see if we can find parameters that make it work. For example, let us guess that

$$a_n = Ad^n$$

for some constant numbers $d$ and $A$. Then we also need:

$$a_{n+1} = Ad^{(n+1)}$$

$$a_{n+2} = Ad^{(n+2)}$$

Then plug into our equation:

$$Ad^{(n+2)} = \frac{Ad^{(n+1)}+Ad^n}{2}$$

Every term is divisible by $Ad^n$, so cancelling that everywhere we get $$d^2 = \frac{d+1}{2}$$

We can see that the recurrence relation is true if we can find a $d$ that satisfies this quadratic equation. Rearranging, we see that it is

$$d^2-\frac{d}{2}-\frac{1}{2} = 0$$

$$(d-1)(d+1/2) = 0$$

which is true when $d=1$ or $d=-1/2$. Now what this tells us is that if we take

$$a_n = A1^n = A$$

or

$$a_n = A(-1/2)^n,$$

we have a solution to the original problem. Recall that $A$ was an arbitrary constant that has not been determined yet, so it is possible that it is actually two different constants between the two cases above. To account for this, we write the second constant as $B$, giving two independent solutions

$$a_n = A,\;\text{or}\;a_n=B(-1/2)^n$$

Now, we can see that plugging in either solution solves the recurrence. What about their sum? You can work out that the sum of the two solutions is also a solution, so consider

$$a_n = A + B(-1/2)^n$$

This is the general solution. We figured out what the $d$ value was, now we have to figure out the $A$ and $B$ constants. Fortunately, we have some additional constraints: $$a_1 = a,\;a_2=b$$ You should be able to take it from here to solve for $A$ and $B$, following what the other answers show.

Generalizing Kay K's solution:

If $a_{n+1} =ca_n+(1-c)a_{n-1}$ where $0 < c < 1$, then $a_{n+1}-a_n =-(1-c)(a_n-a_{n-1}) =r(a_n-a_{n-1})$, where $r = -(1-c)$.

By induction, $a_{n+1}-a_n =r^k(a_{n-k+1}-a_{n-k-2})$.

Setting $k = n-1$, $a_{n+1}-a_n =r^{n-1}(a_{2}-a_{1}) =sr^{n-1}$, where $s =a_{2}-a_{1}$.

Summing this from $n=1$ to $m-1$,

$\begin{array}\\ a_m-a_1 &=s\sum_{n=1}^{m-1} r^{n-1}\\ &=s\sum_{n=0}^{m-2} r^{n}\\ &=s\frac{1-r^{m-1}}{1-r}\\ &=(a_{2}-a_{1})\frac{1-(c-1)^{m-1}}{c}\\ &=(a_{2}-a_{1})\frac1{c}-\frac{(c-1)^{m-1}}{c}\\ \end{array}$

so $a_m =a_1+(a_{2}-a_{1})\frac1{c}-\frac{(c-1)^{m-1}}{c} =\frac{a_{2}+(1-c)a_{1}}{c}-\frac{(c-1)^{m-1}}{c}$.

Therefore, since $|c-1| < 1$, $\lim_{m \to \infty}a_m =\frac{a_{2}+(1-c)a_{1}}{c}$.

If $c = \frac12$, this is $\frac{a_{2}+\frac12 a_{1}}{\frac12} =2a_{2}+a_{1}$.

Note that the characteristic polynomial is $0 =x^2-cx-(1-c) =(x-1)(x-(c-1))$. This shows that the roots are always nice.