Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Finding a Limit by Iterating a Function

Date: 04/21/2004 at 21:49:25
From: Matan
Subject: Determine the limit of f^n(x) for x > 0

Given:

f(x) = 2x/(x + 1)

        2                3         2          n         n-1
Define f (x) = f(f(x)), f (x) = f(f (x)),...,f (x) = f(f   (x))

                                                 n
Determine the limit as n approaches infinity of f (x) for x > 0.

I thought I should plug in the given f(x) into the first couple to see
if I noticed a pattern, and then use my limit taking knowledge to take
the limit.  Things got very confusing at that point!



Date: 04/22/2004 at 09:28:41
From: Doctor Vogler
Subject: Re: Determine the limit of f^n(x) for x > 0

Hi Matan,

That's a very good question.  What you are doing is called "iterating"
the function f(x).  In general, this is not a simple or easy thing to
do, and it is where fractals (the Mandelbrot and Julia sets) come
from.  However, a rational function of degree 1 (which is what you
have) is the only kind of rational function for which we can give an
*explicit* formula for f^n(x).  The trick lies in looking for the
fixed points.

Basically, we figure that if f^n(x) is going to approach a limit, and
that limit is y, then we would expect f of something really close to y
to be even closer to y, right?  So we should also expect

  f(y) = y.

So let's solve that equation:

  2y/(y+1) = y
  2y = y^2 + y
  0 = y^2 - y
  0 = y(y - 1)

which has two solutions, namely 0 and 1.  (You don't always get
integers, but I expect someone chose this problem for you so that you
would get integers.)  Now the secret is to move these points to 0 and
infinity.  So we use a transformation:

  h(x) = x/(x - 1)

which takes 0 to 0 and 1 to infinity.  This is what I mean by that: 
We define a completely new function by

  g(x) = h(f(h^-1(x)))

and it so happens (in this case) that h-inverse (h^-1) equals h (this
doesn't always happen either).  So then

  f(h(x)) = f(x/(x - 1))
          = 2[x/(x - 1)]/([x/(x - 1)] + 1)
          = 2x/(x + x - 1)
          = 2x/(2x - 1)

and

  g(x) = h(f(h(x)))
       = h(2x/(2x - 1))
       = [2x/(2x - 1)]/([2x/(2x - 1)] - 1)
       = 2x/(2x - (2x - 1))
       = 2x

You see, we will always get a function in a very simple form when we
transform the fixed points to 0 and infinity.  Now we know what g^n(x)
is, right?

  g^n(x) = (2^n)x

Well, notice that

  g(x) = h(f(h^-1(x)))

also implies that

  g^n(x) = h(f^n(h^-1(x))).

Do you see why?  (Induction will prove this.)  It also means that

  h^-1(g^n(h(x))) = f^n(x),

so that

  f^n(x) = h^-1(2^n * h(x))
         = h^-1(2^n * x/(x - 1))
         = [2^n * x/(x - 1)]/([2^n * x/(x - 1)] - 1)
         = (2^n * x)/(2^n * x - (x - 1))
         = (2^n * x)/((2^n - 1)*x + 1)

and now you have an explicit formula for f^n(x), which you might have
discovered by experimenting, although this technique that I described
will work for any rational function of degree 1, and which you could
easily prove by induction (if we had come up with this formula by some
less mathematical means), and whose limit you can now easily take,
especially if you write it as

  f^n(x) = 1/[1 - 2^(-n)*(x - 1)/x].

Of course, we already figured out right from the beginning that the
limit had to be either 0 or 1.  In fact, if you take the limit as n
goes to negative infinity (which is called backwards iterating), then
you will get 0.

If you have other questions or need more help, please write back, and
I will try to offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Functions

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/