Fixed Points, and Why They Solve Recurrences

Every student of sequences learns the same move: to solve $a_{n+1}=2a_n+3$, first find the number that stays put, then subtract it. It works, it always works, and almost nobody is told why. The answer is worth the detour, because the same idea — choose the coordinate in which the map is a multiplication — is the whole content of eigenvalues, of the characteristic-root method, and of local linearization in dynamics.

1.A trick that works too well

Here is the problem in its smallest form.

The standard recipe has three steps. Solve $L=2L+3$, giving $L=-3$. Subtract it from both sides:

$$a_{n+1}+3 = 2a_n+6 = 2\,(a_n+3).$$

So $a_n+3$ is geometric with ratio $2$ and first term $a_1+3=4$, hence $a_n+3=4\cdot 2^{\,n-1}$ and

$$a_n = 2^{\,n+1}-3 .$$

Clean. But look again at the first step. We solved $L=2L+3$, which is the statement that the constant sequence $a_n=L$ satisfies the recurrence. That is a solution we explicitly do not want: our sequence starts at $1$, not at $-3$. Why should a solution we are throwing away be the key to the one we are looking for? And why $-3$ and nothing else — would $-2$ also have worked a little?

It would not, and the reason has nothing to do with sequences. It has to do with the map.

2.The fixed point is an origin

Write the recurrence as $a_{n+1}=f(a_n)$ with $f(x)=2x+3$. The sequence is then nothing but the orbit of the starting value under repeated application of $f$:

$$a_1,\quad f(a_1),\quad f(f(a_1)),\quad f^{3}(a_1),\ \dots$$

Changing $a_1$ changes the orbit but not $f$. So the object that deserves study is $f$, and the question becomes: what does $f$ actually do?

It does two things at once: it scales by $2$, and it shifts by $3$. The scaling is intrinsic — doubling is doubling in any coordinate system. The shift is not. A shift is a statement about where we happened to put the number $0$, and we are free to put it somewhere else. Let $u = x - L$ measure position relative to a new origin $L$. In this coordinate,

$$f(x)-L \;=\; 2x+3-L \;=\; 2\,(x-L) + \underbrace{(2L+3-L)}_{\text{leftover shift}} .$$

The leftover shift vanishes for exactly one choice of origin: $L=2L+3$, i.e. $L=-3$. Only there does $f$ lose its additive part and become the pure scaling $u \mapsto 2u$.

In general, for $f(x)=px+q$ with $p\neq 1$, the fixed point is $L=\dfrac{q}{1-p}$ and

$$f(x)-L=p\,(x-L) \qquad\Longrightarrow\qquad a_n-L=p^{\,n-1}(a_1-L).$$

When $p=1$ there is no fixed point at all, and indeed nothing to subtract: $f(x)=x+q$ is a translation, and the sequence is arithmetic rather than geometric. The dichotomy is already visible here — a fixed point exists exactly when the map is a scaling in disguise.

A picture makes the mechanism obvious. In a cobweb diagram we draw $y=f(x)$ and $y=x$; the orbit bounces vertically to the curve and horizontally to the diagonal. Fixed points are intersections of the two, and the steepness of $f$ where they meet decides everything.

Play with the slope in the first preset. At $|p|<1$ the staircase spirals into the fixed point; at $|p|>1$ it marches away from it; at $p=-1$ it cycles forever. The fixed point itself never moves — only its character changes, and the quantity that governs that character is the slope of $f$ at the point. Hold on to that; it is the punchline of the whole article.

3.The same question, with a harder map

Try the recipe. Fixed points satisfy $x(x+1)=4x-2$, that is $x^2-3x+2=0$, so there are now two of them: $x=2$ and $x=1$. Which one do we subtract?

Subtract the first and see what happens:

$$a_{n+1}-2=\frac{4a_n-2-2(a_n+1)}{a_n+1}=\frac{2(a_n-2)}{a_n+1}.$$

Not geometric — the denominator still depends on $n$. But the factor $(a_n-2)$ did appear, which is encouraging. Now subtract the other one:

