skip to content

For the counting recurrence f(n)=f(n-1)+f(n-2), what does solving the characteristic equation r^2=r+1 give you that iteration does not?

level: seniorimportance: should knowfreq 44%

answer

  1. guess a geometric solution
  2. substitute r^n, divide out
  3. the polynomial's roots are the bases
  4. two roots, two constants, two base cases
  5. largest magnitude sets the growth

basics

~10 s

A closed form and a growth rate. Guessing f(n)=r^n turns the recurrence into r^2=r+1, whose roots (1+sqrt5)/2 and (1-sqrt5)/2 combine as Ar1^n + Br2^n; the larger root, about 1.618, is the per-step growth factor.

solid answer

~40 s

Guess that a geometric sequence `r^n` satisfies the recurrence. Substituting and dividing by `r^(n-2)` turns it into the polynomial `r^2 = r + 1`, whose roots are about `1.618` and `-0.618`. Because a second-order linear homogeneous recurrence has a two-dimensional solution space, and two distinct roots give two independent solutions, every solution is `A*1.618^n + B*(-0.618)^n`; the two initial conditions pin `A` and `B`. Iteration gives you one value at a time and never states the growth. The closed form does: the second root has magnitude below one, so its term decays, and the count multiplies by roughly `1.618` per added slot. What the closed form is bad at is exact values — the roots are irrational, so for an exact integer you still iterate.

go deeper

for a junior

Know that a recurrence of this shape has a closed form and that it is found by solving a small polynomial, not by pattern-matching the first few values.

for a middle

Be able to carry out the substitution, produce the characteristic equation, and explain why both roots appear in the general solution with constants set by the starting values.

for a senior

Show the operational read: the dominant root is the per-step growth factor, the decaying root is noise, and exact counts still come from iterating because the roots are irrational.

for a principal

Treat the exponent as the decision input. Whether a configuration space is walkable turns on the dominant root, and that answer arrives before any implementation choice is made.

## From a recurrence to a polynomial A **linear homogeneous recurrence with constant coefficients** looks like `f(n) = c1*f(n-1) + ... + ck*f(n-k)`: every earlier term appears to the first power, multiplied by a constant, with no extra additive term. The counting recurrence `f(n) = f(n-1) + f(n-2)` is of this family, with order `k = 2`. The method starts from a guess. Try a purely geometric sequence `f(n) = r^n` for some non-zero `r`. Substituting gives `r^n = r^(n-1) + r^(n-2)`, and dividing through by `r^(n-2)` leaves a polynomial with no `n` in it at all: `r^2 = r + 1`, i.e. `r^2 - r - 1 = 0`. That is the **characteristic equation**. Its roots are `r1 = (1 + sqrt5)/2 ≈ 1.61803` and `r2 = (1 - sqrt5)/2 ≈ -0.61803`. Note that the coefficients of the recurrence are 1 and 1 and neither root is 1 — reading growth rates off the coefficients is the standard mistake. ## Why the general solution mixes both roots Two facts do the work: 1. If `u(n)` and `v(n)` both satisfy the recurrence, so does `A*u(n) + B*v(n)` — the recurrence is linear, so solutions form a vector space. 2. That space has dimension exactly `k`, because a solution is completely determined by its first `k` values, and those `k` values are free. So for `k = 2`, two **independent** solutions span everything. Distinct roots give independent geometric sequences, hence `f(n) = A*r1^n + B*r2^n` is the general solution, and the two initial conditions choose the one you want. For the schedule count with `f(0) = 1` and `f(1) = 2`: `A + B = 1` and `A*r1 + B*r2 = 2`, which solve to `A ≈ 1.17082`, `B ≈ -0.17082`. Check at `n = 2`: `1.17082 * 2.61803 - 0.17082 * 0.38197 ≈ 3.065 - 0.065 = 3`, agreeing with the brute-force count. ## What the dominant root buys you | root | value | its term here | behaviour as n grows | |---|---|---|---| | r1 | ≈ 1.618 | `1.171 * r1^n` | grows, multiplying by ≈1.618 per step | | r2 | ≈ -0.618 | `-0.171 * r2^n` | alternates sign, shrinks toward zero | Because `|r2| < 1`, the second term vanishes. Two consequences follow, and they are the reason anyone solves the characteristic equation at all: - **A growth statement.** The ratio `f(n+1)/f(n)` converges to `≈ 1.618`. That single number answers "what does one more slot cost me?" without computing any value. - **A one-shot estimate.** `f(200)` is `≈ 1.171 * 1.618^200` — an exponent you can reason about immediately, where iteration needs 200 steps to say anything. In this particular instance the decaying term never exceeds `0.171` in magnitude, comfortably under `0.5`, so `f(n)` is the nearest integer to `1.17082 * 1.618^n` for every `n`. That is a property of these constants, not a general law. The dominant-root reading needs two conditions to be honest: the root of largest magnitude must be **strictly** larger than the others, and its coefficient must be non-zero. Roots of equal magnitude (`+r` and `-r`, say) produce an oscillation with no single growth factor. ## Where the closed form is the wrong tool - **Exactness.** The roots are irrational. Evaluating the closed form in finite-precision arithmetic drifts, and for a count — an integer — a drifting answer is simply wrong. Iterating the recurrence is exact, and costs `n` additions. - **Magnitude.** The counts themselves outgrow fixed-width integers quickly, so an exact result eventually needs arbitrary-precision accumulation regardless of which method produced it. - **Scope.** The method requires linearity, constant coefficients and a fixed order. A recurrence whose coefficients depend on `n`, or whose number of terms grows with `n`, has no characteristic polynomial to solve. The practical division of labour: **use the closed form for the exponent** — capacity claims, feasibility arguments, "how much worse is n+1" — and **use iteration for the number**. ## What is actually being checked - You derive the polynomial rather than reciting it, and you can say why dividing by `r^(n-2)` is legitimate. - You know the number of arbitrary constants equals the order, and that the initial conditions determine them. - You read the growth off the dominant root, with the right caveats. - You do not claim the closed form is the better way to compute an exact value.

  • What does it mean if the characteristic roots come out complex?
    Complex roots arrive as a conjugate pair, and so do the constants, so the sequence stays real. Rewriting the pair in polar form gives `modulus^n` times a sine-and-cosine combination: the modulus is still the growth rate, while the angle sets the period of the oscillation riding on it.
  • How many initial conditions does a recurrence with a lookback of k positions need, and why exactly that many?
    Exactly `k`. The first `k` values are free and every later value is forced, so the solution space has dimension `k` and needs `k` independent conditions to select one member. Fewer leaves the constants underdetermined; more risks contradicting the recurrence itself.
  • Does the root of largest magnitude always determine the growth?
    Only when it is strictly larger than every other root in magnitude and its coefficient is non-zero. If two roots share the largest magnitude — `+r` and `-r`, for instance — the terms interfere and the sequence oscillates rather than settling to a single per-step factor.

saying these in an interview costs you the question

  • Reads the growth bases off the recurrence's coefficients instead of the roots
  • Keeps only the dominant root and then cannot match both initial conditions
  • Claims the closed form is the accurate way to compute an exact count
  • Applies characteristic roots to a recurrence whose coefficients depend on n
  • Says a negative root means the count itself can turn negative