90
$\begingroup$

We have a sequence of numbers $x_n$ determined by the equality

$$x_n = \frac{x_{n-1} + x_{n-2}}{2}$$

The first and zeroth term are $x_1$ and $x_0$.The following limit must be expressed in terms of $x_0$ and $x_1$ $$\lim_{n\rightarrow\infty} x_n $$

The options are:

A)$\frac{x_0 + 2x_1}{3}$ B)$\frac{2x_0 + 2x_1}{3}$

C)$\frac{2x_0 + 3x_1}{3}$ D)$\frac{2x_0 - 3x_1}{3}$

Since it was a multiple choice exam I plugged $x_0=1$ and $x_1=1$. Which means that all terms of this sequence is $1$,i.e, $$x_n=1, n\in \mathbb{N} $$

From this I concluded that option A was correct.I could not find any way to solve this one hence I resorted to this trick. What is the actual method to find the sequence's limit?

$\endgroup$
  • 72
    $\begingroup$ Your 'trick' was very smart, in the setting of a multiple choice exam. It makes it very easy to exclude options. But it is even smarter that you want to know the 'actual' method to solve this! $\endgroup$ – Pakk May 11 '17 at 15:32
  • 4
    $\begingroup$ @Pakk thanks for the compliment! $\endgroup$ – Ananth Kamath May 12 '17 at 2:21
  • 2
    $\begingroup$ @Pakk Hehe, me on those factoring problems back in ye olde days o' Algebra. Just plug $x=0$ in and you pretty much done... $\endgroup$ – Simply Beautiful Art May 27 '17 at 0:29

13 Answers 13

73
$\begingroup$

$$2x_n = x_{n-1} + x_{n-2}$$

$$2x_2 = x_{1} + x_{0}\\ 2x_3 = x_{2} + x_{1}\\ 2x_4 = x_{3} + x_{2}\\ 2x_5 = x_{4} + x_{3}\\ ...\\ 2x_n = x_{n-1} + x_{n-2}$$

Now sum every equation and get

$$2x_n+x_{n-1}=2x_1+x_0$$

Supposing that $x_n$ has a limit $L$ then making $n\to \infty$ we get:

$$2L+L=2x_1+x_0\to L=\frac{2x_1+x_0}{3}$$

$\endgroup$
  • 1
    $\begingroup$ What did you sum to arrive at $2x_n+x_{n-1}=2x_1+x_0$? When I summed the numbered equations, I got a proportion of $x_0$ and $x_1$, but not $2:1$, and summing the indexed equations was quite boring. $\endgroup$ – user121330 May 12 '17 at 22:40
  • 2
    $\begingroup$ @user121330: just those equations as written (equivalently, you can rewrite them bringing the RHS terms to LHS and negating them). Note that each (non-terminal) $x_i$ occurs once as $2x_i$ on the LHS, and twice as $x_i$ on the RHS. So they all cancel out except for the terminal ones. $\endgroup$ – smci May 12 '17 at 23:23
  • $\begingroup$ @user121330, look at the sums starting with $2x_2$. On the rhs $x_2$ appears twice, once on the line below and once again on the line below that. Cancelling out this way, you get the simplified expression. $\endgroup$ – PatrickT May 13 '17 at 14:48
  • $\begingroup$ I fondly remember this as exercise 3.5.10 of Bartle's and Sherbert's Introduction to Real Analysis, how my teacher solved it by finding an invariant as you did, and how I had wondered how she came up with it (she just said to 'play with it'). The nostalgia. $\endgroup$ – Vandermonde May 14 '17 at 22:27
  • 2
    $\begingroup$ No you're not summing to infinity. You're summing for LHS's from $x_2$ to $x_n$. That's finite. After you get that sum, we then apply the condition that if ${x_n}$ has a limit L as $n \to \infty$ then both $x_n, x_n+1 \to L$, and that sets up a useful equality involving $x_1, x_0$. $\endgroup$ – smci May 16 '17 at 6:40
40
$\begingroup$

