| <!doctype html> |
| <html lang="en"> |
| <head> |
| <meta charset="utf-8"> |
| <meta name="viewport" content="width=device-width, initial-scale=1, viewport-fit=cover"> |
| <title>Fixed Points, and Why They Solve Recurrences — Math Lab</title> |
| <meta name="description" content="The fixed point of a recurrence is not a lucky guess. It is the origin of the coordinate system in which the map becomes a pure multiplication — and the multiplier is exactly the derivative there."> |
| <link rel="icon" href="../assets/favicon.svg" type="image/svg+xml"> |
| <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.16.9/dist/katex.min.css"> |
| <link rel="stylesheet" href="../assets/style.css"> |
| </head> |
| <body data-slug="fixed-points-and-closed-forms"> |
|
|
| <header class="masthead"> |
| <div class="masthead__in"> |
| <a class="brand" href="../index.html">Math<span class="brand__mark"> Lab</span></a> |
| <span class="masthead__tag">notes on ideas worth slowing down for</span> |
| <nav class="masthead__nav"><a href="../index.html">All articles</a></nav> |
| </div> |
| </header> |
|
|
| <main class="wrap article"> |
|
|
| <div class="article__cat">Sequences & Recurrences</div> |
| <h1>Fixed Points, and Why They Solve Recurrences</h1> |
| <p class="article__sub">From a high-school trick to the geometry of a Möbius map</p> |
| <div class="article__meta">September 21, 2026 · 20 min read</div> |
|
|
| <div class="toc" id="toc" hidden></div> |
|
|
| <div class="prose"> |
|
|
| <p class="lede"> |
| 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 — <em>choose the coordinate in which the |
| map is a multiplication</em> — is the whole content of eigenvalues, of the characteristic-root |
| method, and of local linearization in dynamics. |
| </p> |
|
|
| <h2 id="s1"><span class="num">1.</span>A trick that works too well</h2> |
|
|
| <p>Here is the problem in its smallest form.</p> |
|
|
| <div class="boxed"> |
| <div class="boxed__h">Problem</div> |
| <p style="margin:0">Find a closed form for $a_{n+1}=2a_n+3$ with $a_1=1$.</p> |
| </div> |
|
|
| <p>The standard recipe has three steps. Solve $L=2L+3$, giving $L=-3$. Subtract it from both sides:</p> |
|
|
| $$a_{n+1}+3 = 2a_n+6 = 2\,(a_n+3).$$ |
|
|
| <p> |
| 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 |
| </p> |
|
|
| $$a_n = 2^{\,n+1}-3 .$$ |
|
|
| <p> |
| Clean. But look again at the first step. We solved $L=2L+3$, which is the statement that |
| the <em>constant</em> 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? |
| </p> |
|
|
| <p> |
| It would not, and the reason has nothing to do with sequences. It has to do with the map. |
| </p> |
|
|
| <h2 id="s2"><span class="num">2.</span>The fixed point is an origin</h2> |
|
|
| <p> |
| Write the recurrence as $a_{n+1}=f(a_n)$ with $f(x)=2x+3$. The sequence is then nothing but |
| the <em>orbit</em> of the starting value under repeated application of $f$: |
| </p> |
|
|
| $$a_1,\quad f(a_1),\quad f(f(a_1)),\quad f^{3}(a_1),\ \dots$$ |
|
|
| <p> |
| Changing $a_1$ changes the orbit but not $f$. So the object that deserves study is $f$, and the |
| question becomes: <strong>what does $f$ actually do?</strong> |
| </p> |
|
|
| <p> |
| 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, |
| </p> |
|
|
| $$f(x)-L \;=\; 2x+3-L \;=\; 2\,(x-L) + \underbrace{(2L+3-L)}_{\text{leftover shift}} .$$ |
|
|
| <p> |
| 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$. |
| </p> |
|
|
| <div class="callout"> |
| <span class="callout__h">The point</span> |
| <p> |
| The fixed point is not a guess and not a convenient coincidence. It is the unique origin |
| from which an affine map looks like a multiplication. Solving $L=pL+q$ is not solving the |
| recurrence — it is <em>choosing a coordinate system</em>. |
| </p> |
| </div> |
|
|
| <p>In general, for $f(x)=px+q$ with $p\neq 1$, the fixed point is $L=\dfrac{q}{1-p}$ and</p> |
|
|
| $$f(x)-L=p\,(x-L) \qquad\Longrightarrow\qquad a_n-L=p^{\,n-1}(a_1-L).$$ |
|
|
| <p> |
| 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 — <em>a fixed point exists exactly when the map is a scaling in disguise.</em> |
| </p> |
|
|
| <p> |
| 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. |
| </p> |
|
|
| <div class="widget" data-widget="cobweb" data-presets="linear,two,dbl,golden,rot"> |
| <div class="widget__head"> |
| <div class="widget__title">Cobweb explorer</div> |
| <p class="widget__desc"> |
| The orbit of $f(x)=\dfrac{ax+b}{cx+d}$, drawn against the diagonal $y=x$. Take $c=0,\ d=1$ for the |
| affine case $f(x)=ax+b$. Change $a,b,c,d$ or the starting value and watch where the staircase goes; |
| the readout names the fixed points and the multiplier $f'$ at each one. |
| </p> |
| </div> |
| </div> |
|
|
| <p> |
| 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 <em>character</em> 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. |
| </p> |
|
|
| <h2 id="s3"><span class="num">3.</span>The same question, with a harder map</h2> |
|
|
| <div class="boxed"> |
| <div class="boxed__h">Problem</div> |
| <p style="margin:0">Find a closed form for $\displaystyle a_{n+1}=\frac{4a_n-2}{a_n+1}$ with $a_1=3$.</p> |
| </div> |
|
|
| <p> |
| Try the recipe. Fixed points satisfy $x(x+1)=4x-2$, that is $x^2-3x+2=0$, so there are now |
| <em>two</em> of them: $x=2$ and $x=1$. Which one do we subtract? |
| </p> |
|
|
| <p>Subtract the first and see what happens:</p> |
|
|
| $$a_{n+1}-2=\frac{4a_n-2-2(a_n+1)}{a_n+1}=\frac{2(a_n-2)}{a_n+1}.$$ |
|
|
| <p> |
| Not geometric — the denominator still depends on $n$. But the factor $(a_n-2)$ did appear, |
| which is encouraging. Now subtract the other one: |
| </p> |
|
|
| $$a_{n+1}-1=\frac{4a_n-2-(a_n+1)}{a_n+1}=\frac{3(a_n-1)}{a_n+1}.$$ |
|
|
| <p> |
| The <em>same</em> unwanted denominator. Two expressions spoiled by the identical factor can be |
| repaired by dividing one by the other: |
| </p> |
|
|
| $$\frac{a_{n+1}-2}{a_{n+1}-1}=\frac{2}{3}\cdot\frac{a_n-2}{a_n-1}.$$ |
|
|
| <p> |
| 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, |
| </p> |
|
|
| $$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 .$$ |
|
|
| <p> |
| So with one fixed point we subtract; with two we take a <em>ratio</em>. That looks like two |
| unrelated tricks. It is one identity. |
| </p> |
|
|
|
|
| <h2 id="s4"><span class="num">4.</span>One identity does all the work</h2> |
|
|
| <p> |
| Both recurrences above are instances of the same family. A <strong>Möbius map</strong> (also |
| called a fractional linear or homographic map) is |
| </p> |
|
|
| $$f(x)=\frac{ax+b}{cx+d},\qquad ad-bc\neq 0 .$$ |
|
|
| <p> |
| 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. |
| </p> |
|
|
| $$cx^{2}+(d-a)x-b=0,$$ |
|
|
| <p>a quadratic: generically two roots, sometimes one (a double root), sometimes none in $\R$.</p> |
|
|
| <div class="boxed"> |
| <div class="boxed__h">Lemma (the only computation in this article)</div> |
| <p>If $p$ is a fixed point of $f$, then for every $x$,</p> |
| $$f(x)-p=\frac{(a-cp)\,(x-p)}{cx+d}.$$ |
| <p style="margin-bottom:0"> |
| <em>Proof.</em> Expanding, $f(x)-p=\dfrac{(a-cp)x+(b-pd)}{cx+d}$. Because $p$ is fixed, |
| $ap+b=p(cp+d)$, so $b=cp^{2}+dp-ap$ and therefore |
| $b-pd=cp^{2}-ap=-p\,(a-cp)$. The numerator is thus $(a-cp)x-p(a-cp)=(a-cp)(x-p)$. $\ \blacksquare$ |
| </p> |
| </div> |
|
|
| <p> |
| 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. |
| </p> |
|
|
| <h3>Two distinct fixed points: divide</h3> |
|
|
| <p>If $p\neq q$ are both fixed, apply the lemma twice and divide; the denominators cancel:</p> |
|
|
| $$\frac{f(x)-p}{f(x)-q}=\underbrace{\frac{a-cp}{a-cq}}_{\textstyle k}\cdot\frac{x-p}{x-q}.$$ |
|
|
| <p>So the transformed sequence $w_n=\dfrac{a_n-p}{a_n-q}$ is <strong>geometric</strong> with ratio $k$:</p> |
|
|
| $$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}.$$ |
|
|
| <h3>A double fixed point: take reciprocals</h3> |
|
|
| <p> |
| 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)$: |
| </p> |
|
|
| $$\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}.$$ |
|
|
| <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 |
| </p> |
|
|
| $$\frac{1}{f(x)-p}=\frac{1}{x-p}+\frac{2c}{a+d}.$$ |
|
|
| <p> |
| The reciprocal sequence $w_n=\dfrac{1}{a_n-p}$ is <strong>arithmetic</strong>. 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. |
| </p> |
|
|
| <div class="callout callout--warm"> |
| <span class="callout__h">Worked example — the double root</span> |
| <p> |
| $a_{n+1}=\dfrac{3a_n-4}{a_n-1}$ with $a_1=3$. Fixed points: $x^{2}-4x+4=0$, so $p=2$ twice. |
| Here $c=1$, $a+d=3+(-1)=2$, so the step is $2c/(a+d)=1$: |
| $\dfrac{1}{a_{n+1}-2}=\dfrac{1}{a_n-2}+1$. Since $\dfrac{1}{a_1-2}=1$, we get |
| $\dfrac{1}{a_n-2}=n$ and |
| </p> |
| $$a_n=2+\frac{1}{n}.$$ |
| </div> |
|
|
| <p> |
| 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 <em>that</em>, |
| and translated back. The table below is the honest version of "trust me, it's geometric": watch |
| the last column refuse to move. |
| </p> |
|
|
| <div class="widget" data-widget="linearize" data-presets="two,dbl,linear,golden"> |
| <div class="widget__head"> |
| <div class="widget__title">The transformed sequence</div> |
| <p class="widget__desc"> |
| The raw sequence $a_n$ has no visible pattern. The coordinate $w_n$ built from the fixed points |
| does: its successive ratios (or, in the double-root case, its successive differences) are constant. |
| </p> |
| </div> |
| </div> |
|
|
| <h2 id="s5"><span class="num">5.</span>Why: iterating a Möbius map is a matrix power</h2> |
|
|
| <p> |
| 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$: |
| </p> |
|
|
| $$f\!\left(\frac{X}{Y}\right)=\frac{a\frac XY+b}{c\frac XY+d}=\frac{aX+bY}{cX+dY}.$$ |
|
|
| <p> |
| The numerator and the denominator transform <em>linearly</em>. In other words, the nonlinear map $f$ |
| on numbers is a linear map on pairs: |
| </p> |
|
|
| $$\begin{pmatrix}X\\Y\end{pmatrix}\longmapsto M\begin{pmatrix}X\\Y\end{pmatrix}, |
| \qquad M=\begin{pmatrix}a&b\\c&d\end{pmatrix},$$ |
|
|
| <p> |
| 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 <em>lines through the origin</em> in the plane — |
| the projective line. Composition of Möbius maps corresponds to multiplication of their matrices, |
| and therefore |
| </p> |
|
|
| $$f^{\,n}\ \text{is the map with matrix }\ M^{n}.$$ |
|
|
| <div class="callout"> |
| <span class="callout__h">The reframing</span> |
| <p> |
| Computing $a_n$ in closed form is computing a power of a $2\times2$ matrix. And we know how to |
| take powers of matrices: diagonalize. |
| </p> |
| </div> |
|
|
| <p> |
| 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 <strong>eigenvector</strong> of $M$: |
| </p> |
|
|
| $$M\begin{pmatrix}p\\1\end{pmatrix}=\lambda_p\begin{pmatrix}p\\1\end{pmatrix}.$$ |
|
|
| <p> |
| Reading the second coordinate gives the eigenvalue for free: $\lambda_p=cp+d$. And since the two |
| eigenvalues sum to the trace, |
| </p> |
|
|
| $$a-cp=(a+d)-(cp+d)=\lambda_p+\lambda_q-\lambda_p=\lambda_q .$$ |
|
|
| <p>So the mysterious constant $k$ from section 4 was an eigenvalue ratio all along:</p> |
|
|
| $$k=\frac{a-cp}{a-cq}=\frac{\lambda_q}{\lambda_p}.$$ |
|
|
| <p>And there is a third face of the same number. Differentiating $f$ and using $ad-bc=\lambda_p\lambda_q$,</p> |
|
|
| $$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 .$$ |
|
|
| <div class="tbl-wrap"> |
| <table class="tbl"> |
| <thead><tr><th>The number $k$</th><th>where it comes from</th><th>what it tells you</th></tr></thead> |
| <tbody> |
| <tr><td style="text-align:left">$\dfrac{a-cp}{a-cq}$</td><td style="text-align:left">the ratio trick</td><td style="text-align:left">the common ratio of $w_n$</td></tr> |
| <tr><td style="text-align:left">$\dfrac{\lambda_q}{\lambda_p}$</td><td style="text-align:left">the eigenvalues of $M$</td><td style="text-align:left">which eigendirection wins</td></tr> |
| <tr><td style="text-align:left">$f'(p)$</td><td style="text-align:left">calculus at the fixed point</td><td style="text-align:left">attracting if $|k|<1$</td></tr> |
| </tbody> |
| </table> |
| </div> |
|
|
| <p> |
| 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 <em>larger</em> 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. |
| </p> |
|
|
| <p> |
| 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$, |
| </p> |
|
|
| $$\begin{pmatrix}\lambda&1\\0&\lambda\end{pmatrix}^{\! n} |
| =\lambda^{n}\begin{pmatrix}1&n/\lambda\\0&1\end{pmatrix},$$ |
|
|
| <p> |
| and that stray $n$ is exactly the $n$ that appeared in $a_n=2+\frac1n$. The arithmetic sequence |
| was a Jordan block in disguise. |
| </p> |
|
|
| <h2 id="s6"><span class="num">6.</span>The essence: solving means choosing coordinates</h2> |
|
|
| <p> |
| Step back from the algebra. In each case we produced a map $\varphi$ that turns $f$ into something |
| trivial. The precise notion is <strong>conjugacy</strong>: $\varphi$ conjugates $f$ to $g$ when |
| </p> |
|
|
| $$\varphi\circ f=g\circ\varphi, \qquad\text{equivalently}\qquad g=\varphi\circ f\circ\varphi^{-1}.$$ |
|
|
| <p> |
| 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: |
| </p> |
|
|
| <div class="tbl-wrap"> |
| <table class="tbl"> |
| <thead><tr><th>fixed points</th><th>coordinate $\varphi(x)$</th><th>normal form $g(w)$</th><th>orbit</th></tr></thead> |
| <tbody> |
| <tr><td style="text-align:left">one, affine map</td><td style="text-align:left">$x-L$</td><td style="text-align:left">$k\,w$</td><td style="text-align:left">geometric</td></tr> |
| <tr><td style="text-align:left">two, $p\neq q$</td><td style="text-align:left">$\dfrac{x-p}{x-q}$</td><td style="text-align:left">$k\,w$</td><td style="text-align:left">geometric</td></tr> |
| <tr><td style="text-align:left">one, double</td><td style="text-align:left">$\dfrac{1}{x-p}$</td><td style="text-align:left">$w+s$</td><td style="text-align:left">arithmetic</td></tr> |
| </tbody> |
| </table> |
| </div> |
|
|
| <p> |
| 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. <em>We are not solving |
| the recurrence; we are moving the fixed points to where they belong.</em> |
| </p> |
|
|
| <div class="callout"> |
| <span class="callout__h">The essence, in one sentence</span> |
| <p> |
| A closed form exists because the map can be conjugated to a multiplication, the conjugating |
| coordinate is determined by the fixed points, and the multiplier is $f'$ at the attracting one. |
| </p> |
| </div> |
|
|
| <h3>Why this is not special to Möbius maps</h3> |
|
|
| <p> |
| Take any differentiable $f$ with $f(p)=p$. Near $p$, Taylor gives |
| $f(x)\approx p+f'(p)(x-p)$: <em>every</em> 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. |
| </p> |
|
|
| <blockquote> |
| <strong>Koenigs' linearization theorem.</strong> 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$. |
| </blockquote> |
|
|
| <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 |
| <em>globally</em> and can be written down in closed form. That is why these recurrences, and almost |
| no others, have elementary closed forms. |
| </p> |
|
|
| <p>The excluded cases in Koenigs' hypothesis are exactly the interesting ones, and we have met both:</p> |
|
|
| <ul> |
| <li> |
| <strong>$f'(p)=1$, the parabolic case.</strong> 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. |
| </li> |
| <li> |
| <strong>No real fixed point.</strong> 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 |
| <em>rotation</em>. 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. |
| </li> |
| </ul> |
|
|
| <div class="boxed"> |
| <div class="boxed__h">The recipe, with reasons attached</div> |
| <ol style="margin:0"> |
| <li>Write $a_{n+1}=\frac{a\,a_n+b}{c\,a_n+d}$ and form $M=\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)$.</li> |
| <li>Solve $cx^{2}+(d-a)x-b=0$ for the fixed points — the eigendirections of $M$.</li> |
| <li>Two real roots $p\neq q$: set $w_n=\frac{a_n-p}{a_n-q}$; it is geometric with ratio $k=f'(p)=\lambda_q/\lambda_p$.</li> |
| <li>One double root $p$: set $w_n=\frac{1}{a_n-p}$; it is arithmetic with step $\frac{2c}{a+d}$.</li> |
| <li>No real root: no closed form of this shape — the orbit rotates; work over $\C$ if you want one.</li> |
| <li>Invert $w_n$ to recover $a_n$.</li> |
| </ol> |
| </div> |
|
|
| <h2 id="s7"><span class="num">7.</span>Where this goes next</h2> |
|
|
| <p> |
| 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 <em>each</em> of the two coordinate sequences obeys the same |
| second-order linear recurrence: |
| </p> |
|
|
| $$u_{n+2}=(a+d)\,u_{n+1}-(ad-bc)\,u_{n}.$$ |
|
|
| <p> |
| 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$. |
| </p> |
|
|
| <p> |
| The cleanest example is sitting in the presets above. Take |
| </p> |
|
|
| $$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}.$$ |
|
|
| <p> |
| 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. |
| </p> |
|
|
| <p> |
| Which means we have already computed, without noticing, the hard part of Binet's formula. The next |
| article takes that route deliberately: <em>characteristic roots</em> 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. |
| </p> |
|
|
| </div> |
|
|
| <div class="series" id="series" hidden></div> |
|
|
| <div class="pagenav"> |
| <a href="../index.html">← All articles</a> |
| <a href="#s1">Back to top ↑</a> |
| </div> |
|
|
| </main> |
|
|
| <footer class="sitefoot"> |
| <div class="sitefoot__in"> |
| <span>Math Lab © <span data-year></span></span> |
| <span><a href="../index.html">Index</a></span> |
| </div> |
| </footer> |
|
|
| <script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.9/dist/katex.min.js"></script> |
| <script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.9/dist/contrib/auto-render.min.js"></script> |
| <script defer src="../assets/posts.js"></script> |
| <script defer src="../assets/widgets.js"></script> |
| <script defer src="../assets/post.js"></script> |
| </body> |
| </html> |
|
|
