---
title: First-Order Difference Equations
module: First-Order Equations
moduleNumber: 2
lessonNumber: 6
order: 206
summary: >
  A difference equation advances a sequence one index at a time by a rule
  y_{n+1} = f(y_n). The linear case y_{n+1} = rho*y_n + b solves in closed form and
  converges to its equilibrium exactly when the ratio has magnitude below one,
  which underlies compound-interest and loan calculations. The logistic difference
  equation shows the nonlinear counterpart: an exchange of stability, a cascade of
  period doublings, and the onset of chaos.
topics: [First-Order Equations]
draft: false
sources:
  - book: Boyce
    ref: "§2.9 First-Order Difference Equations; the linear equation, the logistic map, period doubling, and chaos"
---

A **difference equation** advances a sequence one index at a time. Given a rule

$$
y_{n+1} = f(y_n), \qquad n = 0, 1, 2, \dots
$$

and a starting value $y_0$, the whole sequence is generated by repeated
substitution: $y_1 = f(y_0)$, $y_2 = f(y_1) = f(f(y_0))$, and in general
$y_n = f^n(y_0)$, the $n$-th **iterate**. Where a first-order differential equation
runs a solution continuously in $t$, a first-order difference equation steps a
solution discretely in $n$, and the central question is the same: how does $y_n$
behave as $n \to \infty$?[^boyce-29]

The discrete analogue of a constant solution is a sequence that never changes.

> **Definition (Equilibrium solution).** A value $y^\ast$ is an equilibrium
> solution of $y_{n+1} = f(y_n)$ if $y^\ast = f(y^\ast)$. The constant sequence
> $y_n = y^\ast$ for all $n$ then satisfies the equation. An equilibrium is
> **asymptotically stable** if sequences starting nearby converge to it, and
> **unstable** if they move away.

Equilibria are the fixed points of $f$, found by setting $y_{n+1} = y_n$.

## Linear difference equations

Take a population whose size in year $n+1$ is a fixed multiple of its size in year
$n$, plus a constant net migration $b$:

$$
y_{n+1} = \rho\, y_n + b, \qquad n = 0, 1, 2, \dots
$$

The constant $\rho$ is the reproduction ratio, and $b$ the yearly immigration
($b > 0$) or emigration ($b < 0$). Iterating from $y_0$,

$$
y_1 = \rho y_0 + b,
\qquad
y_2 = \rho^2 y_0 + \rho b + b,
\qquad
y_3 = \rho^3 y_0 + \rho^2 b + \rho b + b,
$$

and the pattern is a geometric sum. For $\rho \neq 1$,

$$
y_n = \rho^n y_0 + \left(1 + \rho + \cdots + \rho^{n-1}\right)b
     = \rho^n y_0 + \frac{1 - \rho^n}{1 - \rho}\,b.
$$

The first term is the descendants of the original population; the second collects
the migration of every preceding year. Rewriting it around the equilibrium makes
the long-time behavior visible:

$$
y_n = \rho^n\!\left(y_0 - \frac{b}{1 - \rho}\right) + \frac{b}{1 - \rho}.
$$

Setting $y_{n+1} = y_n$ in the equation gives the same equilibrium directly,
$y^\ast = b/(1 - \rho)$. Everything hinges on the factor $\rho^n$:

- **$\lvert\rho\rvert < 1$.** The factor $\rho^n \to 0$, so $y_n \to b/(1-\rho)$
  from any start. The equilibrium is asymptotically stable.
- **$\lvert\rho\rvert > 1$.** The factor $\rho^n$ grows without bound and $y_n$
  diverges, unless $y_0 = b/(1-\rho)$ exactly. The equilibrium is unstable.
- **$\rho = 1$.** The formula degenerates; iterating directly gives
  $y_n = y_0 + nb$, growing linearly without bound (unless $b = 0$).

For the pure model $y_{n+1} = \rho y_n$ (no migration) the equilibrium is
$y^\ast = 0$, stable for $\lvert\rho\rvert < 1$ and unstable for
$\lvert\rho\rvert > 1$: the same dichotomy the continuous equation $y' = ky$ shows
through the sign of $k$, now read off the magnitude of $\rho$.

$$
% caption: For a stable linear difference equation the iterates approach the
% equilibrium b/(1-rho) monotonically; each point is one step of the rule
% y_{n+1} = rho*y_n + b with 0 < rho < 1.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=0.55]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (-0.4,0) -- (9.2,0) node[right] {$n$};
  \draw[->, black] (0,-0.3) -- (0,7.4) node[above] {$y_n$};
  \draw[acc, dashed] (0,6) -- (8.7,6) node[right, black] {equilibrium};
  \foreach \n/\yv in {0/1,1/3.5,2/4.75,3/5.375,4/5.6875,5/5.844,6/5.922,7/5.961,8/5.980} {
    \draw[black] (\n,0) -- (\n,\yv);
    \fill[black] (\n,\yv) circle (2.6pt);
  }
