Applications of Iteration

In one sentence

Many processes apply the same map again and again: shrinking a map, computing the next term of a recurrence, replacing a number by the sum of the squares of its digits… Write it as $x_{n + 1} = f (x_{n})$ , and the question becomes “where does the orbit of $f$ go?” Three keys:

Fixed points: if an orbit comes to rest, it can only rest at a point with $f (x) = x$ .
Shrinking: if each step multiplies the distance to the fixed point by a number less than $1$ , the orbit is certain to be pulled in.
Finiteness: if the orbit can only take finitely many values, sooner or later one repeats, and from then on it cycles.

Some point of the big map lies exactly on top of the point that represents it on the small map

Step 1 / 5

Write the correspondence as a map
A point $z$ of the big map is represented on the small map by $T (z)$ . The small map is the big one shrunk by $k$ , turned through $θ$ and moved to $p$ , so $T (z) = p + k e^{i θ} z$ (points of the plane written as complex numbers).

$T (z) = p + k e^{i θ} z$
Distances shrink by k
Iterate: maps inside maps
That point is the fixed point
Uniqueness

Predict first

Shrink the map by half, do not turn it, and place it inside the original: $T (x, y) = (\frac{x}{2} + 4, \frac{y}{2} + 2)$ . What is the $x$ -coordinate of the fixed point?

Choose an answer first; then you can see the result.

Stop 1 · Sequences: the limit of an orbit

$a_{1} = 0$ , $a_{n + 1} = 2 + a_{n}$ . This is the orbit of $f (x) = x + 2$ starting from $0$ .

Press “Iterate once”: the staircase climbs from bottom left to top right, its steps getting lower and lower, squeezing toward the fixed point

2

To make “it tends to $2$ ” precise, take two steps:

The candidate: if the limit $L$ exists, then $L = L + 2$ , so $L = 2$ (the negative root is rejected).
It really goes there: $2 - a_{n + 1} = 2 - 2 + a_{n} = \frac{2 - a _{n}}{2 + 2 + a _{n}}$ . The denominator is at least $2 + 2 > 2$ , so the distance to $2$ at least halves at every step: $0 \leq 2 - a_{n} \leq \frac{2}{2 ^{n - 1}} \to 0$ .

The second step is the same idea as the proof about maps: shrinking.

Stop 2 · Number theory: finite means it cycles

Replace a positive integer by the sum of the squares of its digits, and call the result $S (n)$ . For example $S (32) = 9 + 4 = 13$ , $S (13) = 10$ , $S (10) = 1$ , $S (1) = 1$ : the orbit of $32$ stops at the fixed point $1$ . But $S (4) = 16$ , $S (16) = 37$ , …: starting from $4$ you never reach $1$ .

Why every orbit ends up in a cycle

Step 1 / 4

Big numbers get smaller
If $n$ has $d \geq 4$ digits, then $S (n) \leq 81 d$ , while $n \geq 1 0^{d - 1}$ . For $d \geq 4$ , $81 d < 1 0^{d - 1}$ , so $S (n) < n$ .

$d \geq 4 : S (n) \leq 81 d < 1 0^{d - 1} \leq n$
Falling into a finite range
Finite + iteration ⇒ cycle
In fact there are only two endings

Stop 3 · Functional equations: finding a fixed point inside $f (f (x))$

Example. $f : R \to R$ satisfies $f (f (x)) = x^{2} - x + 1$ . Find $f (1)$ .

Notice that $x = 1$ is a fixed point of $x^{2} - x + 1$ . The iteration idea: apply $f$ once more. Then $f (f (f (x)))$ can be computed in two ways:

f (f (f (x))) = f (x^{2} - x + 1) and also = f (x)^{2} - f (x) + 1.

Put $x = 1$ and write $a = f (1)$ : the left side is $f (1) = a$ , the right side is $a^{2} - a + 1$ . So $a^{2} - 2 a + 1 = 0$ and $a = 1$ .

Practice

Exercise 1Basic

Start from $7$ and keep taking “the sum of the squares of the digits”. After how many steps do you first get $1$ ?

Exercise 2Basic

$a_{1} = 0$ , $a_{n + 1} = 6 + a_{n}$ . Find $n \to \infty lim a_{n}$ .

Exercise 3Advanced

$T (x, y) = (\frac{x}{3} + \frac{5}{3}, \frac{y}{3} + 1)$ shrinks a map and places it inside itself. Find the sum of the coordinates of the fixed point.

Exercise 4Challenge

$f : R \to R$ satisfies $f (f (x)) = x^{2} - x + 1$ . Find $f (0)$ .

In one sentence

Some point of the big map lies exactly on top of the point that represents it on the small map

Stop 1 · Sequences: the limit of an orbit

Stop 2 · Number theory: finite means it cycles

Why every orbit ends up in a cycle

Stop 3 · Functional equations: finding a fixed point inside $f (f (x))$

Practice

Mistake Museum · Exhibits from this stop

Solving the fixed-point equation without proving the limit exists

Applications of Iteration

In one sentence

Stop 1 · Sequences: the limit of an orbit

Stop 2 · Number theory: finite means it cycles

Stop 3 · Functional equations: finding a fixed point inside f(f(x))

Practice

Mistake Museum · Exhibits from this stop

Stop 3 · Functional equations: finding a fixed point inside $f (f (x))$