Motivation
A counting problem often becomes simpler after removing the final piece of an object. The remaining object is smaller, so the decomposition gives a recurrence. A recurrence is not yet a closed answer: its initial values and range of validity matter. A generating function packages the entire sequence so that shifting an index becomes multiplication by a formal variable.
Definitions
Definition 3.1.1
(Formal series and recurrences)
For a sequence over the real or complex numbers, its ordinary generating function is the formal series . Equality means equality of every coefficient. Products use the finite convolution rule
A homogeneous linear recurrence of order with constant coefficients is for , together with specified .
“Formal” means we do not first choose numerical values of or ask about analytic convergence. Every coefficient of a product involves only finitely many terms. A formal series with nonzero constant coefficient has a unique multiplicative inverse, found recursively by solving coefficients from degree zero upward.
Theorem/Proposition
Theorem 3.1.2
(Initial values determine the recurrence solution)
A recurrence of the displayed form and initial values determine exactly one sequence. Its generating function satisfies
In particular its generating function is rational as a formal series.
Theorem 3.1.3
(Two distinct characteristic roots)
If for and has distinct nonzero roots , then there are unique constants such that for every . They are determined by and .
Proof sketch or proof idea
Proof
(Existence, uniqueness and the numerator polynomial)
Existence of a recurrence solution follows by defining the next term successively. If two solutions agree on the first terms, induction makes them agree on every later term, proving uniqueness. Multiply by the denominator polynomial. For degree the coefficient is ; for it is exactly the coefficient on the right. The denominator has constant coefficient , so it is invertible formally.
Proof
(Construct a combination, then invoke uniqueness)
For the characteristic-root theorem, each sequence and satisfies the recurrence by its defining quadratic equation. The two equations for have nonzero determinant . Their linear combination has the correct initial values, so uniqueness proves it equals the desired sequence. This proof does not guess that all solutions have the displayed form; it constructs one and invokes uniqueness.
Proof X-ray
Where distinct roots are used
The proof has two independent ingredients. First, each geometric sequence solves the recurrence: for ,
and the recurrence is linear, so every combination solves it too. This part never uses . Second, the initial values must be matched: the system , has determinant , and this is the only place where distinctness enters. A nonzero determinant gives exactly one pair for every choice of ; two pairs that both represent the sequence would solve the same nonsingular system at , so they are equal. The argument closes through the first theorem rather than by computing further terms: the combination and the given sequence are two solutions with the same first two values, so they coincide for every .
When roots coincide, the two exponentials are the same sequence, so the argument no longer works. For example the recurrence says the first differences are constant, giving . The extra factor arises from a genuinely different second solution.
Counterexample mode
A repeated root leaves the initial values unmatched
Claim: every solution of a second-order recurrence is a combination of powers of its characteristic roots. For the characteristic polynomial is , whose only root is , and every combination of its powers is the constant . The initial values , would require and at once, which is impossible. Yet the recurrence has the solution ; for instance . The determinant is zero here, which is exactly the hypothesis that failed. Repair: for a repeated nonzero root , so that and , the sequence is a second solution, because . For the initial conditions read and , a system with determinant .
Worked examples
Worked example 3.1.4
(Binary strings with no adjacent ones)
Let count length- binary strings without the block . There is one empty string, so , and . For , strings ending in arise by appending to a permitted length- string. Strings ending in must end in and arise from permitted length- strings. The cases are disjoint and exhaustive, so . Thus and .
Worked example 3.1.5
(A nonhomogeneous recurrence)
For and for , put . Then and , so . Checking gives on both sides. This substitution removes the forcing term; the homogeneous characteristic formula cannot simply ignore that term.
Worked example 3.1.6
(Extracting coefficients after a repeated factor)
The formal geometric series satisfies . Squaring and using convolution gives , because the coefficient counts the pairs of nonnegative integers summing to . Consequently for , and the constant coefficient is .
Formal algebra without convergence assumptions
A formal generating function is a record of coefficients, not initially a numerical function. Infinite notation is legitimate because every requested coefficient of a sum or product is determined by finitely many inputs. For a product, the coefficient at a given degree uses only pairs of degrees adding to it. This is why the convolution formula is well-defined even when no numerical value of the variable would make both original series converge.
The existence of an inverse can be proved by the same finite reasoning. At degree zero, the product equation forces the constant coefficient of the inverse. At degree one it forces the next coefficient using only the coefficient already determined. Each successive degree produces one linear equation with the same nonzero leading scalar. Thus the inverse exists uniquely and no analytic limit has been taken. If the original constant coefficient is zero, the degree-zero product cannot equal one, so no such inverse exists.
This perspective explains the denominators that occur in recurrence problems. Their constant coefficient is one, so division is valid in the formal sense from the beginning. One may later study numerical convergence if an analytic question is asked, but a coefficient-counting argument should not depend on an unproved substitution at a numerical point.
Initial conditions are the boundary terms of index shifts
Multiplying a generating function by the variable shifts its coefficient sequence by one place and inserts zero at the start. A recurrence shift does not automatically insert the actual initial values; they must be accounted for separately. This is the source of the numerator polynomial, and it is why two sequences can satisfy the same recurrence but have different generating functions.
A reliable derivation begins by multiplying the recurrence at its valid indices, summing only over those indices, and writing each truncated series explicitly before simplifying. Every omitted initial term is then visible. Once the pattern is understood, the general formula in the theorem performs this bookkeeping efficiently. If a numerator seems unexpectedly simple, verify its first few coefficients against the specified initial values rather than assuming all boundary terms disappeared.
Here the board-tiling sequence counts coverings by tiles of lengths one and two: it has one empty tiling and one tiling at length one, and removing the final tile gives the same two-term recurrence. The no-adjacent-ones sequence and this board-tiling sequence illustrate the distinction. They satisfy the same second-order recurrence but start with different first terms. Their denominator is therefore the same, while the numerator differs. The recurrence describes the update rule; the numerator records which solution of that update rule was selected. Neither piece alone specifies the counting sequence.
Ordered assemblies and unordered selections
Generating functions reflect the exact structure of objects being counted. Suppose an integer total is made from parts of sizes one and two, with no order attached to the parts. The number of size-two parts determines the object uniquely, and the remaining units are size-one parts. The generating function is the product of a series allowing any number of size-one parts and a series allowing any number of size-two parts. Its denominator is the product of the corresponding two geometric denominators.
At total five, there are three such unordered choices: use zero, one or two parts of size two. This differs from the eight tilings of a board of length five, because a tiling records the order of its tiles. A tile of length two followed by a tile of length one is a different tiling from the reverse order, even though both have the same numbers of each tile type. The mismatch is not a failure of generating functions; it reveals that the models count different objects.
To extract the unordered coefficient directly, choose the number of size-two parts from zero up to half the total, rounded down. Each choice leaves one valid count of size-one parts. Hence the answer is that rounded-down half plus one. The coefficient calculation is a finite convolution, giving another concrete interpretation of the multiplication rule.
A nonlinear recurrence from the first return
Not every useful recurrence is linear. Consider parenthesis strings with equal total numbers of opening and closing parentheses, in which every prefix contains at least as many opening as closing parentheses. The empty string is allowed. A nonempty such string begins with an opening parenthesis. Its matching closing parenthesis, at the first return to balance zero, splits the string uniquely into an inner balanced string and a following balanced string.
If there are a fixed number of pairs in total, choosing the number inside determines how many pairs follow. The two smaller strings are then chosen independently. Summing their product counts over all possible split sizes gives a convolution recurrence, with the empty-string count equal to one. The split is unique because it uses the first return to zero; choosing an arbitrary closing parenthesis would not provide the same unambiguous decomposition.
In generating-function language, the series equals one for the empty case plus the variable times its square for the nonempty case. The variable records the outer matched pair. This equation determines every coefficient recursively: the coefficient at a positive degree depends only on earlier ones. Beginning with one, the counts for zero through three pairs are one, one, two and five. A closed formula would need a further argument; the decomposition already proves the recurrence and its meaning without one.
If counts strings with pairs and , this decomposition states and for , hence .
Concept lensStructural
A product records a split into two objects
The convolution coefficient in a product considers every way to split the total size between the first and second objects. A combinatorial product is justified only when the original object has a unique decomposition into that ordered pair. The same coefficient rule can encode two parenthesis pieces, two independent selections, or an algebraic recurrence, but the interpretation must be supplied in each case.
Closed forms are verified by existence and uniqueness
A proposed formula may be discovered by a clever substitution, a characteristic polynomial or a generating-function manipulation. Verification can be much simpler than discovery. Check the initial values, substitute the proposed expression into the recurrence at every valid index, and invoke uniqueness. This three-part argument proves the formula even when the path that suggested it was informal.
For repeated characteristic roots, the distinct-root theorem's hypothesis has genuinely failed. One must derive another solution or return to the generating function; merely assigning the same root to two constants produces only one exponential sequence. For nonhomogeneous recurrences, a particular solution for the forcing term must be included before the homogeneous uniqueness argument applies. These are different reasons for extending the method, so they should not be merged into one vague exception.
Finally, a recurrence's order is not automatically the minimum possible order for every selected sequence. Special initial values may make one term in a closed form vanish, allowing a lower-order relation. The stated recurrence still determines the sequence correctly. Distinguishing a valid recurrence from a minimal one avoids claiming more than the calculation establishes.
Common mistakes
Common mistake
(Applying a recurrence below its first valid index)
A recurrence valid from cannot be substituted at unless a term such as has been separately defined and justified. For strings with no , setting and applying at would give , while the two strings and give . Keeping the initial polynomial in the generating-function calculation prevents this index error.
Common mistake
(Removing the last symbol without a bijection)
Combinatorial recurrences require a bijective decomposition. Saying “remove the last symbol” is insufficient if the number of allowable extensions depends on the remaining string. In the no- example a permitted string ending in can be extended only by , so is not : already . Separating the endings and makes that dependence explicit.
Common mistake
(Substituting a number into a formal identity)
Formal identities do not automatically justify numerical substitutions outside a series' analytic convergence domain. Read at , the formal identity would assert , which is meaningless as a numerical sum. The identity is a statement about coefficients; a substitution needs a separate convergence argument.
Summary
A decomposition supplies a recurrence and its initial values. Formal generating functions turn shifts into polynomial multiplication, with initial terms appearing in the numerator. Uniqueness then provides a clean way to verify a proposed closed form.
Exercises
Quick check
(Count tilings of a length- board by tiles of lengths one and two. Find the generating function and the count at .)
The empty board has one tiling.
Solution · Answer
Let . For , removing the last length-one or length-two tile gives , with disjoint cases and unique reconstruction. Thus . The values show .
Quick check
(Solve with and , and find its generating function.)
Use first differences or the general generating-function identity.
Solution · Answer
The recurrence gives , so every first difference is . Hence . The generating function is . The numerator also follows directly from .
Quick check
(With , use to compute , and say what the term with index counts.)
Solution · Answer
Taking gives . The term with index counts the strings with four pairs whose first pair, closed at the first return to zero, encloses pairs, followed by a balanced string with the remaining pairs. The four cases are disjoint and cover every string, which is why their products are added.