\end{tikzpicture}
$$

The same linear model covers many financial calculations. There $y_n$ is an
account balance in period $n$, $\rho = 1 + r$ with $r$ the interest rate per
period, and $b$ is the deposit ($b > 0$) or payment ($b < 0$) made each period.

> **Worked example.** A recent graduate takes out a \$10,000 car loan at a
> $12\%$ annual rate and pays it off with equal monthly payments over four years.
> The monthly rate is $1\%$, so the balance $y_n$ after $n$ months follows
> $y_{n+1} = \rho y_n + b$ with $\rho = 1.01$; the payment enters as a constant
> $b < 0$, and the actual payment is $\lvert b\rvert$. From the solution formula,
>
> $$
> y_n = (1.01)^n\,(10{,}000 + 100b) - 100b.
> $$
>
> The loan is cleared when $y_{48} = 0$. Solving for $b$,
>
> $$
> b = -100\,\frac{(1.01)^{48}}{(1.01)^{48} - 1} = -263.34,
> $$
>
> a monthly payment of \$263.34. Over $48$ months the total paid is
> $48 \times 263.34 = 12{,}640.32$ dollars, of which \$10,000 is principal and
> \$2,640.32 is interest.

## The logistic difference equation

Nonlinear difference equations behave far more richly than linear ones. The
sharpest example is the discrete counterpart of the logistic model. Replacing the
derivative in $\frac{\d y}{\d t} = r y (1 - y/K)$ by a difference quotient and
rescaling the variable turns it into the **logistic map**

$$
u_{n+1} = \rho\, u_n(1 - u_n),
$$

with $\rho > 0$ a single parameter. The equilibria come from $u = \rho u(1-u)$,
that is $u = \rho u - \rho u^2$, so

$$
u^\ast = 0
\qquad\text{or}\qquad
u^\ast = \frac{\rho - 1}{\rho}.
$$

The second equilibrium is positive only for $\rho > 1$. Stability is tested by
linearizing near each fixed point. Near $u = 0$ the quadratic term is negligible
and the map reduces to $u_{n+1} \approx \rho u_n$, stable for $0 < \rho < 1$. Near
$u^\ast = (\rho-1)/\rho$, writing $u_n = u^\ast + v_n$ and dropping the quadratic
term gives

$$
v_{n+1} = (2 - \rho)\, v_n,
$$

stable for $\lvert 2 - \rho\rvert < 1$, that is $1 < \rho < 3$. The two ranges
meet at $\rho = 1$, where the equilibria coincide and stability passes from one
branch to the other.

> **Worked example.** Iterate $u_{n+1} = \rho u_n(1 - u_n)$ at $\rho = 2.8$ from
> $u_0 = 0.3$. The nonzero equilibrium is $(\rho - 1)/\rho = 1.8/2.8 = 0.6429$, and
> since $1 < \rho < 3$ it is asymptotically stable, so the sequence should approach
> it. Computing each $u_{n+1} = 2.8\,u_n(1 - u_n)$ in turn:
>
> | $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
> | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
> | $u_n$ | $0.3000$ | $0.5880$ | $0.6783$ | $0.6111$ | $0.6655$ | $0.6234$ | $0.6575$ | $0.6306$ | $0.6523$ |
>
> The values straddle $0.6429$ with shrinking swings, converging by damped
> oscillation, the behavior the cobweb spiral shows below.

A **cobweb diagram** displays the iteration geometrically. Plot the map
$y = \rho x(1-x)$ and the line $y = x$ on the same axes; their intersections are
the equilibria. Starting at $u_0$ on the horizontal axis, a vertical segment to
the parabola computes $u_1 = \rho u_0(1 - u_0)$, a horizontal segment to the line
$y = x$ transfers that value back to the axis, and repeating traces a staircase
or spiral toward the stable equilibrium.

$$
% caption: Cobweb diagram for u_{n+1} = rho*u_n(1-u_n) at rho = 2.8: iterates
% spiral inward to the nonzero equilibrium (rho-1)/rho = 0.6429, approaching with
% damped oscillation.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=3.6]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (0,0) -- (1.08,0) node[right] {$u_n$};
  \draw[->, black] (0,0) -- (0,0.84) node[above] {$u_{n+1}$};
  \draw[thick] plot[domain=0:1, samples=50] (\x, {2.8*\x*(1-\x)});
  \draw[black, dashed] (0,0) -- (0.79,0.79) node[above] {$u_{n+1} = u_n$};
  \draw[black, thin]
    (0.3,0) -- (0.3,0.588) -- (0.588,0.588) -- (0.588,0.678) -- (0.678,0.678)
    -- (0.678,0.611) -- (0.611,0.611) -- (0.611,0.665) -- (0.665,0.665)
    -- (0.665,0.623) -- (0.623,0.623);
  \fill[acc] (0.6429,0.6429) circle (0.9pt);
  \node[acc, anchor=west] at (0.70,0.50) {stable equilibrium};
  \node[black, anchor=north] at (0.3,-0.01) {$u_0$};
