What's the rationale behind rejecting limits of recurrence relation?

Question

I found this problem in Understanding Analysis by Stephen Abbott.

Define a recurrence relation as $x_1=3$ and $x_{n+1}=\frac{1}{4-x_n}$. Find the limit of the sequence $(x_n)$.

There are other parts to the question, but what I want to ask is: why do we reject a limit and not another when solving for the limit? If $(x_n) \rightarrow L$, it is not too hard to show that $(x_{n+1}) \rightarrow L$. Thus we can take the limit of both sides of $x_{n+1}=\frac{1}{4-x_n}$ to get $L=\frac{1}{4-L}$. We can solve for $L$ to get $L=0.268$ or $L=3.732$. My question is why $L=0.268$ is the answer, and not $3.732$. Is there any significance behind $3.732$ popping out here?

Logically, we can conclude that $x_n$ is strictly decreasing and reject $3.732$ on the basis that it is greater than $x_1$, but is that a valid reason though? What about sequences whose behaviour is neither monotone decreasing/increasing? How do we tell if a particular limit we solved for is correct or wrong?

Answer 1

Yes, we can reject limit for other reason. After all, the relation $L=1/(4-L)$ is merely a necessary condition, not a sufficient one.

It is plausible that the limit is actually $3.732\dotso$ instead, had you pick a different starting point (for example, if you start at $3.732\dotso$).

These limit are fixed points of the recurrent relation. Some fixed point are attractive, and some are not, so it depends on the situation.

For this kind of recurrent relation, a well-known method is known to solve exactly for the sequence. Consider $y_{i}=x_{i}-L$. Then \begin{align} &y_{i+1}=x_{i+1}-L=\frac{1}{4-x_{i}}-L=\frac{1-4L+Lx_{i}}{4-x_{i}}=\frac{1-4L+L^{2}+Ly_{i}}{4-L-y_{i}}=\frac{Ly_{i}}{4-L-y_{i}} \\ &\qquad\qquad\implies \frac{1}{y_{i+1}}=\frac{4-L-y_{i}}{Ly_{i}}=\left(\frac{4}{L}-1\right)\frac{1}{y_{i}}-\frac{1}{L} \\ &\qquad\qquad\implies \frac{1}{y_{i+1}}-\left(\frac{4}{L}-1\right)\frac{1}{y_{i}}=-\frac{1}{L}. \end{align} Write $z_{i}=\frac{1}{y_{i}}$ and we have $$z_{i+1}-\left(\frac{4}{L}-1\right)z_{i}=-\frac{1}{L}.$$ This is now a standard first order inhomogeneous linear recurrent relation and can be solved exactly, and from there you can figure out precisely whether the original sequence converge to $L$ or not by checking whether $|z_{i}|$ go to infinity.

