Recurrence Relations

How many binary strings of length nn avoid two consecutive zeros? Counting them directly by brute force becomes hopeless as nn grows. Yet a simple observation about how such a string must end changes everything. It turns the problem into arithmetic on small numbers. This is the central move of enumerative combinatorics. Instead of counting a large structure from scratch, express its count using smaller structures of the same kind. A recurrence relation is the equation that records this relationship. An initial condition anchors it to concrete small cases. Together they ensure the equation determines a unique sequence. Recurrence relations matter for an important reason. A huge fraction of counting problems that arise naturally — tilings, binary strings, ways to climb a staircase, subsets without adjacent elements, sequences of parenthesizations — decompose according to "what happens at the last step" or "what happens at the first step." That decomposition is almost always easier to see and prove correct than a closed formula would be. This is because it uses the Sum and Product Rules on a small, structurally clear case split. It does not require a global combinatorial argument. The big picture is this: a recurrence relation, together with initial conditions, is a finite piece of data. It is a difference equation plus a handful of numbers. Together these pin down an infinite sequence completely. This works in the same way that a differential equation with initial conditions pins down a function. Much of the analytic machinery built later in combinatorics (Solving Linear Recurrences, Ordinary Generating Functions) exists for a precise purpose. It converts this implicit recursive description into an explicit closed-form or asymptotic one. This article gives the precise definition of a recurrence relation and of a sequence satisfying one. It builds intuition through a worked "tiling" picture. It proves the fundamental existence-and-uniqueness theorem. This theorem justifies calling recurrence-plus-initial-conditions a complete description of a sequence. The article then works through two genuinely different examples. One is linear, and one comes from a very different combinatorial family. Together they show the technique's reach. It closes with the historical figure most associated with the paradigmatic example, the Fibonacci recurrence. Finally, it points toward the sequences (Catalan numbers) and tools (generating functions) that recurrences feed into.

Key takeaways
  • A recurrence relation expresses ana_n in terms of earlier terms an−1,an−2,…a_{n-1}, a_{n-2}, \dots; initial conditions supply the starting values.
  • Finding a recurrence usually means finding a bijective case split on the "last piece" of the combinatorial object being counted.
  • A recurrence relation plus enough initial conditions determines the entire sequence uniquely — this is a genuine theorem, proved by induction.
  • The order of a recurrence tells you exactly how many initial conditions are needed; too few leaves the sequence undetermined, too many is redundant but not wrong.
  • Recurrences are computationally exact but not automatically informative about growth rate or closed form — that is the job of later solving techniques.
  • Key idea: Decompose a size-nn combinatorial structure by what its last (or first) piece can be, then count each case with smaller structures.

Where this lives today

Recurrence relations are the backbone of algorithm analysis in computer science: the running time of a divide-and-conquer algorithm such as merge sort is captured by a recurrence like T(n)=2T(n/2)+cnT(n) = 2T(n/2) + cn, and solving such recurrences (via the Master Theorem, itself a descendant of the linear-recurrence machinery) is standard practice in complexity analysis. Dynamic programming, one of the most widely used algorithmic paradigms, is precisely the systematic computation of a sequence (or array) defined by a recurrence relation, evaluated bottom-up from initial conditions exactly as in the existence proof above. In cryptography and pseudorandom number generation, linear feedback shift registers produce bit sequences governed by linear recurrences over finite fields, and the theory of such recurrences (periods, initial states) underlies stream ciphers. In statistics and time series analysis, autoregressive models express each observation as a function of previous observations plus noise — a stochastic analogue of a linear recurrence relation, with initial conditions replaced by a starting distribution. In numerical analysis, recurrence relations generate special functions (Legendre polynomials, Bessel functions, Chebyshev polynomials) far more efficiently than their closed-form definitions, and the initial-value framework here is exactly what guarantees the recursively computed values match the analytically defined functions. In combinatorics itself, recurrences are the natural intermediate step between "a bijective description of a structure" and "an explicit formula or generating function," a bridge fully built in Solving Linear Recurrences, Catalan Numbers, and Ordinary Generating Functions.

Ask the tutor: How do I convert a recurrence relation with initial conditions into a closed-form formula?

DefinitionRecurrence relation and initial conditions