\end{tikzpicture}
$$

Collecting the stability results: $u = 0$ is stable for $0 \le \rho < 1$ and
$u = (\rho-1)/\rho$ is stable for $1 < \rho < 3$. Plotting both equilibria against
$\rho$, the stable portions form a continuous path that jumps from one branch to
the other at $\rho = 1$, an **exchange of stability**.

$$
% caption: Exchange of stability for the logistic map (parameter rho on the
% horizontal axis): u = 0 is stable (solid) below rho = 1, then loses stability to
% u = (rho-1)/rho, stable for 1 < rho < 3 and unstable (dashed) beyond.
\begin{tikzpicture}[>=stealth, font=\footnotesize, xscale=1.5, yscale=2.6]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (0,0) -- (3.7,0) node[right] {parameter};
  \draw[->, black] (0,-0.28) -- (0,0.95) node[above] {$u$};
  \draw[thick] (0,0) -- (1,0);
  \draw[thick, dashed] (1,0) -- (3.5,0);
  \draw[thick] plot[domain=1:3, samples=40] (\x, {1 - 1/\x});
  \draw[thick, dashed] plot[domain=3:3.5, samples=12] (\x, {1 - 1/\x});
  \foreach \r in {1,2,3} \draw[black] (\r,0.03) -- (\r,-0.03) node[below] {$\r$};
  \node[circle, fill=acc, inner sep=0pt, minimum size=3pt] at (1,0) {};
  \node[anchor=south] at (2.15,0.6) {nonzero equilibrium};
  \node[black, anchor=north] at (2.6,0) {$u = 0$};
  \node[acc, anchor=south east] at (1.0,0.05) {exchange};
\end{tikzpicture}
$$

## Period doubling and chaos

For $\rho > 3$ neither equilibrium is stable, and the iterates never settle to a
single value. Just past $\rho = 3$ the sequence approaches a **two-cycle**: after
a transient it alternates between two values. At $\rho = 3.2$ the alternation is
between $0.5130$ and $0.7995$.

> **Worked example.** Find the two-cycle of $u_{n+1} = \rho u_n(1 - u_n)$ for
> $\rho = 3.2$. A two-cycle is a pair $p \neq q$ with $q = \rho p(1 - p)$ and
> $p = \rho q(1 - q)$. Subtracting the two equations and dividing by $p - q$,
>
> $$
> p + q = 1 + \frac{1}{\rho} = \frac{\rho + 1}{\rho}.
> $$
>
> Adding them and writing $S = p + q$, $P = pq$ gives
> $P = S/\rho = (\rho + 1)/\rho^2$, so $p$ and $q$ are the roots of
>
> $$
> u^2 - \frac{\rho + 1}{\rho}\,u + \frac{\rho + 1}{\rho^2} = 0.
> $$
>
> At $\rho = 3.2$ this is $u^2 - 1.3125\,u + 0.41016 = 0$, with roots
>
> $$
> u = \frac{1.3125 \pm \sqrt{0.08203}}{2} = 0.7995 \ \text{and}\ 0.5130,
> $$
>
> matching the values the iteration alternates between.

The cobweb of a two-cycle is a rectangle traced repeatedly: the map now folds the
interval so that two points map to each other, and the fixed point at
$(\rho-1)/\rho = 0.6875$ sits inside the loop, unstable.

$$
% caption: Cobweb of the period-2 orbit at rho = 3.2: the iteration settles into a
% rectangle between the two-cycle points p = 0.513 and q = 0.80, cycling around
% the now-unstable fixed point at 0.6875.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=3.6]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (0,0) -- (1.08,0) node[right] {$u_n$};
  \draw[->, black] (0,0) -- (0,0.96) node[above] {$u_{n+1}$};
  \draw[thick] plot[domain=0:1, samples=50] (\x, {3.2*\x*(1-\x)});
  \draw[black, dashed] (0,0) -- (0.9,0.9) node[above] {$u_{n+1} = u_n$};
  \draw[black, thick] (0.513,0.513) -- (0.513,0.7995) -- (0.7995,0.7995) -- (0.7995,0.513) -- cycle;
  \node[circle, draw=acc, thick, fill=white, inner sep=0pt, minimum size=3pt] at (0.6875,0.6875) {};
  \node[black, anchor=north] at (0.513,-0.01) {$p$};
  \node[black, anchor=north] at (0.7995,-0.01) {$q$};
  \node[acc, anchor=west] at (0.71,0.65) {unstable equilibrium};
