Skip to main content

Solving Linear Recurrences and Extracting Coefficients

What This Concept Is​

Once a recurrence is derived, the next question is whether it can be solved or at least understood well enough to predict values and growth. For this module, the goal is not exhaustive recurrence theory; it is to learn two practical moves:

  • Characteristic-root method for linear homogeneous recurrences with constant coefficients.
  • Generating-function method for arbitrary linear recurrences (including nonhomogeneous ones), extracting coefficients once a closed form for $A(x)$ is obtained.

Characteristic-root recipe (linear homogeneous, constant coefficients). Given

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k},$$

form the characteristic polynomial $x^k = c_1 x^{k-1} + c_2 x^{k-2} + \cdots + c_k$. If its roots are distinct, $r_1, \ldots, r_k$, the general solution is $a_n = \alpha_1 r_1^n + \cdots + \alpha_k r_k^n$, and the constants $\alpha_i$ are pinned down by the initial conditions. Repeated roots introduce polynomial-in-$n$ multipliers: a double root $r$ contributes $(\alpha + \beta n) r^n$.

Generating-function recipe. Multiply the recurrence by $x^n$, sum over $n$, solve algebraically for $A(x)$, decompose by partial fractions, and read coefficients using $\frac{1}{1 - rx} = \sum_{n\ge 0} r^n x^n$.

Both methods produce the same closed form for linear cases; the generating-function approach generalizes further (to nonlinear or nonhomogeneous forcing terms).

A dictionary to memorize. These three identities together solve most linear cases you will meet this semester:

$$\frac{1}{1 - rx} = \sum_{n \ge 0} r^n x^n, \quad \frac{1}{(1 - rx)^2} = \sum_{n \ge 0} (n+1) r^n x^n, \quad \frac{x}{1 - x - x^2} = \sum_{n \ge 0} F_n x^n.$$

The first handles any distinct-root linear recurrence after partial fractions. The second handles the repeated-root case (a double root $r$ contributes terms of the form $(\alpha + \beta n) r^n$). The third is the Fibonacci encoding that you should be able to write from memory.

Why It Matters Here​

You need enough recurrence fluency to:

  • verify a conjectured counting formula against the recurrence it should satisfy.
  • move from recursive description to a usable closed-form expression.
  • predict asymptotic growth (dominant-root analysis: $a_n \sim C r_{\max}^n$ where $r_{\max}$ is the largest-magnitude root).
  • prepare for divide-and-conquer analysis and dynamic programming in later semesters.

This is a bridge topic between discrete math and algorithms. The Master Theorem you meet in Semester 2 is a pre-solved table of characteristic-root results for divide-and-conquer recurrences; understanding it requires seeing the method at least once from scratch.

Dominant-root analysis in one sentence. If $r_{\max}$ is the root of largest modulus in the characteristic polynomial, then $a_n = \Theta(r_{\max}^n)$ (with a polynomial correction if $r_{\max}$ is a repeated root). This is the cleanest way to talk about "this algorithm runs in time $\Theta(\phi^n)$" without messy case analysis on initial conditions.

Concrete Examples​

Example 1: Fibonacci via characteristic roots. Take $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 0, a_1 = 1$ (standard Fibonacci). Characteristic polynomial $x^2 = x + 1$, i.e., $x^2 - x - 1 = 0$. Roots $\phi = \frac{1+\sqrt 5}{2}, \psi = \frac{1 - \sqrt 5}{2}$.

General solution: $a_n = \alpha \phi^n + \beta \psi^n$. From $a_0 = 0$: $\alpha + \beta = 0$. From $a_1 = 1$: $\alpha\phi + \beta\psi = 1$. Solve: $\alpha = 1/\sqrt 5, \beta = -1/\sqrt 5$. Binet's formula:

$$F_n = \frac{\phi^n - \psi^n}{\sqrt 5}.$$

