1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Given sequence - finding the limit

  1. Nov 6, 2013 #1
    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.
    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. jcsd
  3. Nov 6, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.)
  4. Nov 6, 2013 #3
    I am not sure what you mean but do you ask me to do this: ##x_n=A\lambda^n##?
  5. Nov 6, 2013 #4
    Suppose A is the cf of x0 and B is the cf of x1.

    Hint: if n is odd then

    [tex]A =\frac{2^{n-1}-1}{3}[/tex]

    [tex] B=2^{n-1} -A [/tex]
  6. Nov 6, 2013 #5
    How do you get those? :confused:

    I honestly can't catch the pattern for even ones. :(
  7. Nov 6, 2013 #6
    Hint: [tex] A+B=2^{n-1} [/tex]
  8. Nov 6, 2013 #7


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
  9. Nov 7, 2013 #8
    I honestly don't understand what your statements mean. What is this "recurrence" thing? I have never heard of anything like that. :uhh:
  10. Nov 7, 2013 #9


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    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
    This you plug into your recursion relation and see, whether you can find two different values for [itex]\lambda[/itex].

    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 [itex]x_0[/itex] and [itex]x_1[/itex].
  11. Nov 7, 2013 #10
    Is there any way to solve the problem using elementary techniques? I have never seen words like "vector spaces" and "recursion" in my course.
  12. Nov 7, 2013 #11


    User Avatar
    Homework Helper

    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 [itex]x_0[/itex] and [itex]x_1[/itex] you can calculate [itex]x_3[/itex], [itex]x_4[/itex], etc.

    The method of solving linear recurrence relations with constant coefficients is based on the fact that for any [itex]A[/itex], [itex]x_n = A \lambda^n[/itex] 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 [itex]A[/itex], [itex]x(t) = Ae^{\lambda t}[/itex] is a solution of
    \dot x = \lambda x
    and in practice is largely identical: you solve a polynomial for [itex]\lambda[/itex] which gives you your complementary functions, and the general solution is a linear combination of these.
  13. Nov 7, 2013 #12
    Last hint:

    [tex]x_n = \frac{x_0 + 2x_1}{3} + \left( \frac{-1}{2} \right)^n \left(\frac{2}{3} \right) (x_0-x_1)[/tex]
  14. Nov 7, 2013 #13
    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.
  15. Nov 7, 2013 #14
    1) Set up the characteristic equation: [tex] 2\lambda^2 -\lambda -1 =0[/tex]
    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.
  16. Nov 7, 2013 #15


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
  17. Nov 7, 2013 #16
    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
  18. Nov 8, 2013 #17
    Okay, I substitute the values as you say.
    $$x_0=A\lambda^0 \Rightarrow A=x_0$$
    $$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$$
    Solving for ##\lambda## I get two values, -1/2 and 1.
    So I have
    I have no idea about what I am doing. :confused:
  19. Nov 8, 2013 #18
    No, [tex] x(n) = C1 \cdot \lambda_1^n +C1 \cdot \lambda_2^n [/tex]
    since a linear combination of a solution is also a solution.
  20. Nov 8, 2013 #19
    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
  21. Nov 8, 2013 #20


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    Of course it must read
    [tex]x_n=C_1 \lambda_1^n + C_2 \lambda_2^n=C_1+C_2 (-1/2)^n.[/tex]
    Now you can determine [itex]C_1[/itex] and [itex]C_2[/itex] from the initial condition of the recursion, i.e.,
    [tex]x_0=C_1+C_2, \quad x_1=C_1-\frac{C_2}{2}.[/tex]
    Then it's pretty easy to get the limit
    [tex]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[/tex]
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Given sequence - finding the limit
  1. Limit of a Sequence (Replies: 18)

  2. Limits and Sequences (Replies: 8)

  3. Limit of a Sequence (Replies: 1)