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 suitable recurrences whose generating-function equations can be solved, including many nonhomogeneous constant-coefficient cases, 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},$$

Assume $c_k \ne 0$ so this is genuinely order $k$, and the recurrence holds for $n \ge 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 when the initial data and dominant roots justify it; check for zero coefficients, repeated roots and oscillation.
  • prepare for divide-and-conquer analysis and dynamic programming in later semesters.

This is a bridge to recurrence analysis in algorithms. Divide-and-conquer recurrences involve smaller input sizes such as n/2; the Master Theorem analyzes their recursion-tree work under additional hypotheses. It is not simply a table of solutions to constant-coefficient recurrences indexed by n−1 and n−2.

Dominant roots need initial data. A unique largest-modulus positive simple root r gives a_n ~ C r^n only when its coefficient C is nonzero. A repeated active root can introduce powers of n; multiple roots of equal modulus can produce cancellation or oscillation. For example, a_n=3a_(n−1)−2a_(n−2) has roots 2 and 1, but initial values a_0=a_1=1 give the constant sequence 1. Root magnitude alone does not determine the sequence’s growth.

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 using the roots whose coefficients are nonzero; check multiplicity and possible oscillation.
  7. justify the formula by a valid coefficient derivation or by substitution, initial values and uniqueness of the recurrence solution. Agreement on a few terms alone is only a test.

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 to the workshop model​

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

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. Find the characteristic roots of $a_n = 2a_{n-1} + 3a_{n-2}$. Why are initial values needed to claim a growth rate? Compare $a_0=a_1=1$ with $a_0=1, a_1=-1$.
  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 both a first-order nonhomogeneous and a second-order homogeneous constant-coefficient recurrence 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​

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

Initial corrections and exact coefficients​

For a recurrence valid only from n=2, summing it from zero silently invents equations for the initial values. Write A−a₀−a₁x on the left and the corresponding shifted corrections on the right. Then verify the first few coefficients as a diagnostic, followed by a general recurrence or coefficient argument establishing equality.

Characteristic-root formulas apply to constant-coefficient linear recurrences with the specified initial data. Formal generating functions also encode many other recurrences but do not guarantee a convenient solvable rational expression. Floating evaluation of an exact closed form can introduce rounding even when the sequence consists of integers. Transfer: solve P9 exactly and compare the two numerator choices in the worked no-11/tiling example.

After your attempt use practice feedback and model contracts to check the argument.