Since $|\psi| < 1$, the second term is negligible for large $n$: $F_n \sim \phi^n / \sqrt 5$. Growth is exponential at rate $\phi \approx 1.618$. The closest-integer rule: $F_n = \operatorname{round}(\phi^n / \sqrt 5)$ for all $n \ge 0$, a striking integer consequence of an irrational formula.

Example 2: Fibonacci via generating functions. Let $A(x) = \sum_n F_n x^n$. Multiply the recurrence by $x^n$ and sum over $n \ge 2$:

$$\sum_{n\ge 2} F_n x^n = \sum_{n\ge 2} F_{n-1} x^n + \sum_{n\ge 2} F_{n-2} x^n.$$

Rewrite: $A(x) - F_0 - F_1 x = x(A(x) - F_0) + x^2 A(x)$. With $F_0 = 0, F_1 = 1$: $A(x) - x = xA(x) + x^2 A(x)$, giving

$$A(x) = \frac{x}{1 - x - x^2}.$$

Partial fractions give $A(x) = \frac{1}{\sqrt 5}\left(\frac{1}{1 - \phi x} - \frac{1}{1 - \psi x}\right)$, from which $[x^n] A(x) = (\phi^n - \psi^n)/\sqrt 5$ -- Binet's formula again.

Notice how the two methods end at the same answer but reveal different things. The characteristic-root derivation makes the roots ($\phi, \psi$) visible first; the generating-function derivation makes the denominator shape ($1 - x - x^2$) visible first, which is closely tied to the combinatorial recurrence structure. Fluency is the ability to flip between the two views.

Example 3: nonhomogeneous linear. Solve $c_n = c_{n-1} + 3$ with $c_0 = 4$. The homogeneous part is $c_n = c_{n-1}$, with solution $c_n = \alpha$. A particular solution to the full recurrence is $c_n = 3n + \beta$. Substitute: $3n + \beta = 3(n-1) + \beta + 3$, which is an identity -- so any $\beta$ works for the particular form. The general solution is $c_n = \alpha + 3n$. Apply $c_0 = 4$: $\alpha = 4$. Answer: $c_n = 4 + 3n$. Check: $c_1 = 7 = 4 + 3$; $c_2 = 10 = 7 + 3$. ✓

Common Confusion / Misconceptions​

  • Mechanical algebra without model check. Solving an equation without remembering what $a_n$ counts. If a proposed closed form gives noninteger or negative values for a counting sequence, you have a bug. Counting sequences are always integer-valued.
  • Wrong initial conditions. Using the recurrence before checking that $a_0, a_1, \ldots$ align with the combinatorial object definition. A recurrence is a structural law; the initial conditions pick out which sequence it governs.
  • Forgetting repeated roots. If the characteristic polynomial has a double root $r$, the general solution is $(\alpha + \beta n)r^n$, not $\alpha r^n + \beta r^n$ (those are the same term).
  • Partial-fraction sign errors. When decomposing $\frac{1}{(1-rx)(1-sx)} = \frac{A}{1-rx} + \frac{B}{1-sx}$, sign errors in $A, B$ flip the growth direction. Always verify on $x = 0$.
  • "Complex roots mean no closed form." If the characteristic polynomial has a complex conjugate pair $r, \bar r$ with $r = \rho e^{i\theta}$, the real solution is $\rho^n(\alpha \cos(n\theta) + \beta \sin(n\theta))$ -- still a closed form, just with trigonometric shape. Damped oscillations ($\rho < 1$) or growing oscillations ($\rho > 1$) are both common in engineering-flavored recurrences.

How To Use It​

When solving a recurrence:

  1. restate what the sequence counts; write down the combinatorial definition of $a_n$.
  2. verify the initial conditions by computing $a_0, a_1, a_2$ from the combinatorial model directly.
  3. compute a few values from the recurrence as an independent cross-check.
  4. choose a method: characteristic roots for linear homogeneous with constant coefficients; generating functions for nonhomogeneous or when a product form is natural.
  5. confirm that the resulting formula matches the first computed values.
  6. analyze asymptotics: the dominant characteristic root determines exponential growth rate.
  7. treat the closed form as a conjecture you have tested until you prove it by induction against the recurrence.