Yet another trick: you can write the recurrence in matrix form: $$ \left(\begin{array}{c} x_n\\ x_{n-1} \end{array} \right) = \left(\begin{array}{cc} 1/2 & 1/2\\ 1 & 0\\ \end{array} \right) \left(\begin{array}{c} x_{n-1}\\ x_{n-2} \end{array} \right). $$ Then, $$ \left(\begin{array}{c} x_n\\ x_{n-1} \end{array} \right) = \left(\begin{array}{cc} 1/2 & 1/2\\ 1 & 0\\ \end{array} \right)^{n-1} \left(\begin{array}{c} x_1\\ x_0 \end{array} \right). $$ Diagonalizing/converting the matrix to the Jordan form, you can find a closed form for the sequence.

$\endgroup$
  • 4
    $\begingroup$ I wouldn't call it a trick, I think it's the most natural approach to these problems. And it justifies the method in Arnaud's answer. $\endgroup$ – Sasho Nikolov May 12 '17 at 19:11
31
$\begingroup$

First, notice that you can rewrite the recurrence relation as $$2x_{n+2}-x_{n+1}-x_n=0,\quad n\geq 0.$$ Now the key point is that this recurrence relation is linear, and thus if $(y_n)_{n\geq 0}$ and $(z_n)_{n\geq 0}$ satisfy this relation, then for any $\alpha,\beta\in \Bbb R$, $(\alpha y_n+\beta z_n)_{n\geq 0}$ will also satisfy it. So we can try to express $(x_n)$ as a linear combination of simpler sequences $(y_n)$ and $(z_n)$. An example of simple sequence would be a geometric sequence $y_n=r^n$ for some $r$. Can we find a sequence of this form satisfying the recurrence relation? $r$ would have to be such that $$2r^{n+2}-r^{n+1}-r^n=r^{n}(2r^2-r-1)=0,\quad n\geq 0,$$thus it is enough that $$2r^2-r-1=0.$$ This will hold if and only if $r\in \left\{1,\frac{-1}{2}\right\}$.

Thus we know that any sequence of the form

