Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 36 ยท Recurrences and Generating Functions

Solving Linear Recurrences

Solve linear recurrences with constant coefficients using the characteristic equation: distinct and repeated roots, Binet's formula, sympy rsolve and matrix powers.

A linear recurrence with constant coefficients looks like a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}. Fibonacci is the best known, but they appear all over counting. The beautiful fact: every such recurrence has a closed form that you can find with a little algebra, no guessing.

This lesson solves the homogeneous case (no extra terms), then adds a constant term, and shows two computer shortcuts: sympy.rsolve and matrix powers. It continues from Recurrence Relations.

The idea: try geometric sequences

Guess a_n = r^n. Plug it into a_n = a_{n-1} + a_{n-2}: r^n = r^{n-1} + r^{n-2}. Divide by r^{n-2}:

r^2 = r + 1, i.e. r^2 - r - 1 = 0.

This is the characteristic equation. Its roots are phi = (1+sqrt5)/2 and psi = (1-sqrt5)/2. Any combination A phi^n + B psi^n also satisfies the recurrence (linearity), and the two constants A, B are chosen to match a_0 and a_1. For Fibonacci this gives Binet's formula:

F_n = (phi^n - psi^n) / sqrt5.

Python Binet's formula against the loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ratio of consecutive terms tends to phi, the dominant root: for large n the term with the biggest |r| wins. Floating-point round works here up to about n = 70; beyond that use integers (the matrix method below).

The method, step by step

For a_n = c_1 a_{n-1} + ... + c_k a_{n-k}:

  1. Write the characteristic polynomial r^k - c_1 r^{k-1} - ... - c_k = 0.
  2. Find its roots.
  3. Distinct roots r_1, ..., r_k: a_n = A_1 r_1^n + ... + A_k r_k^n.
  4. A root r repeated m times: it contributes (A_0 + A_1 n + ... + A_{m-1} n^{m-1}) r^n.
  5. Plug in the initial values and solve the linear system for the constants.

Example with distinct roots

a_n = 5 a_{n-1} - 6 a_{n-2}, a_0 = 2, a_1 = 5. The characteristic equation r^2 - 5r + 6 = 0 has roots 2 and 3, so a_n = A 2^n + B 3^n. From A + B = 2 and 2A + 3B = 5: B = 1, A = 1. So a_n = 2^n + 3^n.

Example with a repeated root

a_n = 4 a_{n-1} - 4 a_{n-2}, a_0 = 1, a_1 = 6. The equation r^2 - 4r + 4 = (r-2)^2 has the double root 2, so a_n = (A + B n) 2^n. The conditions give A = 1, B = 2: a_n = (1 + 2n) 2^n.

Python sympy.rsolve

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

rsolve prints 2**n + 4*2**(n - 1)*n, which simplifies to (1 + 2n) 2^n, matching the hand calculation. The third line solves the Hanoi recurrence a_n = 2 a_{n-1} + 1 and returns 2**n - 1. The last line uses the matrix [[1,1],[1,0]]: its n-th power contains Fibonacci numbers, and the exact integer arithmetic of sympy gives F_30 = 832040.

Non-homogeneous recurrences

If the recurrence has an extra term, such as a_n = 2 a_{n-1} + 1, solve in two parts: a particular solution that fits the extra term, plus the general solution of the homogeneous part. For a constant term, try a constant c: c = 2c + 1 gives c = -1. The homogeneous part gives A 2^n, so a_n = A 2^n - 1, and a_0 = 0 gives A = 1. If the extra term is a polynomial in n, try a polynomial of the same degree; if it clashes with a homogeneous solution, multiply by n.

Matrix powers: fast and exact

Any order-k linear recurrence is v_n = M v_{n-1} for a k x k companion matrix. Computing M^n by repeated squaring takes O(k^3 log n) steps, so you can find a_{10^18} modulo a prime in microseconds. This is the standard trick when a competitive-programming problem asks for the n-th term for gigantic n.

flowchart LR
    A["Recurrence"] --> B["Characteristic equation"]
    B --> C["Roots"]
    C --> D["General solution with unknown constants"]
    D --> E["Fit initial values"]
    E --> F["Closed form"]

From recurrence to closed form in five moves.

Not every counting recurrence is linear with constant coefficients. Catalan numbers, partitions and Stirling numbers need generating functions or direct formulas instead.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the characteristic equation of a(n) = 5 a(n-1) - 6 a(n-2)?

    Substitute a(n) = r^n and divide by r^(n-2): r^2 = 5r - 6, so r^2 - 5r + 6 = 0 with roots 2 and 3.
  2. 2. A characteristic equation has the double root r = 3. What is the form of the general solution?

    A root of multiplicity m contributes a polynomial of degree m-1 in n times r^n.
  3. 3. What closed form solves a(n) = 2 a(n-1) + 1 with a(0) = 0?

    A particular solution is -1, the homogeneous part is A 2^n, and a(0) = 0 gives A = 1.
  4. 4. Why does F(n+1)/F(n) approach (1 + sqrt5)/2?

    |psi| < 1, so psi^n vanishes and F(n) is about phi^n / sqrt5.

Summary

  • Try r^n to get the characteristic equation; roots give the building blocks of the solution.
  • Distinct roots give A r^n; a root of multiplicity m gives a degree m-1 polynomial times r^n.
  • Initial conditions fix the constants; add a particular solution for an inhomogeneous term.
  • sympy.rsolve and matrix exponentiation do the same job by computer.

Next: Generating Functions