posts/fixed-points-and-closed-forms.html

<!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">&nbsp;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 &amp; 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&ouml;bius map</p>
  <div class="article__meta">September 21, 2026 &middot; 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 &mdash; <em>choose the coordinate in which the
    map is a multiplication</em> &mdash; 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 &mdash; 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 &mdash;
    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 &mdash; 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 &mdash; <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|&lt;1$ the staircase spirals into the fixed
    point; at $|p|&gt;1$ it marches away from it; at $p=-1$ it cycles forever. The fixed point
    itself never moves &mdash; 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 &mdash; 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&ouml;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&nbsp;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$ &mdash; 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 &mdash; 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 &mdash; 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&ouml;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 &mdash;
    the projective line. Composition of M&ouml;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 &mdash; 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&nbsp;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|&lt;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 &mdash; 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 &mdash; 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&ouml;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&ouml;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&lt;|f'(p)|&lt;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&ouml;bius maps
    lucky is not that a linearizing coordinate exists &mdash; that is generic &mdash; 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$ &mdash; 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 &mdash; 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 &mdash; 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&ndash;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 &mdash; 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$ &mdash; 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">&larr; All articles</a>
    <a href="#s1">Back to top &uarr;</a>
  </div>

</main>

<footer class="sitefoot">
  <div class="sitefoot__in">
    <span>Math Lab &copy; <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>