Pattern Recognition
Mathematics advances by the interplay of conjecture and proof. Pattern recognition — the art of observing regularity in data and formulating precise conjectures — is the creative engine that drives discovery. Euler, Gauss, and Ramanujan were supreme pattern-finders whose conjectures shaped centuries of subsequent mathematics. This skill covers systematic methods for detecting patterns, generating conjectures, and calibrating confidence before committing to a proof attempt.
Agent affinity: ramanujan (intuitive pattern discovery, sequence analysis, identity generation)
Concept IDs: math-pattern-recognition, math-experimental-probability, math-data-representation, math-functions
Part I — Sequence Analysis
The OEIS (On-Line Encyclopedia of Integer Sequences)
The OEIS (oeis.org), founded by Neil Sloane in 1964 and now containing over 370,000 sequences, is the single most important resource for pattern recognition in mathematics. Given the first several terms of a sequence, searching the OEIS often identifies the sequence, its name, its generating function, known formulas, and references.
Strategy. When encountering an unfamiliar sequence:
- Compute at least 6-8 terms.
- Search the OEIS by the terms.
- If no match, compute the sequence of first differences, second differences, or ratios and search those.
- If still no match, try looking at the sequence modulo small primes.
Recurrence Relations
A recurrence relation defines each term as a function of previous terms.
Linear recurrences with constant coefficients. The general form a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k} has solutions determined by the roots of the characteristic polynomial x^k - c_1 x^{k-1} - ... - c_k = 0.
Worked example. Find a closed form for the Fibonacci sequence: F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1.
Characteristic equation: x^2 - x - 1 = 0. Roots: phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2.
General solution: F_n = A phi^n + B psi^n. From F_0 = 0: A + B = 0. From F_1 = 1: A*phi + B*psi = 1. Solving: A = 1/sqrt(5), B = -1/sqrt(5).
Closed form (Binet's formula): F_n = (phi^n - psi^n) / sqrt(5).
Since |psi| < 1, for large n, F_n is approximately phi^n / sqrt(5), and F_n is always the nearest integer to phi^n / sqrt(5).
Generating Functions
A generating function encodes a sequence {a_n} as the coefficients of a formal power series:
A(x) = sum_{n=0}^{infinity} a_n x^n (ordinary generating function) A(x) = sum_{n=0}^{infinity} a_n x^n / n! (exponential generating function)
Why they matter. Algebraic operations on generating functions correspond to operations on sequences: multiplication corresponds to convolution, differentiation to index-shifting, and composition to certain substitution operations. Many sequence identities that are hard to prove combinatorially become routine algebra on generating functions.
Worked example. Find the generating function for the Fibonacci sequence.
From F_n = F_{n-1} + F_{n-2}: multiply by x^n and sum over n >= 2.
sum_{n>=2} F_n x^n = sum_{n>=2} F_{n-1} x^n + sum_{n>=2} F_{n-2} x^n
F(x) - F_0 - F_1 x = x(F(x) - F_0) + x^2 F(x)
F(x) - x = xF(x) + x^2 F(x)
F(x)(1 - x - x^2) = x
F(x) = x / (1 - x - x^2)
Partial fraction decomposition recovers Binet's formula.
Part II — Pattern Detection Methods
Finite Differences
The first difference of a sequence {a_n} is Delta(a_n) = a_{n+1} - a_n. Higher differences are defined recursively.
Key insight. If the k-th differences are constant, the sequence is a polynomial of degree k.
| Sequence type | 1st diff | 2nd diff | 3rd diff | |---|---|---|---| | Linear (an + b) | Constant | Zero | Zero | | Quadratic (an^2 + bn + c) | Linear | Constant | Zero | | Cubic | Quadratic | Linear | Constant |
Worked example. Identify the pattern: 1, 5, 14, 30, 55, 91, ...
First differences: 4, 9, 16, 25, 36 (perfect squares!) Second differences: 5, 7, 9, 11 (arithmetic) Third differences: 2, 2, 2 (constant)
Third differences are constant, so the sequence is a cubic polynomial. The first differences being perfect squares suggests a_n = sum_{k=1}^{n} k^2 = n(n+1)(2n+1)/6.
Verify: a_1 = 1, a_2 = 5, a_3 = 14, a_4 = 30, a_5 = 55, a_6 = 91. Confirmed.
Ratio Analysis
Compute successive ratios a_{n+1}/a_n. Convergence to a constant L suggests geometric growth (a_n is approximately C * L^n). Convergence to 1 from above suggests polynomial growth.
Worked example. For 1, 1, 2, 3, 5, 8, 13, 21, ..., compute ratios: 1, 2, 1.5, 1.667, 1.6, 1.625, 1.615...
The ratios converge to phi = (1 + sqrt(5))/2 approximately 1.618, confirming Fibonacci-like exponential growth at rate phi.
Modular Patterns
Reduce a sequence modulo small numbers to reveal periodic structure.
Worked example. Fibonacci numbers mod 3: 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, ...
The sequence is periodic with period 8. This is the Pisano period pi(3) = 8. Every Fibonacci sequence mod m is periodic (a theorem), and the Pisano periods themselves form a fascinating sequence (OEIS A001175).
Part III — Conjecture Generation Workflow
The process from observation to theorem follows a structured workflow:
Step 1: Gather Data
Compute many examples. For sequence problems, compute at least 10-15 terms. For structural problems (graphs, groups, partitions), enumerate small cases completely.
Step 2: Look for Patterns
Apply the detection methods above: differences, ratios, modular reduction, OEIS lookup. Also look for:
- Symmetry: Is a_n = a_{N-n} for some N?
- Monotonicity: Is the sequence always increasing/decreasing?
- Divisibility: Do certain primes always divide certain terms?
- Recurrence: Can each term be expressed in terms of earlier terms?
Step 3: Formulate a Precise Conjecture
A conjecture must be a precise mathematical statement, not a vague observation. "The sequence seems to grow" is not a conjecture. "a_n = 2^n - 1 for all n >= 1" is a conjecture.
Step 4: Test the Conjecture
Verify the conjecture on data not used in its formation. If the conjecture predicts the next 5-10 terms correctly, confidence increases. If any prediction fails, revise.
Step 5: Attempt a Proof
If the conjecture survives testing, attempt a proof using the techniques from the proof-techniques skill. Common approaches: induction for sequences indexed by N, combinatorial arguments for identity conjectures, generating function methods for recurrence conjectures.
Step 6: Calibrate Confidence
See the cautionary tales section below. Even extensive numerical evidence can be misleading.
Part IV — Classical Integer Sequences
Fibonacci Numbers (A000045)
F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}. Closed form: Binet's formula (above).
Key properties: gcd(F_m, F_n) = F_{gcd(m,n)}. F_n divides F_{mn}. sum_{k=0}^{n} F_k = F_{n+2} - 1.
Appearance: rabbit populations (the original Fibonacci problem, Liber Abaci, 1202), phyllotaxis in plants, tilings of 2xn boards, Zeckendorf representation.
Catalan Numbers (A000108)
C_n = (2n choose n) / (n + 1) = 1, 1, 2, 5, 14, 42, 132, 429, ...
The Catalan numbers count an astonishing variety of combinatorial objects:
- Balanced parentheses strings with n pairs
- Full binary trees with n + 1 leaves
- Triangulations of a convex (n + 2)-gon
- Monotonic lattice paths from (0,0) to (n,n) that stay below the diagonal
- Non-crossing partitions of {1, ..., n}
Generating function: C(x) = (1 - sqrt(1 - 4x)) / (2x).
Recurrence: C_0 = 1, C_{n+1} = sum_{k=0}^{n} C_k * C_{n-k}.
Partition Numbers (A000041)
p(n) = number of ways to write n as a sum of positive integers (order doesn't matter). p(0) = 1, p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, ...
Ramanujan discovered stunning congruences: p(5n + 4) = 0 mod 5, p(7n + 5) = 0 mod 7, p(11n + 6) = 0 mod 11. These congruences, initially discovered by pattern recognition on computed values, were lat