Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  J. M. Nov 15 '10 at 10:26
    
@Américo Tavares: not really. Even once you've shown that a limit exists, a limit of 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. –  Qiaochu Yuan Nov 15 '10 at 10:29
    
@Qiaochu Yuan: if you post your comment as an answer I will accept it. Thanks! –  Américo Tavares Nov 15 '10 at 10:34
    
@Yuval Filmus: Thanks for changing the tag for "recurrence-relations". Is it a new tag, an existing or a renamed ones? –  Américo Tavares Jun 3 '11 at 20:25
    
@Américo: I believe it's a new tag. We're trying to phase out the tag (recursive). –  Yuval Filmus Jun 3 '11 at 21:12
show 1 more comment

1 Answer

up vote 9 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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