Recurrence Relations

Applied Combinatorics (CC BY-SA) · appliedcombinatorics.org

A recurrence defines each term from earlier ones. Fibonacci is the archetype: f(n) = f(n−1) + f(n−2). Linear recurrences with constant coefficients always have a closed form built from the roots of a characteristic polynomial.

Iterate forward, or solve in closed form

Computing a recurrence forward is linear and exact. But a linear recurrence also has a closed form: guess f(n) = rⁿ, get a polynomial in r, and the roots give the basis. For Fibonacci the roots are the golden ratio and its conjugate, yielding Binet's formula.

Scheme

; Forward iteration: O(n), exact integers
(define (fib n)
  (let loop ((a 0) (b 1) (k 0))
    (if (= k n) a (loop b (+ a b) (+ k 1)))))

(define (fibs upto)
  (let loop ((n 0) (acc '()))
    (if (> n upto) (reverse acc)
        (loop (+ n 1) (cons (fib n) acc)))))

(display "fib 0..10 = ") (display (fibs 10)) (newline)
(display "fib 30    = ") (display (fib 30)) (newline)   ; 832040

; ratio of consecutive terms approaches the golden ratio
(display "f31/f30   = ") (display (/ (fib 31) (fib 30))) (newline)

Neighbors

🧮 Ch.5 Generating Functions — turn a recurrence into a rational generating function and read off the closed form
⚙ Algorithms — recurrences bound divide-and-conquer running time

← Generating Functions · 5 of 10 by june.kim Partially Ordered Sets · 7 of 10 →