\end{tikzpicture}
$$

Raising $\rho$ further, each state of the two-cycle splits in two. At about
$\rho = 3.449$ the orbit becomes a **four-cycle**; near $\rho = 3.544$ it becomes
an eight-cycle, and periods $16, 32, \dots$ follow in quick succession. This
cascade of **period doublings** accumulates at a finite limit
$\rho_\infty \approx 3.57$. The parameter gaps between successive doublings shrink
by a nearly constant factor, the **Feigenbaum constant**
$\delta \approx 4.6692$, which recurs across a wide class of maps.

Beyond $\rho \approx 3.57$ the solutions are **chaotic**: they stay in a bounded
range but follow no periodic pattern. For $\rho = 3.65$ the iterates wander
between roughly $0.3$ and $0.9$ with no discernible order.

$$
% caption: A chaotic orbit of u_{n+1} = 3.65*u_n(1-u_n) from u_0 = 0.3: bounded
% between about 0.3 and 0.9 but aperiodic, with no repeating block of values.
\begin{tikzpicture}[>=stealth, font=\footnotesize, xscale=0.3, yscale=3.0]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (-0.5,0) -- (16.6,0) node[right] {$n$};
  \draw[->, black] (0,0) -- (0,1.08) node[above] {$u_n$};
  \draw[black] (0,1) -- (16,1);
  \draw[black, thick] plot coordinates {
    (0,0.300) (1,0.767) (2,0.653) (3,0.827) (4,0.523) (5,0.911) (6,0.297)
    (7,0.762) (8,0.661) (9,0.818) (10,0.544) (11,0.905) (12,0.313)
    (13,0.785) (14,0.617) (15,0.863)};
  \foreach \n/\uv in {0/0.300,1/0.767,2/0.653,3/0.827,4/0.523,5/0.911,6/0.297,7/0.762,8/0.661,9/0.818,10/0.544,11/0.905,12/0.313,13/0.785,14/0.617,15/0.863}
    \node[circle, fill=black, inner sep=0pt, minimum size=2.6pt] at (\n,\uv) {};
\end{tikzpicture}
$$

A hallmark of chaos is **sensitivity to initial conditions**. Two orbits of the
same map starting at $u_0 = 0.3$ and $u_0 = 0.305$ stay close for about fifteen
iterations, then diverge completely; after that, neither can be used to predict
the other. The logistic map was one of the first simple systems in which this was
recognized, in Robert May's 1974 study of insect populations: a growth parameter
too large makes long-range prediction impossible in principle, not merely in
practice.

| Range of $\rho$ | Long-time behavior of $u_n$ |
| --- | --- |
| $0 < \rho < 1$ | converges to $u = 0$ (extinction) |
| $1 < \rho < 3$ | converges to $u = (\rho-1)/\rho$ |
| $3 < \rho < 3.449$ | period-2 oscillation |
| $3.449 < \rho < 3.57$ | period $4, 8, 16, \dots$ (doubling cascade) |
| $\rho > 3.57$ | chaotic: bounded, aperiodic, sensitive to $u_0$ |

## Summary

- A **first-order difference equation** $y_{n+1} = f(y_n)$ generates a sequence by
  iteration; its equilibria are the fixed points $y^\ast = f(y^\ast)$.
- The **linear equation** $y_{n+1} = \rho y_n + b$ solves in closed form, with
  equilibrium $b/(1-\rho)$ that is stable for $\lvert\rho\rvert < 1$ and unstable
  for $\lvert\rho\rvert > 1$; the $\rho = 1$ case grows linearly. Compound
  interest, savings, and loan amortization are direct applications.
- The **logistic map** $u_{n+1} = \rho u_n(1 - u_n)$ has equilibria $0$ and
  $(\rho-1)/\rho$, with an exchange of stability at $\rho = 1$ and loss of
  stability of the nonzero branch at $\rho = 3$.
- Past $\rho = 3$ come **period doublings** at a geometric rate set by the
  Feigenbaum constant $\delta \approx 4.6692$, accumulating at
  $\rho \approx 3.57$, beyond which the dynamics are **chaotic** and sensitive to
  the initial value.

[^boyce-29]: **Boyce**, _Elementary Differential Equations_, §2.9 — First-Order Difference Equations: iteration and equilibria, the linear equation and its financial applications (Example 1, the car loan), and the logistic map with its exchange of stability, period-doubling cascade, and chaotic regime (the Feigenbaum constant and May's 1974 analysis).