$$a_{n+1}-1=\frac{4a_n-2-(a_n+1)}{a_n+1}=\frac{3(a_n-1)}{a_n+1}.$$

The same unwanted denominator. Two expressions spoiled by the identical factor can be repaired by dividing one by the other:

$$\frac{a_{n+1}-2}{a_{n+1}-1}=\frac{2}{3}\cdot\frac{a_n-2}{a_n-1}.$$

That is the entire solution. With $w_n=\dfrac{a_n-2}{a_n-1}$ we have $w_{n+1}=\tfrac23 w_n$, and $w_1=\tfrac{3-2}{3-1}=\tfrac12$, so $w_n=\tfrac12\left(\tfrac23\right)^{n-1}$. Solving $w_n=\frac{a_n-2}{a_n-1}$ for $a_n$ gives $a_n=\dfrac{2-w_n}{1-w_n}$, and after clearing powers,

$$a_n=\frac{8\cdot 3^{\,n-1}-2^{\,n}}{4\cdot 3^{\,n-1}-2^{\,n}} \;=\; 3,\ \tfrac52,\ \tfrac{16}{7},\ \tfrac{50}{23},\ \dots \;\longrightarrow\; 2 .$$

So with one fixed point we subtract; with two we take a ratio. That looks like two unrelated tricks. It is one identity.

4.One identity does all the work

Both recurrences above are instances of the same family. A Möbius map (also called a fractional linear or homographic map) is

$$f(x)=\frac{ax+b}{cx+d},\qquad ad-bc\neq 0 .$$

The condition $ad-bc\neq0$ just says $f$ is not constant. Taking $c=0,\ d=1$ recovers the affine case $f(x)=ax+b$, so everything from section 2 is included. Fixed points satisfy $x(cx+d)=ax+b$, i.e.

$$cx^{2}+(d-a)x-b=0,$$

a quadratic: generically two roots, sometimes one (a double root), sometimes none in $\R$.

The lemma says that subtracting a fixed point always produces the factor $(x-p)$ we want, together with the same nuisance denominator $cx+d$ no matter which fixed point we used. Everything else follows by removing that denominator, and there are exactly two ways to remove it.

Two distinct fixed points: divide

If $p\neq q$ are both fixed, apply the lemma twice and divide; the denominators cancel:

$$\frac{f(x)-p}{f(x)-q}=\underbrace{\frac{a-cp}{a-cq}}_{\textstyle k}\cdot\frac{x-p}{x-q}.$$

So the transformed sequence $w_n=\dfrac{a_n-p}{a_n-q}$ is geometric with ratio $k$:

$$w_{n+1}=k\,w_n \qquad\Longrightarrow\qquad w_n=k^{\,n-1}w_1, \qquad a_n=\frac{p-q\,w_n}{1-w_n}.$$

A double fixed point: take reciprocals

If the quadratic has a double root $p=\dfrac{a-d}{2c}$, there is no second fixed point to divide by. Instead invert the lemma and split the denominator as $cx+d=c\,(x-p)+(cp+d)$:

$$\frac{1}{f(x)-p}=\frac{c(x-p)+(cp+d)}{(a-cp)(x-p)}=\frac{c}{a-cp}+\frac{cp+d}{a-cp}\cdot\frac{1}{x-p}.$$

For a double root the two quantities $cp+d$ and $a-cp$ are both equal to $\tfrac{a+d}{2}$, so the last fraction has coefficient $1$ and what remains is

$$\frac{1}{f(x)-p}=\frac{1}{x-p}+\frac{2c}{a+d}.$$

The reciprocal sequence $w_n=\dfrac{1}{a_n-p}$ is arithmetic. Convergence is then of order $1/n$ — dramatically slower than geometric, and a first hint that the double-root case is not just a degenerate bookkeeping detail but a genuinely different kind of dynamics.

Both cases are now mechanical. What they have in common is that we never solved the recurrence directly — we changed variable to a $w_n$ whose recursion is trivial, iterated that, and translated back. The table below is the honest version of "trust me, it's geometric": watch the last column refuse to move.