Treat solving as model validation, not detached algebra.

Short decision procedure. If the recurrence is linear homogeneous with constant coefficients and small order, use characteristic roots -- faster, less bookkeeping. If the recurrence is nonhomogeneous, or if you suspect combinatorial structure you want to prove, use generating functions -- more scaffolding, but it carries combinatorial meaning through the derivation. If the recurrence is nonlinear (Catalan-like), generating functions plus functional equations (quadratic in $A(x)$) is your best tool.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: the Master Theorem for $T(n) = aT(n/b) + f(n)$ is a specialized solver drawing on the same asymptotic reasoning as dominant-root analysis. Akra-Bazzi generalizes it using Mellin transforms (a generating-function cousin).
  • Semester 3 data structures: amortized analyses via accounting and potential functions are recurrence solvers in disguise. Randomized data-structure depth bounds use probabilistic recurrence arguments.
  • Semester 4 databases: cost models for iterative query evaluation solve recurrences for convergence of recursive CTEs and fixed-point computations.
  • Semester 5 OS & 6 distributed systems: queueing steady-state solutions to M/M/1 use solving a linear recurrence in probabilities; consensus-round bounds (Paxos, Raft) use linear-recurrence growth-rate arguments.
  • Machine learning (later): linear recurrences underlie autoregressive models and Kalman filters; dominant-root analysis predicts stability of dynamic systems.

Check Yourself​

  1. Why should counting sequences always produce integers in every valid closed form?
  2. What is the role of initial conditions in determining a unique solution? How many are required for an order-$k$ recurrence?
  3. Why is it useful to compute small values directly before trusting a closed form?
  4. For $a_n = 3a_{n-1} - 2a_{n-2}$ with $a_0 = 2, a_1 = 3$, solve by characteristic roots.
  5. What is the dominant root of $a_n = 2a_{n-1} + 3a_{n-2}$? Without solving exactly, give the asymptotic growth rate.
  6. Why does a double root $r$ produce an extra factor of $n$? (Hint: in the generating function picture, $\frac{1}{(1-rx)^2}$ has $(n+1) r^n$ as its coefficient.)
  7. Given $a_n = 2^n - 1$, find a linear recurrence of lowest order that $(a_n)$ satisfies. Verify against initial conditions.

Mini Drill or Application​

For each recurrence:

  1. compute the first five terms.
  2. state what kind of counting model might generate it.
  3. say whether a generating-function or characteristic-root approach seems more natural.
  4. if linear and homogeneous, solve by characteristic roots.

Recurrences:

  1. $a_n = 2 a_{n-1}$, $a_0 = 1$. (Should give $a_n = 2^n$.)
  2. $b_n = b_{n-1} + b_{n-2}$, $b_0 = 2, b_1 = 3$. (Fibonacci-like; solve and verify.)
  3. $c_n = c_{n-1} + 3$, $c_0 = 4$. (Redo Example 3 from scratch.)
  4. $d_n = 4 d_{n-1} - 4 d_{n-2}$, $d_0 = 1, d_1 = 3$. (Has a repeated root; watch the form.)
  5. $e_n = 2 e_{n-1} + 1$, $e_0 = 0$. (Towers of Hanoi; solve to $e_n = 2^n - 1$.)
  6. $g_n = g_{n-1} + 2 g_{n-2}$, $g_0 = 1, g_1 = 1$. (Distinct roots; find the closed form and its dominant root.)
  7. $h_n = h_{n-2}$ with $h_0 = 1, h_1 = 0$. (Period-$2$ sequence; note how characteristic roots $\pm 1$ produce an oscillation rather than growth.)

Read This Only If Stuck​