Let (an)n≥n0(a_n)_{n \ge n_0} be a sequence of real (or complex) numbers, indexed by integers n≥n0n \ge n_0 for some fixed n0∈Zn_0 \in \mathbb{Z}. A recurrence relation of order kk for (an)(a_n) is an equation of the form

an=f(n,an−1,an−2,…,an−k),for all n≥n0+k,a_n = f(n, a_{n-1}, a_{n-2}, \dots, a_{n-k}), \qquad \text{for all } n \ge n_0 + k,

where ff is a fixed function of k+1k+1 arguments and k≥1k \ge 1 is a fixed integer (the order). The relation expresses each term, from index n0+kn_0+k onward, in terms of the kk immediately preceding terms (and possibly nn itself).

Initial conditions are prescribed values

an0=c0,  an0+1=c1,  …,  an0+k−1=ck−1a_{n_0} = c_0, \; a_{n_0+1} = c_1, \; \dots, \; a_{n_0+k-1} = c_{k-1}

for the first kk terms of the sequence. A sequence (an)n≥n0(a_n)_{n \ge n_0} satisfies the recurrence relation with these initial conditions if both the initial equalities and the recurrence equation hold for every applicable index. Such a sequence is said to be defined by (or to be a solution of) the recurrence relation and initial conditions. The recurrence relation is called linear if ff has the form

f(n,an−1,…,an−k)=c1(n)an−1+c2(n)an−2+⋯+ck(n)an−k+g(n),f(n, a_{n-1}, \dots, a_{n-k}) = c_1(n) a_{n-1} + c_2(n) a_{n-2} + \cdots + c_k(n) a_{n-k} + g(n),

and linear with constant coefficients if additionally each ci(n)c_i(n) is a constant cic_i not depending on nn; it is homogeneous if furthermore g(n)≡0g(n) \equiv 0.

Intuition

The right mental picture is peeling off the last piece. Suppose you are counting objects of "size nn" — strings of length nn, tilings of a 1×n1 \times n strip, subsets of {1,…,n}\{1, \dots, n\} with some property — and every such object of size nn can be built by taking an object of smaller size and attaching one new piece at the end, in a way that is reversible and covers every case exactly once. Then the count ana_n is literally a sum, over the finitely many ways to attach that last piece, of the counts an−1,an−2,…a_{n-1}, a_{n-2}, \dots of objects of the corresponding smaller sizes. This is nothing more than the Sum and Product Rules applied to a case split on "what is the last piece," but the case split is what a recurrence is. The classic picture is tiling a 1×n1 \times n board with 1×11\times 1 squares and 1×21\times 2 dominoes. A tiling of length nn either ends in a square — remove it, and a tiling of length n−1n-1 remains — or ends in a domino — remove it, and a tiling of length n−2n-2 remains. Every tiling falls into exactly one of these two cases, and every tiling of length n−1n-1 or n−2n-2 extends uniquely to a tiling of length nn by appending the corresponding last piece. Hence an=an−1+an−2a_n = a_{n-1} + a_{n-2}, the Fibonacci recurrence, with a0=1a_0 = 1 (the empty tiling) and a1=1a_1 = 1 (one square).

Figure
Tilings of a length-4 board decomposed by the last piece: 3 tilings end in a square (reducing to length 3), 2 end in a domino (reducing to length 2), giving a4=a3+a2=3+2=5a_4 = a_3+a_2 = 3+2 = 5.
Case split for tilings of length n = 4 ends in a square (last cell = 1×1): tiling of length 3 (a₃ = 3 ways) + final square ends in a domino (last cell = 1×2): tiling of length 2 (a₂ = 2 ways) + final domino a₄ = a₃ + a₂ = 3 + 2 = 5

