11
$\begingroup$

For a sequence defined by a formula normally the usual limit rules allows one to find its limit. But for a sequence defined by a recurrence, up to now I have only seen some refined ad hoc methods, mostly in Problems.

The Trick explains that "There is one trick that is (...) first to prove that a limit exists, and then to use the recurrence to determine what the limit must be" illustrated by the example of the recurrence $ a_{n+1}=a_{n}/2+1/a_{n}$, $a_{0}=2$.

Question: Are there relatively general methods to find the limit of a sequence defined by a recurrence?

  • 0
    I would think it's more of "case-to-case basis"; for instance, fixed-point recurrences rarely have limits that can be found in closed form.2010-11-15

1 Answers 1

11

Not really. Even once you've shown that a limit exists, a limit of, say, $x_{n+1} = f(x_n)$ is the same as a fixed point of $f$, or a solution to $f(x) - x = 0$. Needless to say it does not make much sense to ask whether there are general methods to find solutions to equations. For example, one can write down solutions to differential equations as fixed points, and there are no general methods to solve differential equations.

In that sense all methods to find limits of recurrences are "ad hoc" in the same way that all methods to solve differential equations or Diophantine equations are "ad hoc." We do what we can.