A sequence is a function from the naturals to some codomain. The interesting question is never "what is the next term?" but "what is the closed form?" Recurrence relations define sequences by self-reference. Solving them means eliminating the self-reference. Induction proves the solution is correct.
Arithmetic sequences
Each term differs from the previous by a constant d. The closed form is a(n) = a(0) + dn. The sum of the first n terms is n(a(0) + a(n))/2. These are linear functions in disguise.
Scheme
; Arithmetic sequence: a(n) = a0 + d*n
(define (arith a0 d n) (+ a0 (* d n)))
; Example: 3, 7, 11, 15, ... (a0=3, d=4)
(display "First 6 terms: ")
(let loop ((i 0))
(when (< i 6)
(display (arith 34 i))
(display " ")
(loop (+ i 1))))
(newline)
; Sum of arithmetic sequence: n * (a0 + an) / 2
(define (arith-sum a0 d n)
(/ (* (+ n 1) (+ a0 (arith a0 d n))) 2))
(display "Sum of first 6 terms: ")
(display (arith-sum 345)) ; 3+7+11+15+19+23 = 78
Python
# Arithmetic sequencedef arith(a0, d, n):
return a0 + d * n
terms = [arith(3, 4, i) for i inrange(6)]
print(f"First 6 terms: {terms}")
print(f"Sum: {sum(terms)}")
Geometric sequences
Each term is the previous multiplied by a constant ratio r. The closed form is a(n) = a(0) * r^n. The partial sum is a(0)(r^n - 1)/(r - 1) when r is not 1. Exponential growth lives here.
Scheme
; Geometric sequence: a(n) = a0 * r^n
(define (geom a0 r n)
(if (= n 0) a0
(* a0 (expt r n))))
; Example: 2, 6, 18, 54, ... (a0=2, r=3)
(display "First 5 terms: ")
(let loop ((i 0))
(when (< i 5)
(display (geom 23 i))
(display " ")
(loop (+ i 1))))
(newline)
; Partial sum: a0 * (r^n - 1) / (r - 1)
(define (geom-sum a0 r n)
(/ (* a0 (- (expt r (+ n 1)) 1)) (- r 1)))
(display "Sum of first 5 terms: ")
(display (geom-sum 234)) ; 2+6+18+54+162 = 242
Python
# Geometric sequencedef geom(a0, r, n):
return a0 * r ** n
terms = [geom(2, 3, i) for i inrange(5)]
print(f"First 5 terms: {terms}")
print(f"Sum: {sum(terms)}")
Recurrence relations
A recurrence defines each term using previous terms. The Fibonacci sequence is the classic: F(n) = F(n-1) + F(n-2). A linear homogeneous recurrence with constant coefficients can be solved by finding roots of its characteristic equation. The characteristic root technique turns a recursive definition into a closed formula.
Scheme
; Fibonacci: F(0)=0, F(1)=1, F(n) = F(n-1) + F(n-2)
(define (fib n)
(if (< n 2) n
(let loop ((a 0) (b 1) (i 2))
(if (= i n) (+ a b)
(loop b (+ a b) (+ i 1))))))
(display "Fibonacci 0..10: ")
(let loop ((i 0))
(when (<= i 10)
(display (fib i))
(display " ")
(loop (+ i 1))))
(newline)
; Tower of Hanoi: T(n) = 2*T(n-1) + 1, T(0)=0; Closed form: T(n) = 2^n - 1
(define (hanoi n) (- (expt 2 n) 1))
(display "Hanoi moves for 1..6 discs: ")
(let loop ((i 1))
(when (<= i 6)
(display (hanoi i))
(display " ")
(loop (+ i 1))))
Python
# Fibonacci (iterative)def fib(n):
a, b = 0, 1for _ inrange(n):
a, b = b, a + b
return a
print(f"Fibonacci 0..10: {[fib(i) for i in range(11)]}")
print(f"Hanoi moves: {[2**i - 1 for i in range(1, 7)]}")
Solving recurrences: the characteristic root method
For a(n) = c1*a(n-1) + c2*a(n-2), guess a(n) = r^n. Substituting gives r^2 = c1*r + c2. Solve this quadratic for r. If you get two distinct roots r1 and r2, the general solution is a(n) = A*r1^n + B*r2^n, where A and B come from initial conditions.
Scheme
; Solve: a(n) = a(n-1) + 2*a(n-2), a(0)=0, a(1)=1; Characteristic equation: r^2 = r + 2; Roots: r = 2 and r = -1; General: a(n) = A*2^n + B*(-1)^n; From a(0)=0: A + B = 0; From a(1)=1: 2A - B = 1; So A = 1/3, B = -1/3; Closed form
(define (closed n)
(/ (- (expt 2 n) (expt -1 n)) 3))
; Verify against recurrence
(define (recur n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (recur (- n 1)) (* 2 (recur (- n 2)))))))
(display "Closed: ")
(let loop ((i 0))
(when (< i 8)
(display (closed i)) (display " ")
(loop (+ i 1))))
(newline)
(display "Recurrence:")
(let loop ((i 0))
(when (< i 8)
(display " ") (display (recur i))
(loop (+ i 1))))
Python
# Characteristic root method
closed = lambda n: (2**n - (-1)**n) // 3def recur(n):
if n < 2: return n
a, b = 0, 1for _ inrange(n - 1):
a, b = b, b + 2*a
return b
for label, f in [("Closed", closed), ("Recur", recur)]:
print(f"{label}: {[f(i) for i in range(8)]}")
Proof by induction
Induction proves a statement P(n) for all n >= 0. Prove P(0) (base case). Then prove that P(k) implies P(k+1) (inductive step). The domino analogy: knock over the first, and every domino falls. Here we verify (not prove, since programs check instances) the classic sum formula.
Scheme
; Verify by induction: sum(0..n) = n*(n+1)/2; Base case: sum(0..0) = 0 = 0*1/2. Check.; Inductive step: if sum(0..k) = k*(k+1)/2,; then sum(0..k+1) = k*(k+1)/2 + (k+1) = (k+1)*(k+2)/2.
(define (sum-formula n) (/ (* n (+ n 1)) 2))
(define (sum-direct n)
(let loop ((i 0) (acc 0))
(if (> i n) acc
(loop (+ i 1) (+ acc i)))))
; Check both agree for n = 0..20
(define (verify n)
(let loop ((i 0) (all-ok #t))
(if (> i n)
all-ok
(loop (+ i 1)
(and all-ok (= (sum-formula i) (sum-direct i)))))))
(display "sum(0..10) by formula: ")
(display (sum-formula 10)) (newline) ; 55
(display "sum(0..10) directly: ")
(display (sum-direct 10)) (newline) ; 55
(display "All match for 0..20? ")
(display (verify 20))
Python
# Verify sum formula by checking instances
formula = lambda n: n * (n + 1) // 2
direct = lambda n: sum(range(n + 1))
print(f"sum(0..10) formula: {formula(10)}")
print(f"sum(0..10) direct: {direct(10)}")
print(f"All match 0..20? {all(formula(i) == direct(i) for i in range(21))}")
Notation reference
Math
Scheme
Python
Meaning
a(n) = a(0) + dn
(arith a0 d n)
a0 + d*n
Arithmetic closed form
a(n) = a(0) * r^n
(geom a0 r n)
a0 * r**n
Geometric closed form
r^2 = c1*r + c2
solve by hand
solve by hand
Characteristic equation
P(0) and P(k) implies P(k+1)
verify instances
verify instances
Induction
Neighbors
Other chapter pages
Milewski Ch.19 โ F-algebras and catamorphisms: recursion as a categorical pattern
Levin Ch.5 โ generating functions encode sequences as formal power series
Levin treats sequences as functions from naturals. The Scheme implementations use iterative loops where possible to avoid stack overflow on large inputs. The characteristic root method is demonstrated but the algebra (solving quadratics, plugging in initial conditions) happens by hand. Programs verify the result, they do not derive it.
Recurrence relation