Limit of sequence in which each term is defined by the average of preceding two terms

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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

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

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

I came to this page because I wanted to justify the formula I came up with for the series with x_n = px_n-1+(1-p)x_n-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 rx₁+(1-r)x₀. Let's simplify things by using x₀=0 and x₁=1. Then x₂=p. We must also have rx₂+(1-r)x₁ as the solution. Taking rx₂+(1-r)x₁ = rx₁+(1-r)x₀ 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 rx_n + (1-r)x_n-1 = rx_n-1 + (1-r)x_n-2. Just substitute for x_n and r and combine terms. By induction, this means that rx_n + (1-r)x_n-1 = rx₁ + (1-r)x₀. As was done in a previous post, we can take x_n-1 on the left side to equal x_n, which proves our assertion provided we have convergence. To find where we have convergence, use the expression for x_n to show that x_n - x_n-1 = -(1-p)(x_n-1 - x_n-2), giving convergence when |1-p| < 1.

Answer 13

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