5.Why: iterating a Möbius map is a matrix power

So far we have a working method and a proof, but not yet a reason. The reason appears the moment we write $x$ as a ratio. Put $x=X/Y$ and feed it through $f$:

$$f\!\left(\frac{X}{Y}\right)=\frac{a\frac XY+b}{c\frac XY+d}=\frac{aX+bY}{cX+dY}.$$

The numerator and the denominator transform linearly. In other words, the nonlinear map $f$ on numbers is a linear map on pairs:

$$\begin{pmatrix}X\\Y\end{pmatrix}\longmapsto M\begin{pmatrix}X\\Y\end{pmatrix}, \qquad M=\begin{pmatrix}a&b\\c&d\end{pmatrix},$$

and $x=X/Y$ is just the pair read as a slope. Scaling $(X,Y)$ by a nonzero constant does not change $x$, so what $f$ really acts on is the set of lines through the origin in the plane — the projective line. Composition of Möbius maps corresponds to multiplication of their matrices, and therefore

$$f^{\,n}\ \text{is the map with matrix }\ M^{n}.$$

Now the fixed points reveal themselves. The point $x=p$ is fixed exactly when the line spanned by $(p,1)$ is mapped to itself — that is, when $(p,1)$ is an eigenvector of $M$:

$$M\begin{pmatrix}p\\1\end{pmatrix}=\lambda_p\begin{pmatrix}p\\1\end{pmatrix}.$$

Reading the second coordinate gives the eigenvalue for free: $\lambda_p=cp+d$. And since the two eigenvalues sum to the trace,

$$a-cp=(a+d)-(cp+d)=\lambda_p+\lambda_q-\lambda_p=\lambda_q .$$

So the mysterious constant $k$ from section 4 was an eigenvalue ratio all along:

$$k=\frac{a-cp}{a-cq}=\frac{\lambda_q}{\lambda_p}.$$

And there is a third face of the same number. Differentiating $f$ and using $ad-bc=\lambda_p\lambda_q$,

$$f'(x)=\frac{ad-bc}{(cx+d)^{2}}\qquad\Longrightarrow\qquad f'(p)=\frac{\lambda_p\lambda_q}{\lambda_p^{2}}=\frac{\lambda_q}{\lambda_p}=k .$$

Note the pleasant symmetry: $f'(q)=\lambda_p/\lambda_q=1/k$. The two fixed points always carry reciprocal multipliers, so if one attracts, the other repels — they can never both be stable. And the attracting one is the eigendirection of the larger eigenvalue. Iterating $f$ is therefore literally the power method from numerical linear algebra: repeated multiplication by $M$ turns any starting vector toward the dominant eigenvector, and $a_n$ is that vector's slope. The sequence converges because eigenvalues have different sizes.

The double-root case is now equally transparent. It occurs when $\lambda_p=\lambda_q$, so $k=1$ and $M$ cannot be diagonalized — it is a Jordan block. A Jordan block's powers grow with an extra factor of $n$,

$$\begin{pmatrix}\lambda&1\\0&\lambda\end{pmatrix}^{\! n} =\lambda^{n}\begin{pmatrix}1&n/\lambda\\0&1\end{pmatrix},$$

and that stray $n$ is exactly the $n$ that appeared in $a_n=2+\frac1n$. The arithmetic sequence was a Jordan block in disguise.

6.The essence: solving means choosing coordinates

Step back from the algebra. In each case we produced a map $\varphi$ that turns $f$ into something trivial. The precise notion is conjugacy: $\varphi$ conjugates $f$ to $g$ when

$$\varphi\circ f=g\circ\varphi, \qquad\text{equivalently}\qquad g=\varphi\circ f\circ\varphi^{-1}.$$

If that holds then $g^{\,n}=\varphi\circ f^{\,n}\circ\varphi^{-1}$, so iterating $f$ is the same as iterating $g$ in the $\varphi$ coordinate. Our three cases are three conjugacies:

Each $\varphi$ is itself a Möbius map, and each is chosen by where it sends the fixed points: $\frac{x-p}{x-q}$ sends $p\mapsto0$ and $q\mapsto\infty$, pinning the two special points to the two places where multiplication by $k$ fixes things. In the double case $\frac{1}{x-p}$ sends the single fixed point to $\infty$, which is precisely the fixed point of a translation. We are not solving the recurrence; we are moving the fixed points to where they belong.

Why this is not special to Möbius maps

Take any differentiable $f$ with $f(p)=p$. Near $p$, Taylor gives $f(x)\approx p+f'(p)(x-p)$: every map is a multiplication by $f'(p)$ to first order near a fixed point. The question is whether that approximation can be made exact by a change of coordinate, and the answer is a genuine theorem.

Koenigs' linearization theorem. If $f$ is analytic near a fixed point $p$ and $0<|f'(p)|<1$, there is an analytic change of coordinate $\varphi$, unique up to scale, with $\varphi(f(x))=f'(p)\,\varphi(x)$ near $p$.

So the schoolbook trick is a visible special case of a general principle. What makes Möbius maps lucky is not that a linearizing coordinate exists — that is generic — but that it exists globally and can be written down in closed form. That is why these recurrences, and almost no others, have elementary closed forms.

The excluded cases in Koenigs' hypothesis are exactly the interesting ones, and we have met both:

• $f'(p)=1$, the parabolic case. No linearization exists: the honest normal form is $w\mapsto w+1$, orbits creep in at rate $1/n$, and the fixed point attracts from one side while repelling on the other. This is the double root.
• No real fixed point. The quadratic has complex roots, $\lambda_p$ and $\lambda_q$ are complex conjugates, and $k=\lambda_q/\lambda_p$ has modulus $1$: the map is a rotation. Orbits never settle. Try the last preset in the cobweb above, $a_{n+1}=\frac{a_n-1}{a_n+1}$, whose every orbit has period $4$ — because $k=-i$, and $(-i)^4=1$. A "no solution" in the fixed-point method is really a rotation by an angle.

7.Where this goes next

Once iteration is matrix multiplication, a second door opens. Track the pair $(X_n,Y_n)$ with $a_n=X_n/Y_n$ and $(X_{n+1},Y_{n+1})=M(X_n,Y_n)$. By the Cayley–Hamilton theorem, $M^{2}=(a+d)M-(ad-bc)I$, so each of the two coordinate sequences obeys the same second-order linear recurrence:

$$u_{n+2}=(a+d)\,u_{n+1}-(ad-bc)\,u_{n}.$$

A one-step fractional recurrence and a two-step linear recurrence are the same object seen from two sides — and the "characteristic equation" of the second is the characteristic polynomial of $M$, whose roots are our $\lambda_p,\lambda_q$.

The cleanest example is sitting in the presets above. Take

$$a_{n+1}=1+\frac{1}{a_n}=\frac{a_n+1}{a_n},\qquad a_1=1, \qquad M=\begin{pmatrix}1&1\\1&0\end{pmatrix}.$$

Starting from $(X_1,Y_1)=(1,1)$ the pairs are $(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),\dots$ — the Fibonacci numbers, so $a_n=F_{n+1}/F_n$. The fixed-point equation is $x^{2}-x-1=0$ and the characteristic equation is $\lambda^{2}-\lambda-1=0$: the same quadratic, because here $\lambda=cx+d=x$. The attracting fixed point is the golden ratio $\varphi$, its multiplier is $f'(\varphi)=-1/\varphi^{2}\approx-0.382$, and the negative sign is why the convergents alternate around $\varphi$ instead of approaching from one side.

Which means we have already computed, without noticing, the hard part of Binet's formula. The next article takes that route deliberately: characteristic roots as the eigenvalues of a companion matrix, why $\alpha^{n}$ and $\beta^{n}$ span every solution, and what the repeated-root case $(A+Bn)\alpha^{n}$ is really saying.