# Recurrence Relation

**Type:** Concept  
**Domain:** Discrete Mathematics  
**Codex URL:** /mathematics/discrete/recurrence-relation/  
**Entry status:** Live — v1.0 (2026-05-27)

## Summary
Defines sequence terms using previous terms. Fibonacci is the classic example.

## Fibonacci recurrence
Fₙ=Fₙ₋₁+Fₙ₋₂, F₁=1, F₂=1

## Binet's formula
Substituting Fₙ=rⁿ gives characteristic equation r²=r+1 (the golden ratio equation!). Solution: Fₙ=(φⁿ−ψⁿ)/√5, always an integer despite irrational components.

## Algorithm analysis
Merge sort: T(n)=2T(n/2)+O(n) → O(n log n) via Master Theorem.

## Master Theorem
For T(n)=aT(n/b)+f(n), classifies solution based on comparing f(n) to n^(log_b a).

## Generating functions
Fibonacci: G(x)=x/(1−x−x²) — encodes entire sequence as power series coefficients.

## Historical origins — predates Fibonacci
Piṅgala (c.200 BCE), Virahāṅka (c.600-800 CE), Hemachandra (c.1150 CE) — Indian prosody, syllable-pattern counting, centuries before Fibonacci's 1202 CE *Liber Abaci* introduced it to Europe via a rabbit-population problem.

## Sources
### Tier 1
- Graham, R.L., Knuth, D.E. and Patashnik, O. (1994). *Concrete Mathematics*. 2nd ed.
- Cormen, T.H. et al. (2022). *Introduction to Algorithms*. 4th ed.
### Tier 2
- Plofker, K. (2009). *Mathematics in India*.

---
*Mathematics Codex entry v1.0 — added 2026-05-27 — thecodex.expert/mathematics/*