# Given sequence - finding the limit

1. Nov 6, 2013

### Saitama

1. The problem statement, all variables and given/known data
A sequence of numbers $x_n$ is determined by the equality $x_n=\frac{x_{n-1}+x_{n-2}}{2}$ and the values of $x_0$ and $x_1$. Compute $x_n$ in terms of $x_0, x_1$ and $n$. Also prove that $$\lim_{n \rightarrow \infty} x_n=\frac{x_0+2x_1}{3}$$.

2. Relevant equations

3. The attempt at a solution
I don't know where to start with such kind of problem so I tried with calculating a few terms.
$$x_2=\frac{x_0+x_1}{2}$$
$$x_3=\frac{x_0+3x_1}{4}$$
$$x_4=\frac{3x_0+5x_1}{8}$$
$$x_5=\frac{5x_0+11x_1}{16}$$
Okay, I see the denominator is $2^{n-1}$ but I can't catch any pattern for the numerator. :(

Any help is appreciated. Thanks!

2. Nov 6, 2013

### haruspex

A standard approach is to see if there's a solution like Aλn. In this case you should find two choices for λ, so the general solution will be a sum of two such terms. (The problem is analogous to a second order homogeneous ODE.)

3. Nov 6, 2013

### Saitama

I am not sure what you mean but do you ask me to do this: $x_n=A\lambda^n$?

4. Nov 6, 2013

### dirk_mec1

Suppose A is the cf of x0 and B is the cf of x1.

Hint: if n is odd then

$$A =\frac{2^{n-1}-1}{3}$$

$$B=2^{n-1} -A$$

5. Nov 6, 2013

### Saitama

How do you get those?

I honestly can't catch the pattern for even ones. :(

6. Nov 6, 2013

### dirk_mec1

Hint: $$A+B=2^{n-1}$$

7. Nov 6, 2013

### haruspex

Yes. Plug that into the recurrence relation and simplify. What equation do you get for λ? This is a very powerful and standard method for solving recurrence relations.

8. Nov 7, 2013

### Saitama

I honestly don't understand what your statements mean. What is this "recurrence" thing? I have never heard of anything like that. :uhh:

9. Nov 7, 2013

### vanhees71

The point is that the sequences of this kind build a two-dimensional vector space. Think about this statement. It's a good exercise and a commonly used trick.

Given this statement, you only need two linearly independent solutions of the recursion relation to know all sequences. A common idea then is to check, whether you can find two geometric series' as a basis for your vector space of sequences that are linearly independent. That's why in the thread it was suggested to look for a solution of the recursion in terms of
$$x_n=\lambda^n.$$
This you plug into your recursion relation and see, whether you can find two different values for $\lambda$.

Then all sequences are given as linear combinations of those. Finally you can map the two free parameters in these linear combinations one-to-one to the initial values $x_0$ and $x_1$.

10. Nov 7, 2013

### Saitama

Is there any way to solve the problem using elementary techniques? I have never seen words like "vector spaces" and "recursion" in my course.

11. Nov 7, 2013

### pasmith

A recurrence relation is an equation which defines the nth term of a sequence in terms of previous terms of the sequence; for example
$$x_n = \frac{x_{n-1} + x_{n-2}}{2}.$$
This is 2nd order, so given $x_0$ and $x_1$ you can calculate $x_3$, $x_4$, etc.

The method of solving linear recurrence relations with constant coefficients is based on the fact that for any $A$, $x_n = A \lambda^n$ is a solution of
$$x_n = \lambda x_{n-1}$$
in the same way that the method of solving linear ordinary differential equations with constant coefficients is based on the fact that for any $A$, $x(t) = Ae^{\lambda t}$ is a solution of
$$\dot x = \lambda x$$
and in practice is largely identical: you solve a polynomial for $\lambda$ which gives you your complementary functions, and the general solution is a linear combination of these.

12. Nov 7, 2013

### dirk_mec1

Last hint:

$$x_n = \frac{x_0 + 2x_1}{3} + \left( \frac{-1}{2} \right)^n \left(\frac{2}{3} \right) (x_0-x_1)$$

13. Nov 7, 2013

### Saitama

Thanks dirk_mec1 but how did you come up with that?

The correct way as presented by other posters involves recurrence relations which I have never seen in my course. I don't understand why there is such kind of question in the practice sheet.

Does your method involves only guesswork? It looks quite difficult to come up with that general term.

14. Nov 7, 2013

### dirk_mec1

1) Set up the characteristic equation: $$2\lambda^2 -\lambda -1 =0$$
2) solve it for the two lambda's.
3) Use the first two values to find the two constants: x(0) =x_0 and x(1) =x_1.
4) Check your solution by comparing it with the recurrence relation.

15. Nov 7, 2013

### haruspex

The equality you were given is a recurrence relation, even if that term has never been used in your course, so it is appropriate to use a standard recurrence relation approach.
[pace vanhees71, but I would not call it a recursion, perhaps because of my software background. In programming terms it's more like iteration. But it's a subtle difference.]
dirk_mec1 appears to have used the method vanhees71, pasmith and I have been suggesting, but, unfortunately, whizzed past those first steps and has been posting equations you will come to later during the solution.
So, please, just plug xn=Aλn into your equality (taking it to be true for all n, of course), simplify, and see what you get.

16. Nov 7, 2013

### dirk_mec1

Actually I didn't at first I found the two equations via trial and error that's why it seems as if I skipped a lot of steps but I did not. This is also the reason I differentiated even and odd numbers. Thanks to vanhees the solution can be found in a general manner though.

Last edited: Nov 7, 2013
17. Nov 8, 2013

### Saitama

Okay, I substitute the values as you say.
$$x_0=A\lambda^0 \Rightarrow A=x_0$$
$$x_1=x_0\lambda$$
$$x_2=x_0\lambda^2 \Rightarrow \frac{x_0+x_1}{2}=x_0\lambda^2 \Rightarrow \frac{x_0+x_0\lambda}{2}=x_0\lambda^2$$
Simplifying,
$$2\lambda^2-\lambda-1=0$$
Solving for $\lambda$ I get two values, -1/2 and 1.
So I have
$$x_n=x_0\left(\frac{-1}{2}\right)^n$$
I have no idea about what I am doing.

18. Nov 8, 2013

### dirk_mec1

No, $$x(n) = C1 \cdot \lambda_1^n +C1 \cdot \lambda_2^n$$
since a linear combination of a solution is also a solution.

19. Nov 8, 2013

### Saitama

I am not sure what that means. Do you ask me to substitute $\lambda_1=-1/2$ and $\lambda_2=1$ or do I have to try different values of n and solve the equations?

Last edited: Nov 8, 2013
20. Nov 8, 2013

### vanhees71

$$x_n=C_1 \lambda_1^n + C_2 \lambda_2^n=C_1+C_2 (-1/2)^n.$$
Now you can determine $C_1$ and $C_2$ from the initial condition of the recursion, i.e.,
$$x_0=C_1+C_2, \quad x_1=C_1-\frac{C_2}{2}.$$
$$x_{\infty}=\lim_{n \rightarrow \infty} x_n=\lim_{n \rightarrow \infty} \left [C_1 +C_2 \left (-\frac{1}{2} \right )^n \right]=\cdots$$