# A Thought on Recursive Sequences

In working on coursework I had a thought about recursive sequences. For monotone. bounded, recursive sequences $(x_n)$ , $\lim_{n\to\infty}(x_n)$ seems to equal the point where the differences in terms is zero (i.e. $x_n-x_{n+1}=0$). On brief consideration it seems to stand to reason - the term difference is essentially the rate of change of the sequence, a monotone sequence must be changing in the same direction for all terms. Thus, the sequence should tend toward the point where the next term would be larger if the sequence got there, but never quite actually get there. Hence, the limit.

I would like to ask: is this a known result? If so, does the theorem have a name? If not, where can one poke holes in the claim?

-
As an example, suppose that $x_{n+1}=F(x_n)$. Then, under suitable conditions, the limit of $(x_n)$ is a fixed point of the function $F$, that is, a point $a$ such that $F(a)=a$. That term is standard. I do not know of a specific additional name for the result. –  André Nicolas Oct 6 '11 at 2:02
@andre those are types of sequences that I led me to this thought. Probably just jumped the gun on something later in the course, but it would be cool if that property had a name. None as far as you know? Also, what are the suitable conditions? –  Drew Christianson Oct 6 '11 at 2:39
It sort of has a name, the fixed point property. Your conditions (monotone, bounded) together with continuity of $F$ will do it. We don't really need monotone. Asking that $F$ be differentiable with $|F'(x)|<c<1$ will do. The recurrence need not be first-order. For example, $x_{n+1}=F(x_{n},x_{n-1})$ with $F$ nice enough will do. There is a large literature, since the subject is strongly associated with root-finding techniques. –  André Nicolas Oct 6 '11 at 2:54

There are many results to the effect that under suitable conditions on $F$, if the sequence $(x_n)$ satisfies a recurrence of the shape $x_{n+1}=F(x_n)$, then $\lim_{n\to\infty}x_n$ exists and is equal to a solution of the equation $F(x)=x$, or in other words that the limit is a fixed point of $F$. This is true, for example, if $F$ is differentiable and $|F'(x)|$ is (say) everywhere $<0.9$.
Given the recurrence $x_{n+1}=F(x_n)$, where $F$ is continuous, $\lim_{n \to \infty} x_n$, if it exists, must be a fixed point of $F$. So a common first step in finding the limit is to find the fixed points of $F$. However, we still need to show that the limit exists. The following is a simple illustrative example. Let $x_{n+1}=F(x_n)=-x_n^2$. The fixed points of $F$ are $x=0$ and $x=-1$. If $x_0=1/2$, the sequence $(x_n)$ has a limit, which must be one of the fixed points of $F$. But we cannot use fixed points to "find" the limit if $x_0=-2$.