EDIT: let me add in that it's easy to see from the recurrent relation for $z_{i}$ exactly how the sequence behave in the limit without solving exactly for $\{z_{i}\}$. If you pick $L=3.732\dotso$ then $\frac{4}{L}-1<1$ so it is impossible for $|z_{i}|$ to go to infinity, because when $|z_{i}|$ is sufficiently large then $$|z_{i+1}|=\left|\left(\frac{4}{L}-1\right)z_{i}-\frac{1}{L}\right|<|z_{i}|.$$ So it's impossible for any starting point other than $3.732\dotso$ itself to reach there (the argument doesn't apply for that starting point because then $z_{i}$ are undefined), this fixed point is unstable. But for $L=0.268\dotso$ then $\frac{4}{L}-1$ is large, so for almost all values of $z_{i}$ it should blow up.

Answer 2

A way to reason could be this. First you prove some kind of monotony, by induction. For instance, your sequence looks decreasing to me, Then prove that it is limited from below, that is it can’t go to $- \infty$ (easy to check in your case).

You know that every monotone sequence admits a limit, which can be infinite, but we’ve ruled out that possibility. Call that limit $l$ and for $n \to \infty$ you have $l=\frac{1}{4-l}$. Note that here you are using the continuity of the function $\frac{1}{4-x}$ in the point $l$, since it is discontinuous only in $4$ and you know $l \leq 3$. Now find $l$, and as you can see by yourself there is only one admissible solution, and 3,732 can’t be the answer because of the fact the sequence is decreasing and starting from 3.

A good exercise would be to study how are these “equilibrium points”. I mean, if you start at $l$ equal the other solution, it is obvious you have a fixed point, but... what about points near it? If you start from there, what happens, where do you end up? Try to think about this

Answer 3

Suggestion: Start using technology to actually compute some values for problems like this, and using that to build up intuition about what the process or sequence is doing. Admittedly this is not a core traditional technique in analysis, but I always worked this way through my schooling, and I felt like it put me a step or two ahead of my classmates. Of course it's not a deductive proof, but the intuition should put you on track to answering a number of questions like you posed here yourself.

This could be done with a simple program or a spreadsheet. In this case, the following took about 20 seconds to generate in an open-source spreadsheet:

Answer 4

For iterations of $f(x) = \frac{1}{4-x}$, we can identify the fixed points by setting $x=f(x)$ and solving for $x$. There are two solutions as you have identified, $2 - \sqrt{3}$ and $2 + \sqrt{3}$.

But $2 - \sqrt{3}$ is a stable solution and $2 + \sqrt{3}$ is unstable.

For a one dimensional discrete dynamical system, stability is determined by the magnitude of the derivative at the fixed point. If the magnitude is less than 1, the fixed point is stable, and greater than 1 is unstable. $f'(x) = \frac{1}{(4-x)^2}$, so

$f'(2 - \sqrt{3}) \approx 0.0718 $

$f'(2 + \sqrt{3}) \approx 13.93 $

and therefore the first fixed point is stable and the second is unstable.

Now for discrete dynamical systems it can be a little tricky. There could be higher order cycles, or there could be multiple stable fixed points. In that situation you would need to use the initial condition $(x_1 = 3)$ to identify which fixed point or cycle the iteration converges to. But it cannot converge to the unstable fixed point unless the iteration starts there.

Answer 5

I think the real answer to your inquiry is not in the specific details about limits at all. You wrote (emphasis mine):

Why do we reject a limit and not another when solving for the limit? If $(x_n)→L$, it is not too hard to show that $(x_{n+1})→L$. [...] We can solve for $L$ to get $L=0.268$ or $L=3.732$. My question is why $L=0.268$ is the answer, and not $3.732$.

Consider a completely different question with the same underlying logical misunderstanding:

If $x$ is a real such that $x = \sqrt{x+2}$, then $x^2 = x+2$ and so $(x+1)·(x-2) = 0$, which implies $x=-1$ or $x=2$. Why do we reject $x=-1$?

The answer is not that $\sqrt{x+2}$ is only defined when $x+2 ≥ 0$, because we could very well define square-root for all complex numbers and still face the same issue since $-1 ≠ \sqrt{-1}$.

The answer is that if you want to find some object $X$ that satisfies some property $P$, it is often easier to logically deduce some other simpler property $Q$ that such an $X$ must satisfy, so that you can then check all the objects satisfying $Q$ to see which ones satisfy $P$. This comprises 2 steps, firstly proving $∀X ( P(X) ⇒ Q(X) )$ and secondly checking every $X$ such that $Q(X)$ to see whether $P(X)$ or not.

I hope it is now clear that your inquiry actually has nothing to do with limits, and it is very important that you understand the logical nature of "solving equations", because it is not restricted to limits.

That said, here is another limit-related example:

Define $x_n = (-1)^n$ for every natural $n$. If $\lim_{n→∞} x_n = L$, then $\lim_{n→∞} x_{n+1} = L$, but $\lim_{n→∞} x_{n+1} = \lim_{n→∞} -x_n = -L$, and hence $L = -L$, which implies $L = 0$. Yea?