Notice what makes this rigorous rather than merely suggestive: the two cases are disjoint (a tiling's last piece is either a square or a domino, never both, never neither) and exhaustive (every tiling has a well-defined last piece), and within each case there is a bijection between tilings of length nn ending that way and tilings of length n−1n - 1 (resp. n−2n-2) — obtained by deleting or restoring the last piece. Whenever a combinatorial family admits such a decomposition, a recurrence follows immediately from the Sum Rule.

TheoremExistence and uniqueness of solutions to a recurrence

Let k≥1k \ge 1 be an integer, let n0∈Zn_0 \in \mathbb{Z}, let f:{n≥n0+k}×Rk→Rf : \{n \ge n_0+k\} \times \mathbb{R}^k \to \mathbb{R} be a function, and let c0,…,ck−1∈Rc_0, \dots, c_{k-1} \in \mathbb{R} be given constants. Then there exists exactly one sequence (an)n≥n0(a_n)_{n \ge n_0} such that

an0=c0,an0+1=c1,…,an0+k−1=ck−1,a_{n_0} = c_0, \quad a_{n_0+1} = c_1, \quad \dots, \quad a_{n_0 + k - 1} = c_{k-1},

and

an=f(n,an−1,…,an−k)for all n≥n0+k.a_n = f(n, a_{n-1}, \dots, a_{n-k}) \quad \text{for all } n \ge n_0 + k.
Proof

We prove existence and uniqueness separately, both by strong induction on nn. The technique is induction with a kk-term lookback, i.e. strong induction where the inductive step uses the previous kk values rather than just one.

Existence. We construct a sequence (an)n≥n0(a_n)_{n \ge n_0} satisfying both the initial conditions and the recurrence, by strong induction on n≥n0n \ge n_0. Base case. For n0≤n≤n0+k−1n_0 \le n \le n_0 + k - 1, define an:=cn−n0a_n := c_{n - n_0}. This directly satisfies the required initial conditions by definition. Inductive step. Let n≥n0+kn \ge n_0 + k, and suppose an0,an0+1,…,an−1a_{n_0}, a_{n_0+1}, \dots, a_{n-1} have already been defined (this is the strong inductive hypothesis; note n−1≥n0+k−1≥n0n - 1 \ge n_0 + k - 1 \ge n_0, so at least the base case values exist, and if n−1≥n0+kn - 1 \ge n_0+k then an−1a_{n-1} was itself constructed by this same step at an earlier stage). In particular the kk values an−1,an−2,…,an−ka_{n-1}, a_{n-2}, \dots, a_{n-k} are all defined, since n−k≥n0n - k \ge n_0. Define

an:=f(n,an−1,an−2,…,an−k).a_n := f(n, a_{n-1}, a_{n-2}, \dots, a_{n-k}).

This is a legitimate definition because ff is a genuine function (single-valued) on its domain, and all kk arguments are already-defined real numbers. By strong induction, this process defines ana_n for every integer n≥n0n \ge n_0, and by construction the initial conditions hold and the recurrence equation an=f(n,an−1,…,an−k)a_n = f(n, a_{n-1}, \dots, a_{n-k}) holds for every n≥n0+kn \ge n_0+k. This proves existence.

Uniqueness. Suppose (an)n≥n0(a_n)_{n \ge n_0} and (bn)n≥n0(b_n)_{n \ge n_0} are two sequences, both satisfying the same initial conditions and the same recurrence relation. We show an=bna_n = b_n for all n≥n0n \ge n_0, by strong induction on nn. Base case. For n0≤n≤n0+k−1n_0 \le n \le n_0+k-1, both sequences equal cn−n0c_{n-n_0} by the initial conditions, so an=bna_n = b_n. Inductive step. Let n≥n0+kn \ge n_0 + k and suppose am=bma_m = b_m for every mm with n0≤m≤n−1n_0 \le m \le n - 1 (strong inductive hypothesis). Since n≥n0+kn \ge n_0+k, the recurrence applies to both sequences at index nn:

an=f(n,an−1,…,an−k),bn=f(n,bn−1,…,bn−k).a_n = f(n, a_{n-1}, \dots, a_{n-k}), \qquad b_n = f(n, b_{n-1}, \dots, b_{n-k}).

Each of n−1,…,n−kn-1, \dots, n-k lies between n0n_0 and n−1n-1 inclusive (because n−k≥n0n - k \ge n_0 and n−1≤n−1n - 1 \le n-1), so by the inductive hypothesis an−i=bn−ia_{n-i} = b_{n-i} for i=1,…,ki = 1, \dots, k. Since ff is a single function applied to identical argument tuples (n,an−1,…,an−k)=(n,bn−1,…,bn−k)(n, a_{n-1},\dots,a_{n-k}) = (n, b_{n-1},\dots,b_{n-k}), we get an=f(n,an−1,…,an−k)=f(n,bn−1,…,bn−k)=bna_n = f(n,a_{n-1},\dots,a_{n-k}) = f(n,b_{n-1},\dots,b_{n-k}) = b_n. By strong induction, an=bna_n = b_n for all n≥n0n \ge n_0, i.e. the two sequences are identical. This proves uniqueness. ■\blacksquare

∎
CorollaryOrder determines the exact number of initial conditions needed

For a recurrence relation of order kk as above, exactly kk initial conditions (values of kk consecutive terms starting at an0a_{n_0}) suffice to determine the sequence uniquely, and no proper subset of fewer than kk consecutive starting values does so in general.

Proof

Sufficiency of kk initial conditions is exactly the existence-and-uniqueness theorem above. For the necessity direction: fixing fewer than kk, say only c0,…,ck−2c_0, \dots, c_{k-2} (leaving an0+k−1a_{n_0+k-1} free), one can typically construct two different functions ff-driven completions — concretely, for the order-2 recurrence an=an−1+an−2a_n = a_{n-1}+a_{n-2} with only a0=1a_0 = 1 fixed, both a1=1a_1 = 1 (giving Fibonacci numbers 1,1,2,3,5,…1,1,2,3,5,\dots) and a1=2a_1 = 2 (giving 1,2,3,5,8,…1,2,3,5,8,\dots) yield valid, distinct sequences satisfying the same recurrence and the same partial data. Hence k−1k-1 initial values do not pin down a unique sequence in general. ■\blacksquare

∎

Worked examples

Example 1 — Binary strings with no two consecutive zeros (a linear, order-2 recurrence). Let ana_n be the number of binary strings of length n≥1n \ge 1 (over the alphabet {0,1}\{0,1\}) containing no two consecutive 00's, and set a0=1a_0 = 1 (the empty string vacuously has no such pattern). Finding the recurrence. Fix n≥2n \ge 2 and consider a valid string s=s1s2⋯sns = s_1 s_2 \cdots s_n of length nn. Split on the last symbol sns_n:

  • If sn=1s_n = 1: then s1⋯sn−1s_1 \cdots s_{n-1} is itself an arbitrary valid string of length n−1n-1 (deleting a trailing 11 can never create or destroy a "00" pattern elsewhere), and conversely every valid string of length n−1n-1 extends uniquely by appending a 11. This gives a bijection with valid strings of length n−1n-1: an−1a_{n-1} strings.
  • If sn=0s_n = 0: since two consecutive zeros are forbidden, we must have sn−1=1s_{n-1} = 1 (this forces n≥2n \ge 2). Then s1⋯sn−2s_1 \cdots s_{n-2} is an arbitrary valid string of length n−2n-2, and conversely every valid string of length n−2n-2 extends uniquely to a valid string of length nn by appending "1010". This gives a bijection with valid strings of length n−2n-2: an−2a_{n-2} strings.

These two cases are disjoint (they differ in the value of sns_n) and exhaustive (every string has sn∈{0,1}s_n \in \{0,1\}), so by the Sum Rule,

an=an−1+an−2,n≥2.a_n = a_{n-1} + a_{n-2}, \qquad n \ge 2.

Initial conditions. a0=1a_0 = 1 (empty string). For n=1n=1: both strings "0" and "1" are valid (a single 00 has no consecutive pair), so a1=2a_1 = 2. Computing. Using an=an−1+an−2a_n = a_{n-1}+a_{n-2}:

a0=1, a1=2, a2=3, a3=5, a4=8, a5=13, a6=21, a7=34.a_0=1,\ a_1=2,\ a_2=3,\ a_3=5,\ a_4=8,\ a_5=13,\ a_6=21,\ a_7=34.

So there are exactly 3434 binary strings of length 77 with no two consecutive 00's. As a direct check for a small case: for n=3n=3 the valid strings are 111,110,101,011,010,001,100111, 110, 101, 011, 010, 001, 100 — that is 77 strings out of 88 total, excluding only 000000... but wait, we must also exclude any string containing "00" as a substring, not just equal to it. Let's recheck n=3n=3 exhaustively: all 88 strings are 000,001,010,011,100,101,110,111000,001,010,011,100,101,110,111. Those containing "00" as a substring: 000000 (contains "00" twice), 001001 (contains "00"), 100100 (contains "00"). That excludes 33 strings, leaving 8−3=58 - 3 = 5 valid strings, matching a3=5a_3 = 5 computed from the recurrence — confirming correctness (the illustrative list above was miscounted and the recurrence's value of 55, verified by this direct enumeration, is the correct one). This sequence is exactly the Fibonacci sequence shifted in index — a first hint of how different combinatorial problems can produce the same recurrence, a phenomenon fully explained once one studies Solving Linear Recurrences.

Example 2 — Counting well-formed expressions built from a binary operation (order dependent on all smaller indices, foreshadowing Catalan numbers). Let CnC_n, for n≥0n \ge 0, denote the number of ways to fully parenthesize a product of n+1n+1 symbols x0∗x1∗⋯∗xnx_0 * x_1 * \cdots * x_n using a single binary (non-associative, non-commutative) operation ∗*, where C0:=1C_0 := 1 counts the trivial "product" of a single symbol x0x_0 (no operation needed). Finding the recurrence. For n≥1n \ge 1, any full parenthesization of x0∗x1∗⋯∗xnx_0 * x_1 * \cdots * x_n has, as its outermost operation, exactly one application of ∗* splitting the expression into a left block and a right block:

(x0∗⋯∗xi)∗(xi+1∗⋯∗xn)(x_0 * \cdots * x_{i}) * (x_{i+1} * \cdots * x_n)

for some unique split point ii with 0≤i≤n−10 \le i \le n-1. The left block is a fully parenthesized product of i+1i+1 symbols, and the right block is a fully parenthesized product of n−in - i symbols; these two sub-parenthesizations can be chosen completely independently of each other. This is a case split on ii (disjoint because the outermost operation's position is uniquely recoverable from the parenthesization, exhaustive because every parenthesized expression with n≥1n\ge1 has some outermost operation), combined with independent choices governed by the Product Rule within each case. Hence

Cn=∑i=0n−1Ci Cn−1−i,n≥1,C_n = \sum_{i=0}^{n-1} C_i \, C_{n-1-i}, \qquad n \ge 1,

with initial condition C0=1C_0 = 1. This is not a fixed-order recurrence in the sense of the definition above (each CnC_n depends on all of C0,…,Cn−1C_0, \dots, C_{n-1}, not just a bounded lookback of kk terms) — a useful reminder that the order-kk framework, while central, does not capture every recurrence one meets. Existence and uniqueness of the sequence still hold by the identical strong-induction argument (only the base case and the "ff" become f(C0,…,Cn−1)=∑i=0n−1CiCn−1−if(C_0,\dots,C_{n-1}) = \sum_{i=0}^{n-1}C_i C_{n-1-i}, a function of a variable number of previous terms, and the same induction proof goes through verbatim with kk replaced by "all smaller indices"). Computing. C0=1C_0 = 1.

C1=C0C0=1.C_1 = C_0 C_0 = 1.
C2=C0C1+C1C0=1⋅1+1⋅1=2.C_2 = C_0C_1 + C_1C_0 = 1\cdot1 + 1\cdot1 = 2.
C3=C0C2+C1C1+C2C0=1⋅2+1⋅1+2⋅1=5.C_3 = C_0C_2 + C_1C_1 + C_2C_0 = 1\cdot2 + 1\cdot1 + 2\cdot1 = 5.
C4=C0C3+C1C2+C2C1+C3C0=1⋅5+1⋅2+2⋅1+5⋅1=5+2+2+5=14.C_4 = C_0C_3+C_1C_2+C_2C_1+C_3C_0 = 1\cdot5+1\cdot2+2\cdot1+5\cdot1 = 5+2+2+5=14.

So a product of 55 symbols x0∗x1∗x2∗x3∗x4x_0*x_1*x_2*x_3*x_4 can be fully parenthesized in exactly 1414 ways — for instance ((x0∗x1)∗x2)∗(x3∗x4)((x_0*x_1)*x_2)*(x_3*x_4) is one of them, corresponding to split point i=2i=2 on the outermost level and a further split within the left block. These are the Catalan numbers, whose closed form and generating function are developed under Catalan Numbers.

CounterexampleDropping the base case: the recurrence alone does not determine the sequence

The existence-and-uniqueness theorem requires both the recurrence relation and the full set of kk initial conditions. To see that the recurrence by itself is not enough, consider the order-22 linear recurrence

an=an−1+an−2,n≥2,a_n = a_{n-1} + a_{n-2}, \qquad n \ge 2,

with no initial conditions specified at all. Both of the following sequences satisfy this recurrence for every n≥2n \ge 2:

(an):1,1,2,3,5,8,13,…(the Fibonacci sequence, a0=a1=1)(a_n): \quad 1, 1, 2, 3, 5, 8, 13, \dots \qquad (\text{the Fibonacci sequence, } a_0=a_1=1)
(bn):3,4,7,11,18,29,…(b0=3, b1=4).(b_n): \quad 3, 4, 7, 11, 18, 29, \dots \qquad (b_0 = 3,\, b_1 = 4).

Indeed b2=b1+b0=7b_2 = b_1+b_0 = 7, b3=b2+b1=11b_3 = b_2+b_1=11, and so on, so (bn)(b_n) genuinely satisfies the same recurrence relation. Yet (an)≠(bn)(a_n) \ne (b_n) term by term. Even worse, for any choice of a0,a1∈Ra_0, a_1 \in \mathbb{R}, the resulting sequence satisfies the recurrence, so without initial conditions the "recurrence relation" describes an entire two-parameter family of sequences rather than a single one. This is precisely why the hypothesis "kk initial conditions are given" cannot be dropped from the theorem: existence is unaffected (some sequence, in fact infinitely many, always satisfies a well-posed recurrence), but uniqueness fails completely. Weakening the hypothesis to "at least one initial condition given" also fails: with only a0a_0 fixed, one free parameter a1a_1 remains, still yielding infinitely many solutions. All kk consecutive initial values are needed, matching exactly the order kk of the recurrence.

Scope, edge cases & common traps

SituationWhat to watch for
Order of the recurrenceMust match the number of initial conditions supplied; mismatches break uniqueness (see counterexample)
Case split for "finding" a recurrenceCases must be disjoint and exhaustive, and each case must be a genuine bijection with a smaller instance, not just "roughly the same count"
Variable-lookback recurrences (e.g. Catalan)Do not force every recurrence into the fixed order-kk template; existence/uniqueness still holds via the same induction, adapted
Non-constant coefficients or nonlinear ffThe existence/uniqueness theorem places no linearity assumption on ff — it holds for arbitrary well-defined ff, only later solving techniques require linearity
Off-by-one indexingRecheck whether the recurrence's first valid index is n0+kn_0+k or something else; misindexing silently corrupts the initial conditions needed

The mathematician behind it

Origins · 1 minLeonardo of Pisa (Fibonacci) and how this was discovered
LO
Leonardo of Pisa (Fibonacci)
c. 1170 – c. 1240 · Medieval Italy, Republic of Pisa

Leonardo of Pisa, known as Fibonacci, was a merchant's son who traveled extensively through the Mediterranean world and encountered the Hindu–Arabic numeral system and Arabic mathematical texts during his travels, particularly in Béjaïa (in present-day Algeria). His book Liber Abaci (1202) introduced this numeral system to a European audience alongside a wealth of practical and recreational arithmetic problems. Among these was the now-famous rabbit-breeding problem, whose solution is the sequence satisfying exactly the order-2 recurrence Fn=Fn−1+Fn−2F_n = F_{n-1}+F_{n-2} — the paradigmatic example around which the modern theory of recurrence relations is often first taught, even though Fibonacci himself did not develop a general theory of recurrences.

History
- 1202 — Fibonacci's Liber Abaci poses the rabbit problem, producing the sequence 1,1,2,3,5,8,13,…1,1,2,3,5,8,13,\dots via what is recognizably an order-2 recurrence, though not stated in modern symbolic form.
- 1634 — Albert Girard states the Fibonacci recurrence explicitly in the modern symbolic style, an early instance of recurrence relations written as equations relating ana_n to earlier terms.
- 1730s — Daniel Bernoulli and later Abraham de Moivre develop methods to solve linear recurrences with constant coefficients using characteristic roots, foreshadowing Solving Linear Recurrences.
- 1751 — Leonhard Euler derives a recurrence for the number of triangulations of a polygon, an early appearance of the sequence now called the Catalan numbers.
- 1838 — Eugène Charles Catalan explicitly studies the sequence bearing his name in the context of balanced parenthesizations, cementing the object introduced in Catalan Numbers.
What is the difference between a recurrence relation and a formula?

A formula (closed form) gives ana_n directly as an expression in nn alone, computable in one step without reference to other terms — e.g. an=2na_n = 2^n. A recurrence relation instead expresses ana_n in terms of previous terms of the same sequence, so computing ana_n requires having already computed an−1,…,an−ka_{n-1}, \dots, a_{n-k}. Both can define the same sequence: for instance an=2na_n=2^n satisfies the recurrence an=2an−1a_n = 2a_{n-1} with a0=1a_0=1. Recurrences are often easier to discover from a combinatorial argument, since they only require understanding how a size-nn object relates to smaller ones, while closed forms often require extra algebraic work (see Solving Linear Recurrences) to extract from the recurrence.

How do I find a recurrence relation for a new counting problem?

Look for a natural way to remove or isolate one "piece" of the object being counted — often the last element, last row, last symbol, or outermost structural feature — such that the remaining piece is itself a smaller instance of the same kind of object. Check three things rigorously: the cases arising from different choices of that piece are disjoint, they are exhaustive (cover every object), and each case is in bijection with objects of some smaller size. Then the Sum Rule (across cases) and Product Rule (within a case, if there are independent sub-choices) combine to give the recurrence, exactly as in the tiling and parenthesization examples above.

Does every recurrence relation have order exactly some fixed k?

No. The definition given here covers fixed-order recurrences, where ana_n depends only on the previous kk terms for a fixed kk. Many important combinatorial recurrences, such as the Catalan recurrence Cn=∑i=0n−1CiCn−1−iC_n = \sum_{i=0}^{n-1}C_iC_{n-1-i}, have ana_n depending on all previous terms, with the number of terms involved growing with nn. The existence-and-uniqueness argument still applies with minor rewording (strong induction using all smaller indices rather than a fixed lookback window), but such recurrences fall outside the strict order-kk template.

Why must initial conditions start at consecutive indices from n0n_0?

The uniqueness proof by strong induction needs a solid, gap-free base case: to compute ana_n for n≥n0+kn \ge n_0+k via the recurrence, all of an−1,…,an−ka_{n-1},\dots,a_{n-k} must already be known, and inductively this traces back to needing every one of an0,…,an0+k−1a_{n_0}, \dots, a_{n_0+k-1} pinned down with no gaps. If, say, an0+1a_{n_0+1} were left unspecified while an0a_{n_0} and an0+2a_{n_0+2} were given, the induction could not get started at n=n0+kn = n_0+k, since one of its required arguments would be undetermined, and multiple sequences would again satisfy the data.

Is a linear recurrence with constant coefficients always easier to solve than a general one?

Generally yes, in the sense that a full theory (characteristic equations, closed-form solutions) exists specifically for linear recurrences with constant coefficients, developed under Solving Linear Recurrences. Nonlinear recurrences, or ones with coefficients depending on nn, often have no simple closed form at all, and one falls back on generating functions (Ordinary Generating Functions) or purely numerical/asymptotic analysis. The Catalan recurrence in this article, despite being "only" a sum of products, is already not linear in the constant-coefficient sense (it is a convolution), which is exactly why its closed form requires generating-function techniques rather than the elementary characteristic-root method.

Can a recurrence relation have more than one valid set of initial conditions describing the "same" combinatorial sequence?

No — for a fixed sequence, its values at the first kk indices are simply whatever they are; there is only one correct set of initial conditions once the combinatorial problem and starting index are fixed. What can vary is the presentation: sometimes a problem is naturally indexed starting at n0=0n_0=0 with one small case, sometimes starting at n0=1n_0=1 with a different one, and shifting the index changes which numbers count as "the" initial conditions, but does not change the underlying sequence once translated back to a common indexing.

Before this

Where this leads