Given sequence - finding the limit

[Saitama]

Homework Statement

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

Homework Equations

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!

 

[haruspex]

A standard approach is to see if there's a solution like Aλⁿ. 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.)

 

[Saitama]

A standard approach is to see if there's a solution like Aλⁿ. 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.)

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

 

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

 

[Saitama]

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

How do you get those?

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

 

[dirk_mec1]

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

 

[haruspex]

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

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.

 

[Saitama]

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.

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

 

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

 

[Saitama]

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

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

 

[pasmith]

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

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.

 

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

 

[Saitama]

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

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.

 

[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.

 

[haruspex]

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.

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 x_n=Aλⁿ into your equality (taking it to be true for all n, of course), simplify, and see what you get.

 

[dirk_mec1]

dirk_mec1 appears to have used the method vanhees71, pasmith and I have

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.

 

[Saitama]

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 x_n=Aλⁿ into your equality (taking it to be true for all n, of course), simplify, and see what you get.

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.

 

[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.

 

[Saitama]

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

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?

 

[vanhees71]

Of course it must read
$$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}.$$
Then it's pretty easy to get the limit
$$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$$

 

[haruspex]

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?

What you have found up to this point is that x_n=Cλⁿ is a solution to the equation for any C and either of those two values for λ. But it might not satisfy the initial conditions, so we need to look for the most general solution then see which meets those conditions. Next you notice that if x_n = f(n) and x_n = g(n) are solutions to the equation then so is x_n = f(n)+g(n). So the most general solution we can construct this way is x_n=C₁λ₁ⁿ+C₂λ₂ⁿ. Since that gives us two parameters to play with, and there are two initial conditions, we should be able to find a C₁ and C₂ that work.

 

[Saitama]

What you have found up to this point is that x_n=Cλⁿ is a solution to the equation for any C and either of those two values for λ. But it might not satisfy the initial conditions, so we need to look for the most general solution then see which meets those conditions. Next you notice that if x_n = f(n) and x_n = g(n) are solutions to the equation then so is x_n = f(n)+g(n). So the most general solution we can construct this way is x_n=C₁λ₁ⁿ+C₂λ₂ⁿ. Since that gives us two parameters to play with, and there are two initial conditions, we should be able to find a C₁ and C₂ that work.

I don't think I have grasped the concept of the problem but I did as you and vanhees say and reached the general term.

$$x_n=C_1+C_2\left(\frac{-1}{2}\right)^n$$
$$x_0=C_1+C_2$$
$$x_1=C_1-\frac{C_2}{2}$$
Solving the two equations
$$C_1=\frac{x_0+2x_1}{3}$$
$$C_2=\frac{2}{3}(x_0-x_1)$$
Hence, the general term is
$$x_n=\frac{x_0+2x_1}{3}+\left(\frac{-1}{2}\right)^n\frac{2}{3}(x_0-x_1)$$

Taking the limit gives the right answer.

@haruspex: You said that its analogous to a second order homogeneous ODE. The given problem is from a Calculus practice sheet so perhaps we were to use the analogy but then second order ODE is also not in my course. If I try to learn about second order ODEs, would it be enough for solving the given problem?

Thanks everyone for the help.

 

[haruspex]

If I try to learn about second order ODEs, would it be enough for solving the given problem?

It would probably have given you the clue to use such a method. It extends to higher orders, giving a polynomial. I think someone on this thread mentioned characteristic polynomials. It only handles relatively simple cases. E.g. it won't cope with a_n = n a_n-1 + a_n-2, but the general idea of guessing a form of solution obviously applies.

 

[vanhees71]

The logic is as follows.

You have given the recursive definition of the sequence by
$$x_{n+1}=\frac{x_{n-1}+x_{n}}{2}.$$
Each series is uniquely determined by the initial conditions of the recursion, i.e., the two values of $x_0$ and $x_1$.
With two sequences $x_n$ and $y_n$ also
$$z_n=\lambda_1 x_n + \lambda_2 y_n$$
fulfills the recursion relation for all numbers $\lambda_1$ and $\lambda_2$, because it is linear.

This means the sequences of the kind defined by the recursion build a vector space in the vector space of sequences. Since each series is uniquely determined by the first two values, this vector space is two-dimensional. So if you find two linearly independent solutions of the recursion, you know all of the sequences, because you can build them as linear combinations of these two independent solutions. As you have seen, there are two independent solutions, namely $a_n=1$ and $b_n=(-1/2)^n$. Thus any sequence fulfilling the recursion relation must be of the form
$$x_n=\lambda_1 a_n+ \lambda_2 b_n=\lambda_1+\lambda_2 (-1/2)^n.$$
You have also seen, how to map given initial conditions $x_0$, $x_1$ to the corresponding $\lambda_1$ and $\lambda_2$, and now since you have the solution of your initial-value recursion equation, you can easily determine the limit.

 

[Saitama]

It would probably have given you the clue to use such a method. It extends to higher orders, giving a polynomial. I think someone on this thread mentioned characteristic polynomials. It only handles relatively simple cases. E.g. it won't cope with a_n = n a_n-1 + a_n-2, but the general idea of guessing a form of solution obviously applies.

Thanks haruspex!

I guess I will have to learn about the recursions then. Do you have some good suggestions from where I can learn about this? None of the books I have deal with them.

The logic is as follows.

You have given the recursive definition of the sequence by
$$x_{n+1}=\frac{x_{n-1}+x_{n}}{2}.$$
Each series is uniquely determined by the initial conditions of the recursion, i.e., the two values of $x_0$ and $x_1$.
With two sequences $x_n$ and $y_n$ also
$$z_n=\lambda_1 x_n + \lambda_2 y_n$$
fulfills the recursion relation for all numbers $\lambda_1$ and $\lambda_2$, because it is linear.

This means the sequences of the kind defined by the recursion build a vector space in the vector space of sequences. Since each series is uniquely determined by the first two values, this vector space is two-dimensional. So if you find two linearly independent solutions of the recursion, you know all of the sequences, because you can build them as linear combinations of these two independent solutions. As you have seen, there are two independent solutions, namely $a_n=1$ and $b_n=(-1/2)^n$. Thus any sequence fulfilling the recursion relation must be of the form
$$x_n=\lambda_1 a_n+ \lambda_2 b_n=\lambda_1+\lambda_2 (-1/2)^n.$$
You have also seen, how to map given initial conditions $x_0$, $x_1$ to the corresponding $\lambda_1$ and $\lambda_2$, and now since you have the solution of your initial-value recursion equation, you can easily determine the limit.

Thanks for the effort you have put in explaining this but its too technical for me. I have no idea what a "vector space" is.

I know what a vector is, is "vector space" something complicated?