$$\alpha +\beta \left(\frac{-1}{2}\right)^n$$ satisfies our recurrence relation. Then it suffices to check that the first two term are the same, and all the others will follow. Thus you need to find $\alpha,\beta$ such that $$\left\{ \begin{array}{}\alpha+\beta & = & x_0\\ \alpha-\frac{\beta}{2} & = & x_1.\end{array} \right. $$

This is a simple linear system, whose solution is given by $\alpha=\frac{x_0+2x_1}{3}$ and $\beta=\frac{2x_0-2x_1}{3}$.

Thus the $n$-th term must be given by $$x_n=\frac{x_0+2x_1}{3}+\frac{(2x_0-2x_1)(-1)^{n}}{3\cdot 2^n}$$ and thus $\lim_{n\to \infty }x_n = \frac{x_0+2x_1}{3}$.


This method works for a large variety of cases; in fact, it can be applied to give a formula for $x_n$ for any linear recurrence relations (there are some difficulties if the corresponding polynomial equation has multiple roots, because you don't get enough geometric sequences, but you can find other solutions in those case). For example, you can apply the same method to the Fibonacci sequence, and it gives you the Binet formula (you can find more details in the answers to this question).

$\endgroup$
  • $\begingroup$ How can we come to the conclusion that $x_n = r^n$ ? Thanks for answering by the way. $\endgroup$ – Ananth Kamath May 11 '17 at 14:19
  • $\begingroup$ We can't. It's more "wishful thinking". Maybe I can explain that better. $\endgroup$ – Arnaud D. May 11 '17 at 14:22
  • $\begingroup$ It does makes sense, but I believe such an approach is only good for this particular question? $\endgroup$ – Ananth Kamath May 11 '17 at 14:30
  • 7
    $\begingroup$ @AnanthKamath No, it's a general method for linear recurrence relations. You can find more information for example at en.wikipedia.org/wiki/… $\endgroup$ – Arnaud D. May 11 '17 at 14:44
  • $\begingroup$ I never knew that was possible. Thanks for sharing info. $\endgroup$ – Ananth Kamath May 11 '17 at 14:58
21
$\begingroup$

Here's yet another way to look at the problem, that might not lead directly to a proof, but might give intuitive insight into the sequence.

Note that from $x_0$, we go $x_1-x_0$ up to $x_1$, then $\frac12(x_1-x_0)$ down to $x_2$, then $\frac14(x_1-x_0)$ up to $x_3$, etc. You might be able to prove this by induction, but might not want to. If $x_0=0$ and $x_1=1$, one can put this in a picture: ($A=(0,x_0)$, $B=(1,x_1)$, ...)

half-powers plot

We conclude that, since the jump from $x_0$ to $x_1$ can really be seen a a jump of $1=(-1/2)^0$ relative to $x_0$:

$$x_n = x_0 + (x_1-x_0)\sum_{i=0}^{n-1} \left(-\frac12\right)^i$$

Then the limit for $n \rightarrow \infty$ is:

$$\lim_{n\rightarrow\infty} x_n = x_0 + (x_1-x_0)\sum_{i=0}^\infty \left(-\frac12\right)^i = x_0 + (x_1-x_0)\frac1{1+\frac12}$$

by the geometric series (since $\lvert-\frac12\rvert < 1$). Then this is equal to:

$$\begin{align*} x_0 + (x_1-x_0)\frac1{1+\frac12} &= x_0 + \frac23(x_1-x_0) = \frac{3x_0+2x_1-2x_0}3 \\ &= \frac{x_0 + 2x_1}3. \end{align*}$$

$\endgroup$
  • 3
    $\begingroup$ Can't we upvote an answer twice? :) $\endgroup$ – Kartik May 12 '17 at 10:26
  • 1
    $\begingroup$ This is what Soumik did in his answer. Unfortunately he did not feel like working it out. $\endgroup$ – Carsten S May 12 '17 at 12:39
  • $\begingroup$ @CarstenS Oh right I see; luckily I wasn't the only one to see this :) $\endgroup$ – tomsmeding May 12 '17 at 16:29
  • $\begingroup$ Yes, +1 for the illustration. $\endgroup$ – Carsten S May 12 '17 at 16:31
17
$\begingroup$

$$x_n-x_{n-1}=-\frac{1}{2}(x_{n-1}-x_{n-2})$$ use repeatedly to get $$x_n-x_{n-1}=(-\frac{1}{2})^{n-1}(x_{1}-x_{0})$$ Now it is fairly straightforward to compute

$\endgroup$
  • 3
    $\begingroup$ Could you show a little more work on how you got to your first step? $\endgroup$ – AlgorithmsX May 11 '17 at 19:04
  • 1
    $\begingroup$ subtract $x_{n-1}$ from both sides of the equation and iterate. $\endgroup$ – user379195 May 11 '17 at 19:05
  • 2
    $\begingroup$ I know how you got there, but I think it's better for you to show some less obvious intermediate steps. It's still a great post. $\endgroup$ – AlgorithmsX May 11 '17 at 19:08
11
$\begingroup$

Here is a way to find the general solution of the recurrence using generating functions and then find the limit. We wish to solve the recurrence $$ a_n = \frac{a_{n-1}}{2} + \frac{a_{n-2}}{2}\quad (n\geq 2)\tag{1} $$ where $a_0=x_0$ and $a_1=x_1$. We first make the recurrence valid for all $n\geq 0$. To this end, set $a_n=0$ for $n<0$ and note that the recurrence $$ a_n = \frac{a_{n-1}}{2} + \frac{a_{n-2}}{2}+x_0\delta_{n,0}+(x_1-x_0/2)\delta_{n,1}\tag{2} $$ where $\delta_{ij}$ is the Kronecker Delta does the trick. Let $A(x)= \sum_{n=0}^\infty a_nx^n$ be the generating function and multiply by $x^n$ and sum on $n$ in (2). Then we get $$ A(x)\left(1-\frac{1}{2}x-\frac{1}{2}x^2\right)=x_0+x\left(x_1-\frac{x_0}{2}\right)\tag{3} $$ and hence $$ A(x) =\frac{x_0+(x_1-x_0/2)x}{1-\frac{1}{2}x-\frac{1}{2}x^2} =\frac{x_0+(x_1-x_0/2)x}{(1-x)(1+x/2)} =\frac{2x_1+x_0}{3(1-x)}+\frac{2x_0-2x_1}{3(1+x/2)}\tag{4} $$ by partial fractions. By using the geometric series we get that $$ \begin{align} A(x) &=\sum_{n=0}^\infty \left[\frac{2x_1+x_0}{3}\right]x^n+ \sum_{n=0}^\infty \left[\frac{2x_0-2x_1}{3}\right]\left(\frac{-x}{2}\right)^n\\ &=\sum_{n=0}^\infty \left[\frac{(2x_1+x_0)}{3}+\frac{(2x_0-2x_1)(-1)^n}{3(2^n)}\right]x^n\tag{5} \end{align} $$ Hence

$$a_n=\frac{x_0+2x_1}{3}+\frac{(2x_0-2x_1)(-1)^{n}}{3\cdot 2^n}\tag{6}$$ and thus $$\lim_{n\to \infty }a_n = \color{blue}{\frac{x_0+2x_1}{3}.}\tag{7}$$

$\endgroup$
9
$\begingroup$

Here is a formal derivation of your result. The sequence you have found is a generalization of the Fibonacci sequence.

There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas, and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$; available at http://ms.appliedprobability.org/data/files/Articles%2040/40-3-2.pdf.)

We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show that

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n) $$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.

The result is written in this form to underscore that it is the sum of a Fibonacci-type and Lucas-type Binet-like terms. It will also reduce to the standard Fibonacci and Lucas sequences for $a=b=1 \ \text{and} \ f_0=0, f_1=1$. Notice that there is nothing in this derivation that limits the results to integer values for the initial conditions, scaling factors, or the sequence itself.

So, specializing to your case, we can say

$$x_n=\frac{x_{n-1}}{2} +\frac{x_{n-2}}{2}$$

and

$$\alpha,\beta=\frac{\frac{1}{2}\pm\sqrt{\frac{1}{4}+2}}{2}=1,\frac{1}{2}$$

For the limit as $n\to\infty$, we note that the $\alpha$-term dominates, and is in fact, always unity, ergo

$$ \lim_{n\to\infty} x_n=\left(x_1-\frac{x_0}{4}\right)\frac{\alpha^n}{\alpha-\beta}+\frac{x_0}{2}\alpha^n=\left(x_1-\frac{x_0}{4}\right)\frac{2}{3}+\frac{x_0}{2}=\frac{2x_1+x_0}{3} $$

as was shown previously.

This proves the OP's assertion. The advantage of this method is that it will apply to all such problems.

$\endgroup$
9
$\begingroup$

Start with:

$$ x_n = \frac{x_{n-1}+x_{n-2}}{2} $$

Add $\frac{x_{n-1}}{2}$ to both sides:

$$ \frac{2x_{n}+x_{n-1}}{2} = \frac{2x_{n-1}+x_{n-2}}{2} $$

Let $y_{n} = \frac{2x_{n}+x_{n-1}}{2}$:

$$ y_{n} = y_{n-1} = \ldots = y_{1} $$

As $n \rightarrow \infty, x_{n-1} \rightarrow x_{n}$, so:

$$ \frac{3x_{n}}{2} = \frac{2x_{1}+x_{0}}{2} $$

Note that this is the "same" approach as some of the other answers, I just added it because it is most clear to me.

$\endgroup$
7
$\begingroup$

Unless $x_0=x_1$ which is clear, consider the tranformation $y_n:=\frac{x_n-x_0}{x_1-x_0}$. Then $y_0=0$, $y_1=1$, and $y_{n+1}$ is the average of $y_n$ and $y_{n-1}$. It is clear that $\lim y_n$ is $$ \frac{1}{2}+\frac{1}{4}-\frac{1}{8}+\frac{1}{16}-\frac{1}{32}+\cdots=\frac{1}{2}\left(1+\frac{1}{4}+\frac{1}{16}+\cdots\right)=\frac{2}{3}. $$ Going back, you have $\lim x_n=\frac{1}{3}(x_0+2x_1)$.

$\endgroup$
  • 1
    $\begingroup$ This was my instant reaction to the problem, comparison with the binary number given by 0.101010101010... which is 2/3. $\endgroup$ – richard1941 May 16 '17 at 18:10
6
$\begingroup$

My solution:

Map $[x_0,x_1]$ to $[0,1]$ by setting $x = x_0 + (x_1-x_0)y$ so that $y_0 = 0$ and $y_1 = 1$.

Now the sequence runs $0, 1, \frac{1}{2}, \frac{3}{4}, \frac{5}{8}, \frac{11}{16}$, etc

Take the difference between each successive term i.e. $y_k-y_{k-1}$

You get $+1, -\frac{1}{2}, +\frac{1}{4}, -\frac{1}{8}, +\frac{1}{16}$, etc

This looks like the expansion of $\frac{1}{1-z}$ for $|z|<1$ i.e. $1+z+z^2+z^3+...$

In our case, $z = -\frac{1}{2}$, so the sum is $\frac{1}{1-(-1/2)} = \frac{2}{3}$

So the limit of $y_k$ is $\frac{2}{3}$, given $y_0 = 0$ and $y_1 = 1$. So now map back to $x$

$x = x_0 + (x_1-x_0)\frac{2}{3} = \frac{x_0 + 2x_1}{3}$

$\endgroup$
  • $\begingroup$ Use this link to know how to write mathematics on this site. $\endgroup$ – StubbornAtom May 14 '17 at 10:25
  • $\begingroup$ Apologies, have used the maths editor on the site before but this was from my phone, so it's not particularly easy to do. Appreciate the edit, meant to follow up this evening with the same. Best, james $\endgroup$ – James Spencer-Lavan May 14 '17 at 10:44
6
$\begingroup$

Since the recurrence relation is linear, the sequence's limit is, if it exists, of the form $ax_0+bx_1$. If you consider the sequence $x'_n=x_{n+1}$, it clearly has the same limit therefore $$ax_0+bx_1=ax'_0+bx'_1=ax_1+bx_2=ax_1+\frac b2(x_0+x_1)=\frac{b}2x_0+\left(a+\frac b2\right)x_1.$$ Since this is true for any $x_0$, $x_1$, we have $a=\frac b2$ (and also $b=a+\frac b2$ but this is equivalent). This is enough to answer the question, but not to find $a$ and $b$. To find $a$ and $b$, you can simply take the same trick you used by considering the constant sequence $1$ and you get $a+b=1$, which solves the problem.

$\endgroup$
3
$\begingroup$

I came to this page because I wanted to justify the formula I came up with for the series with xn = pxn-1+(1-p)xn-2. This is more general than the original problem, though not as general as the linear combination problem. Based on what I read here, I can show the solution and justify it using just a little insight and basic algebra. The first insight is to assume the solution has the form rx1+(1-r)x0. Let's simplify things by using x0=0 and x1=1. Then x2=p. We must also have rx2+(1-r)x1 as the solution. Taking rx2+(1-r)x1 = rx1+(1-r)x0 and substituting gives p=(1-r)+rp. Solving for r gives r =1/(2-p) and (1-r) = (1-p)/(2-p). Having found the solution to the problem, we need to justify it. It is straightforward, though a little tedious, to show that, for the value of r that we found, that rxn + (1-r)xn-1 = rxn-1 + (1-r)xn-2. Just substitute for xn and r and combine terms. By induction, this means that rxn + (1-r)xn-1 = rx1 + (1-r)x0. As was done in a previous post, we can take xn-1 on the left side to equal xn, which proves our assertion provided we have convergence. To find where we have convergence, use the expression for xn to show that xn - xn-1 = -(1-p)(xn-1 - xn-2), giving convergence when |1-p| < 1.

$\endgroup$
  • $\begingroup$ There is a simpler approach for finding r. Find a and b such that ax<sub>n</sub>+bx<sub>n-1</sub>=ax<sub>n-1</sub>+bx<sub>n-2</sub>. The constraints for x<sub>n-1</sub> are the same as for x<sub>n-2</sub>, giving b=a(1-p). What we need to realize is that if a and b satisfy the equation, so do ta and tb. We need the additional constraint of a+b=1. Then things work out very simply. $\endgroup$ – user1153980 Nov 12 '17 at 10:10
2
$\begingroup$

First, the sequence $(x_n)$ has clearly a limit $\ell$ because $$ \left|x_{n+1}-x_{n}\right|=\frac{|x_1-x_0|}{2^n}. $$ Now, sum the $n-1$ equations $2x_{i+2}=x_{i+1}+x_i$ for $i=0,1,\ldots,n-2$ and we obtain $$ 2x_n+x_{n-1}=2x_1+x_0. $$ Passing to the limit we reach $$ \ell=\frac{2x_1+x_0}{3}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.