Solving Recurrences with Generating Functions

How many ways can you tile a 1×n1 \times n strip with squares and dominoes? Can a single algebraic manipulation reveal the exact formula for every nn at once? This question, and thousands like it, are governed by linear recurrences. But guessing-and-checking a closed form is slow and unenlightening. Generating functions replace the sequence (an)n≥0(a_n)_{n \ge 0} by a single formal power series A(x)=∑n≥0anxnA(x) = \sum_{n \ge 0} a_n x^n. This turns the recurrence into an algebraic equation for A(x)A(x). Once A(x)A(x) is known as a rational function, partial fraction decomposition mechanically extracts ana_n. It does so in closed form, term by term, with no cleverness required. This matters because it converts a combinatorial or recursive problem into commutative algebra. It becomes a matter of solving for a function, factoring a polynomial, and expanding geometric series. The same machine handles Fibonacci-type sequences, tiling counts, and convolution identities such as ∑kakbn−k\sum_k a_k b_{n-k}. This works because multiplication of generating functions is convolution of sequences. The technique is uniform and checkable at every step. It scales to recurrences with more terms, non-constant coefficients (with modification), or systems of interacting sequences. The big picture is a three-step pipeline. First, encode the sequence as an ordinary generating function (OGF). Second, use the recurrence to derive a functional equation for A(x)A(x). Solve it algebraically, typically producing a ratio of polynomials. Third, decompose that rational function into partial fractions over simple poles. Read off ana_n as a sum of exponential terms. This reconnects with what Solving Linear Recurrences via characteristic polynomials already told us. The poles of A(x)A(x) are literally the reciprocals of the characteristic roots. This article delivers a complete, self-contained treatment. It includes the formal definition of a generating function as a device for encoding recurrences. It offers a fully proved theorem showing that every linear recurrence with constant coefficients yields a rational generating function. That generating function's partial fraction expansion gives a closed form. The article also provides two fully worked asymmetric examples. It includes a counterexample showing why linearity/constant-coefficients cannot be dropped naively. Finally, it looks at where this machinery resurfaces — most gently, in the generating function for the Catalan Numbers.

Key takeaways
  • A sequence (an)(a_n) satisfying a linear recurrence with constant coefficients has an OGF A(x)=∑anxnA(x)=\sum a_n x^n that is a rational function P(x)/Q(x)P(x)/Q(x).
  • The denominator Q(x)Q(x) is built directly from the recurrence's characteristic polynomial (reversed and shifted).
  • Partial fraction decomposition of A(x)A(x) writes it as a sum of simple terms c1−rx\dfrac{c}{1-rx}, each of which expands to c rnxnc\,r^n x^n.
  • Multiplying generating functions corresponds to convolving sequences: (∑aixi)(∑bjxj)=∑n(∑kakbn−k)xn\left(\sum a_ix^i\right)\left(\sum b_jx^j\right) = \sum_n\left(\sum_k a_kb_{n-k}\right)x^n.
  • Initial conditions determine the numerator P(x)P(x) and hence the constants in the partial fraction expansion, giving a fully explicit closed form.
  • Key idea: encode the whole sequence as one function, let algebra (rational function arithmetic + partial fractions) do the recursion-solving for you.

Where this lives today

Generating functions solved via partial fractions appear throughout computer science in the analysis of algorithms, where recurrences for running time (e.g. divide-and-conquer counts, recursive data structure sizes) are converted to rational or algebraic functions whose asymptotics come directly from the dominant pole. In combinatorics on words and lattice paths, OGFs built from convolution encode concatenation of independent structures, foreshadowing the Catalan Numbers, whose OGF C(x)=1−1−4x2xC(x) = \frac{1-\sqrt{1-4x}}{2x} satisfies the quadratic functional equation C(x)=1+xC(x)2C(x) = 1 + xC(x)^2 arising from exactly this convolution principle applied to balanced-parenthesis decompositions. In electrical engineering and signal processing, the same rational-function machinery appears as the zz-transform of a linear-time-invariant (LTI) system, with poles of the transfer function playing the identical role as the poles of A(x)A(x) here. In cryptography, linear feedback shift registers (LFSRs) used in stream ciphers are literally linear recurrences over finite fields, and their period and output structure are analyzed via the rational generating function P(x)/Q(x)P(x)/Q(x) over F2\mathbb{F}_2 or other finite fields. In statistics and probability, probability generating functions of sums of independent random variables convolve exactly as in the definition above, linking this algebraic technique to computing distributions of sums.

Ask the tutor: How does this same convolution technique derive the quadratic functional equation for the Catalan generating function?

DefinitionOrdinary generating function of a recurrence, and its rational form

Let (an)n≥0(a_n)_{n\ge 0} be a sequence of real (or complex) numbers satisfying a linear recurrence with constant coefficients of order k≥1k \ge 1:

an=c1an−1+c2an−2+⋯+ckan−k,n≥k,a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}, \qquad n \ge k,

where c1,…,ckc_1,\dots,c_k are fixed constants with ck≠0c_k \ne 0, together with initial values a0,a1,…,ak−1a_0, a_1, \dots, a_{k-1}. The ordinary generating function (OGF) of (an)(a_n) is the formal power series

A(x)=∑n=0∞anxn.A(x) = \sum_{n=0}^{\infty} a_n x^n .

Two power series are added and multiplied by the usual formal rules; in particular, multiplication is convolution:

(∑iaixi)(∑jbjxj)=∑n≥0(∑k=0nakbn−k)xn.\left(\sum_i a_i x^i\right)\left(\sum_j b_j x^j\right) = \sum_{n\ge 0}\left(\sum_{k=0}^n a_k b_{n-k}\right) x^n .

A rational form for A(x)A(x) is an identity A(x)=P(x)/Q(x)A(x) = P(x)/Q(x) with P,QP, Q polynomials, Q(0)≠0Q(0)\ne 0, valid as formal power series (equivalently, as an identity of analytic functions on a neighborhood of x=0x=0 where the series converges). A partial fraction decomposition of A(x)A(x), when Q(x)=∏i=1m(1−rix)eiQ(x) = \prod_{i=1}^m (1 - r_i x)^{e_i} with the rir_i distinct nonzero constants, is a representation

A(x)=∑i=1m∑j=1eici,j(1−rix)jA(x) = \sum_{i=1}^{m} \sum_{j=1}^{e_i} \frac{c_{i,j}}{(1 - r_i x)^j}

for constants ci,jc_{i,j} (plus a polynomial part if deg⁡P≥deg⁡Q\deg P \ge \deg Q).

Intuition

Think of A(x)=∑anxnA(x) = \sum a_n x^n as a clothesline on which the entire sequence hangs, one value per hook indexed by the power of xx. The recurrence an=c1an−1+⋯+ckan−ka_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} is a local rule relating nearby hooks, valid for all n≥kn \ge k simultaneously. Multiplying A(x)A(x) by xx shifts every value one hook to the right: the coefficient of xnx^n in xA(x)xA(x) is an−1a_{n-1}. So the entire infinite family of recurrence equations (one for each n≥kn \ge k) can be encoded in a single algebraic equation among A(x),xA(x),x2A(x),…A(x), xA(x), x^2A(x), \dots Once you write A(x)(1−c1x−c2x2−⋯−ckxk)=(polynomial from initial data)A(x)(1 - c_1 x - c_2 x^2 - \cdots - c_k x^k) = (\text{polynomial from initial data}), the sequence's asymptotic behavior is entirely visible in the roots of the denominator. If Q(x)=∏(1−rix)Q(x) = \prod (1 - r_i x), each factor 11−rix=∑nrinxn\frac{1}{1-r_ix} = \sum_n r_i^n x^n is a pure geometric sequence, and the full solution is a linear combination of these — exactly the same exponential building blocks that appear in the characteristic-root method, now derived by pure algebra rather than by an ansatz. The picture below shows the correspondence between the recurrence's characteristic roots (as reciprocals of poles of A(x)A(x)) and the exponential pieces of ana_n.

Figure
The poles of A(x)A(x) at x=1/rix = 1/r_i correspond to exponential terms rinr_i^n in ana_n
x-axis x = 1/2 pole from (1 − 2x) x = 1/3 pole from (1 − 3x) a_n = c₁·2ⁿ + c₂·3ⁿ term from x=1/2: contributes 2ⁿ term from x=1/3: contributes 3ⁿ

The central theorem

TheoremRational OGF and closed form for linear recurrences

Let (an)n≥0(a_n)_{n\ge0} satisfy, for all n≥kn \ge k,

an=c1an−1+c2an−2+⋯+ckan−k,a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k},

with constants c1,…,ck∈Cc_1, \dots, c_k \in \mathbb{C}, ck≠0c_k \ne 0, and given initial values a0,…,ak−1a_0,\dots,a_{k-1}. Let

Q(x)=1−c1x−c2x2−⋯−ckxk.Q(x) = 1 - c_1 x - c_2 x^2 - \cdots - c_k x^k .

Then:

(1) The OGF A(x)=∑n≥0anxnA(x) = \sum_{n\ge0} a_n x^n satisfies

A(x)=P(x)Q(x)A(x) = \frac{P(x)}{Q(x)}

for some polynomial P(x)P(x) with deg⁡P≤k−1\deg P \le k-1, determined explicitly by a0,…,ak−1a_0,\dots,a_{k-1} and c1,…,ckc_1,\dots,c_k.

(2) If the characteristic polynomial xk−c1xk−1−⋯−ckx^k - c_1x^{k-1} - \cdots - c_k has distinct roots r1,…,rk∈C∖{0}r_1,\dots,r_k \in \mathbb{C}\setminus\{0\} (equivalently Q(x)=∏i=1k(1−rix)Q(x) = \prod_{i=1}^k (1 - r_ix) with the rir_i distinct), then A(x)A(x) has a partial fraction decomposition

A(x)=∑i=1kαi1−rixA(x) = \sum_{i=1}^k \frac{\alpha_i}{1 - r_i x}

for unique constants α1,…,αk∈C\alpha_1,\dots,\alpha_k \in \mathbb{C}, and consequently

an=∑i=1kαi ri nfor all n≥0.a_n = \sum_{i=1}^{k} \alpha_i\, r_i^{\,n} \qquad \text{for all } n \ge 0.
Proof

Proof technique: formal power series manipulation to derive the functional equation (part 1), followed by algebraic partial-fraction algebra and matching of power series coefficients (part 2).

Part (1): rationality. Consider the formal product

Q(x)A(x)=(1−c1x−c2x2−⋯−ckxk)(∑n≥0anxn).Q(x) A(x) = \left(1 - c_1x - c_2x^2 - \cdots - c_kx^k\right)\left(\sum_{n\ge 0} a_n x^n\right).

By the convolution rule for multiplying power series, the coefficient of xnx^n in Q(x)A(x)Q(x)A(x) is

[xn] Q(x)A(x)=an−c1an−1−c2an−2−⋯−ckan−k,[x^n]\, Q(x)A(x) = a_n - c_1 a_{n-1} - c_2 a_{n-2} - \cdots - c_k a_{n-k},

where any ama_m with m<0m < 0 is understood as 00 (since Q(x)Q(x) has no terms of degree >k> k and A(x)A(x) starts at x0x^0; more precisely for n<kn < k some of the cjan−jc_j a_{n-j} terms simply do not occur because xjx^j has degree >n> n). For n≥kn \ge k, the recurrence gives exactly

an−c1an−1−⋯−ckan−k=0,a_n - c_1a_{n-1} - \cdots - c_ka_{n-k} = 0,

so the coefficient of xnx^n in Q(x)A(x)Q(x)A(x) vanishes for every n≥kn \ge k. Hence Q(x)A(x)Q(x)A(x) is a polynomial of degree at most k−1k - 1; call it P(x)P(x). Concretely, for 0≤n≤k−10 \le n \le k-1,

[xn]P(x)=an−∑j=1ncjan−j,[x^n]P(x) = a_n - \sum_{j=1}^{n} c_j a_{n-j},

(the sum only running over j≤nj \le n, since cjan−jc_j a_{n-j} requires n−j≥0n - j \ge 0), which is an explicit polynomial expression in the initial values a0,…,ak−1a_0,\dots,a_{k-1} and coefficients c1,…,ckc_1,\dots,c_k. Since Q(0)=1≠0Q(0) = 1 \ne 0, Q(x)Q(x) is invertible as a formal power series (its reciprocal 1/Q(x)1/Q(x) exists and is itself a formal power series, by the standard fact that a formal power series with nonzero constant term is a unit in the ring of formal power series). Therefore

A(x)=P(x)Q(x)A(x) = \frac{P(x)}{Q(x)}

holds as an identity of formal power series, with deg⁡P≤k−1\deg P \le k-1. This proves (1).

Part (2): partial fractions and closed form. Assume now the characteristic polynomial χ(t)=tk−c1tk−1−⋯−ck\chi(t) = t^k - c_1t^{k-1} - \cdots - c_k has kk distinct roots r1,…,rkr_1,\dots,r_k, all nonzero (nonzero because ck≠0c_k \ne 0 forces χ(0)=−ck≠0\chi(0) = -c_k \ne 0, so t=0t=0 is not a root). We first verify the factorization of QQ. Since χ(t)=∏i=1k(t−ri)\chi(t) = \prod_{i=1}^k (t - r_i), substituting t=1/xt = 1/x and multiplying by xkx^k gives

xkχ(1/x)=xk(1xk−c1xk−1−⋯−ck)=1−c1x−c2x2−⋯−ckxk=Q(x).x^k \chi(1/x) = x^k\left(\frac{1}{x^k} - \frac{c_1}{x^{k-1}} - \cdots - c_k\right) = 1 - c_1x - c_2x^2 - \cdots - c_kx^k = Q(x).

On the other hand,

xkχ(1/x)=xk∏i=1k(1x−ri)=∏i=1k(1−rix),x^k \chi(1/x) = x^k \prod_{i=1}^k\left(\frac1x - r_i\right) = \prod_{i=1}^k \big(1 - r_i x\big),

where we used x(1x−ri)=1−rixx\left(\frac1x - r_i\right) = 1 - r_ix and distributed one factor of xx into each of the kk factors of the product. Hence

Q(x)=∏i=1k(1−rix),Q(x) = \prod_{i=1}^k (1 - r_i x),

with the rir_i distinct, so the factors (1−rix)(1-r_ix) are pairwise coprime as polynomials (distinct linear factors, since ri≠rjr_i \ne r_j implies (1−rix)(1-r_ix) and (1−rjx)(1-r_jx) have different roots 1/ri≠1/rj1/r_i \ne 1/r_j). By the partial fraction decomposition theorem for rational functions over a field (here C\mathbb{C}), since deg⁡P≤k−1<k=deg⁡Q\deg P \le k - 1 < k = \deg Q and QQ factors into distinct linear factors (1−rix)(1-r_ix), there exist unique constants α1,…,αk∈C\alpha_1,\dots,\alpha_k \in \mathbb{C} with

P(x)Q(x)=∑i=1kαi1−rix.\frac{P(x)}{Q(x)} = \sum_{i=1}^k \frac{\alpha_i}{1 - r_ix}.

(This is the standard cover-up/coprimality argument: since the (1−rix)(1-r_ix) are pairwise coprime, the Chinese Remainder Theorem for the polynomial ring C[x]\mathbb{C}[x] localized appropriately — or directly, clearing denominators and solving the resulting linear system, whose coefficient matrix is a Vandermonde-type matrix and hence invertible because the rir_i are distinct — produces a unique solution (α1,…,αk)(\alpha_1,\dots,\alpha_k).) Explicitly, each αi\alpha_i can be computed by the cover-up rule:

αi=P(x)(1−rix)Q(x)∣x=1/ri=P(1/ri)∏j≠i(1−rj/ri).\alpha_i = \left.\frac{P(x)(1-r_ix)}{Q(x)}\right|_{x = 1/r_i} = \frac{P(1/r_i)}{\prod_{j \ne i}(1 - r_j/r_i)}.

Finally, for each ii, the geometric series expansion

11−rix=∑n≥0rinxn\frac{1}{1 - r_ix} = \sum_{n\ge 0} r_i^n x^n

holds as an identity of formal power series (direct verification: multiplying the right side by (1−rix)(1-r_ix) telescopes to 11, matching coefficients term by term). Substituting,

A(x)=∑i=1kαi∑n≥0rinxn=∑n≥0(∑i=1kαirin)xn.A(x) = \sum_{i=1}^k \alpha_i \sum_{n\ge0} r_i^n x^n = \sum_{n \ge 0}\left(\sum_{i=1}^k \alpha_i r_i^n\right) x^n.

Since A(x)=∑n≥0anxnA(x) = \sum_{n\ge0} a_n x^n by definition, and two formal power series are equal iff all corresponding coefficients agree, we match coefficients of xnx^n on both sides to conclude

an=∑i=1kαirinfor every n≥0.a_n = \sum_{i=1}^k \alpha_i r_i^n \qquad \text{for every } n \ge 0.

This is exactly the claimed closed form, completing the proof of (2). ■\blacksquare

∎

Worked examples

Example 1 (asymmetric second-order recurrence). Solve an=5an−1−6an−2a_n = 5a_{n-1} - 6a_{n-2} for n≥2n \ge 2, with a0=2a_0 = 2, a1=5a_1 = 5. Step 1 — set up the functional equation. Let A(x)=∑n≥0anxnA(x) = \sum_{n\ge0} a_nx^n. Here k=2k=2, c1=5c_1 = 5, c2=−6c_2 = -6, so Q(x)=1−5x+6x2Q(x) = 1 - 5x + 6x^2. Multiply:

Q(x)A(x)=∑nanxn−5x∑nanxn+6x2∑nanxn.Q(x)A(x) = \sum_n a_nx^n - 5x\sum_n a_nx^n + 6x^2\sum_n a_nx^n.

Coefficient of xnx^n for n≥2n \ge 2: an−5an−1+6an−2=0a_n - 5a_{n-1} + 6a_{n-2} = 0 by the recurrence, so all these vanish. Coefficient of x0x^0: a0=2a_0 = 2. Coefficient of x1x^1: a1−5a0=5−10=−5a_1 - 5a_0 = 5 - 10 = -5. So

Q(x)A(x)=2−5x,A(x)=2−5x1−5x+6x2.Q(x)A(x) = 2 - 5x, \qquad A(x) = \frac{2-5x}{1-5x+6x^2}.

Step 2 — factor the denominator. 1−5x+6x2=(1−2x)(1−3x)1 - 5x + 6x^2 = (1-2x)(1-3x) (check: expand (1−2x)(1−3x)=1−3x−2x+6x2=1−5x+6x2(1-2x)(1-3x) = 1 -3x-2x+6x^2 = 1-5x+6x^2 ✓). The characteristic roots are r1=2,r2=3r_1 = 2, r_2 = 3 (reciprocals of x=1/2,1/3x=1/2, 1/3). Step 3 — partial fractions. Write

2−5x(1−2x)(1−3x)=α11−2x+α21−3x.\frac{2-5x}{(1-2x)(1-3x)} = \frac{\alpha_1}{1-2x} + \frac{\alpha_2}{1-3x}.

Clear denominators: 2−5x=α1(1−3x)+α2(1−2x)2 - 5x = \alpha_1(1-3x) + \alpha_2(1-2x). Using cover-up: set x=1/2x = 1/2: 2−5/2=α1(1−3/2)2 - 5/2 = \alpha_1(1 - 3/2), i.e. −1/2=α1(−1/2)-1/2 = \alpha_1(-1/2), so α1=1\alpha_1 = 1. Set x=1/3x = 1/3: 2−5/3=α2(1−2/3)2 - 5/3 = \alpha_2(1-2/3), i.e. 1/3=α2(1/3)1/3 = \alpha_2(1/3), so α2=1\alpha_2 = 1. Step 4 — expand.

A(x)=11−2x+11−3x=∑n(2n+3n)xn  ⟹  an=2n+3n.A(x) = \frac{1}{1-2x} + \frac{1}{1-3x} = \sum_n (2^n + 3^n)x^n \implies a_n = 2^n + 3^n.

Check: a0=1+1=2a_0 = 1+1=2 ✓, a1=2+3=5a_1 = 2+3=5 ✓, a2=4+9=13a_2 = 4+9=13, and directly a2=5(5)−6(2)=25−12=13a_2 = 5(5) - 6(2) = 25-12=13 ✓. a3=8+27=35a_3 = 8+27=35, and directly 5(13)−6(5)=65−30=355(13)-6(5)=65-30=35 ✓.

Example 2 (convolution: OGF of a sum, tiling with a twist). Let tnt_n count tilings of a 1×n1\times n strip by squares (length 1) and dominoes (length 2), with t0=1t_0 = 1 (empty tiling), so tn=tn−1+tn−2t_n = t_{n-1}+t_{n-2} for n≥2n\ge2, t1=1t_1=1 — the Fibonacci recurrence, T(x)=∑tnxn=11−x−x2T(x) = \sum t_nx^n = \dfrac{1}{1-x-x^2} (a standard fact we now use, not reprove, since Q(x)A(x)=1Q(x)A(x) = 1 here as the reader can verify by the same method as Example 1). Now define bn=∑k=0ntktn−kb_n = \sum_{k=0}^n t_k t_{n-k}, the number of ways to choose an ordered pair of tilings of strips of lengths summing to nn — e.g. this counts tilings of a length-nn strip that has been pre-marked with a "cut point," where the left piece is tiled independently from the right. By the convolution rule,

B(x)=∑nbnxn=T(x)2=1(1−x−x2)2.B(x) = \sum_n b_n x^n = T(x)^2 = \frac{1}{(1-x-x^2)^2}.

We extract bnb_n using partial fractions with a repeated factor structure, illustrating the (1−rix)j(1-r_ix)^j terms from the definition. Step 1 — factor 1−x−x21-x-x^2. The roots of t2−t−1=0t^2 - t - 1=0 are φ=1+52\varphi = \frac{1+\sqrt5}{2}, φ^=1−52\hat\varphi = \frac{1-\sqrt5}{2} (so 1−x−x2=(1−φx)(1−φ^x)1-x-x^2 = (1-\varphi x)(1-\hat\varphi x), since these are reciprocals of the roots, exactly as in the theorem). Numerically φ≈1.618\varphi \approx 1.618, φ^≈−0.618\hat\varphi \approx -0.618. Step 2 — decompose B(x)B(x). Since (1−x−x2)2=(1−φx)2(1−φ^x)2(1-x-x^2)^2 = (1-\varphi x)^2(1-\hat\varphi x)^2, write

B(x)=A11−φx+A2(1−φx)2+B11−φ^x+B2(1−φ^x)2.B(x) = \frac{A_1}{1-\varphi x} + \frac{A_2}{(1-\varphi x)^2} + \frac{B_1}{1-\hat\varphi x} + \frac{B_2}{(1-\hat\varphi x)^2}.

Using 1(1−rx)2=∑n(n+1)rnxn\frac{1}{(1-rx)^2} = \sum_n (n+1)r^nx^n (differentiate the geometric series or convolve 11−rx\frac1{1-rx} with itself), the coefficient of xnx^n becomes

bn=A1φn+A2(n+1)φn+B1φ^n+B2(n+1)φ^n.b_n = A_1\varphi^n + A_2(n+1)\varphi^n + B_1\hat\varphi^n + B_2(n+1)\hat\varphi^n.

Rather than solve the full linear system symbolically (routine but tedious algebra using φ+φ^=1\varphi + \hat\varphi = 1, φφ^=−1\varphi\hat\varphi=-1, φ−φ^=5\varphi - \hat\varphi = \sqrt5), we verify the structural point numerically. Compute small tiling numbers directly: t0=1,t1=1,t2=2,t3=3,t4=5t_0=1,t_1=1,t_2=2,t_3=3,t_4=5 (Fibonacci). Then

b0=t02=1,b1=2t0t1=2,b2=2t0t2+t12=4+1=5,b3=2t0t3+2t1t2=6+4=10.b_0 = t_0^2 = 1,\quad b_1 = 2t_0t_1 = 2,\quad b_2 = 2t_0t_2+t_1^2 = 4+1=5,\quad b_3 = 2t_0t_3+2t_1t_2 = 6+4=10.

This sequence (1,2,5,10,… )(1,2,5,10,\dots) is exactly the convolution square of Fibonacci, matching bn=∑k=0nFk+1Fn−k+1b_n = \sum_{k=0}^n F_{k+1}F_{n-k+1} up to indexing — the same object that appears when counting tilings of a strip with a distinguished internal cut, confirming that convolution of OGFs correctly encodes "split the structure into an ordered pair of independent pieces," exactly as claimed by the definition's convolution rule.

Why the constant-coefficient hypothesis is needed

Counterexampledropping "constant coefficients" breaks rationality

The theorem requires the cic_i to be constants, independent of nn. Consider instead the recurrence with a coefficient depending on nn:

an=n an−1,a0=1,a_n = n\, a_{n-1}, \qquad a_0 = 1,

so an=n!a_n = n!. Its OGF is

A(x)=∑n≥0n! xn=1+x+2x2+6x3+24x4+⋯ .A(x) = \sum_{n\ge0} n!\, x^n = 1 + x + 2x^2 + 6x^3 + 24x^4 + \cdots.

This power series has radius of convergence 00 (since n!→∞n! \to \infty faster than any exponential, the ratio test gives ∣an+1x/an∣=(n+1)∣x∣→∞|a_{n+1}x/a_n| = (n+1)|x| \to \infty for any x≠0x \ne 0), so it does not even converge to an analytic function near x=0x=0 — in sharp contrast to the constant-coefficient case, where A(x)=P(x)/Q(x)A(x) = P(x)/Q(x) is a rational function, automatically analytic wherever Q≠0Q \ne 0, in particular on a disk around the origin. Algebraically, the derivation in the proof used Q(x)A(x)=P(x)Q(x)A(x) = P(x) where Q(x)=1−c1x−⋯−ckxkQ(x) = 1 - c_1x - \cdots - c_kx^k is a fixed polynomial multiplying A(x)A(x), which relied on each recurrence coefficient cic_i being the same for every nn; multiplying by xix^i shifts the whole series uniformly, matching ana_n against cian−ic_ia_{n-i} for every nn at once. When the coefficient is nn itself, no fixed polynomial Q(x)Q(x) can produce Q(x)A(x)=P(x)Q(x)A(x) = P(x), because the relation an=nan−1a_n = n a_{n-1} is not expressible as "the coefficient of xnx^n in a fixed polynomial times A(x)A(x)" — that operation always produces a constant-coefficient combination of the an−ia_{n-i}, never an nn-dependent one. (Formally: n!n! is not a solution of any linear recurrence with constant coefficients, since such solutions are always of the form ∑αirin\sum \alpha_i r_i^n times polynomials in nn for repeated roots — but here growth is faster than any fixed exponential rate, so no finite list of rir_i can match it.) This example shows why the rationality conclusion genuinely needs constant coefficients: variable-coefficient recurrences typically demand exponential generating functions or other techniques entirely, not the rational-OGF machinery developed here.

Scope, edge cases & common traps

SituationWhat happens
Distinct roots rir_iPartial fractions have only simple poles αi1−rix\frac{\alpha_i}{1-r_ix}; an=∑αirina_n = \sum \alpha_i r_i^n.
Repeated root rir_i with multiplicity eie_iNeed terms ci,j(1−rix)j\frac{c_{i,j}}{(1-r_ix)^j} for j=1,…,eij=1,\dots,e_i; contributes rinr_i^n times a degree-(ei−1)(e_i-1) polynomial in nn to ana_n.
Complex conjugate rootsOccur in conjugate pairs when ci∈Rc_i \in \mathbb{R}; the closed form is still valid over C\mathbb{C} but can be rewritten with cos⁡,sin⁡\cos,\sin to show an∈Ra_n\in\mathbb{R}.
deg⁡P≥deg⁡Q\deg P \ge \deg QPerform polynomial division first; the quotient contributes finitely many extra terms only at small nn, absent from the tail behavior.
Non-constant coefficientsTheorem does not apply; rationality of A(x)A(x) can fail entirely (see counterexample).
Convolution used to combine two known OGFsValid whenever both OGFs are genuine formal power series; no additional hypothesis is needed beyond correct indexing of the convolution sum.

The mathematician behind it

Origins · 1 minLeonhard Euler and how this was discovered
LE
Leonhard Euler
1707–1783 · 18th-century analysis and combinatorics, University of Basel / St. Petersburg / Berlin Academies

Euler pioneered the systematic use of formal power series to encode combinatorial sequences, most famously in his study of partitions, where he manipulated infinite products and series as purely formal algebraic objects, decades before a rigorous theory of convergence existed. This willingness to treat generating functions as legitimate algebraic entities — multiplying, inverting, and expanding them freely — is the direct ancestor of the technique presented here: encode a sequence as a power series, manipulate the series algebraically, and read off the answer from the resulting closed form.

History
- 1748 — Euler's Introductio in Analysin Infinitorum develops formal power series methods and generating-function-style arguments for partitions and related sequences.
- 1202 — Fibonacci's Liber Abaci introduces the rabbit-population recurrence later solved in closed form by generating function methods.
- 1730s – 1750s — Euler and de Moivre develop early forms of the characteristic-root approach to linear recurrences, later unified with the OGF viewpoint.
- 1840s — Partial fraction decomposition is formalized within the developing theory of rational functions and complex analysis, becoming a standard algebraic tool.
- 1960s – 1970s — Generating functions become a central organizing framework in enumerative combinatorics, systematized in texts by Riordan, and later Stanley and Wilf.
Why must Q(0)≠0Q(0) \ne 0 in the rational form A(x)=P(x)/Q(x)A(x) = P(x)/Q(x)?

The condition Q(0)≠0Q(0)\ne 0 ensures Q(x)Q(x) is invertible as a formal power series, since a formal power series is a unit in C[[x]]\mathbb{C}[[x]] exactly when its constant term is nonzero (you can build the inverse coefficient by coefficient, always dividing by that nonzero constant term). In our setting Q(x)=1−c1x−⋯−ckxkQ(x) = 1 - c_1x - \cdots - c_kx^k automatically has Q(0)=1≠0Q(0) = 1 \ne 0, so this is never actually an extra hypothesis to check — it is built into how the recurrence is encoded. If Q(0)Q(0) were 00, the division P(x)/Q(x)P(x)/Q(x) would not correspond to a well-defined formal power series, and the entire coefficient-extraction argument would break down.

What happens if the characteristic polynomial has a repeated root?

The proof of part (2) assumed distinct roots so that Q(x)Q(x) factors into distinct linear terms, allowing the simplest partial fraction form. If a root rir_i has multiplicity ei>1e_i > 1, the partial fraction expansion instead needs terms ci,11−rix+⋯+ci,ei(1−rix)ei\frac{c_{i,1}}{1-r_ix} + \cdots + \frac{c_{i,e_i}}{(1-r_ix)^{e_i}}. Using 1(1−rx)j=∑n(n+j−1j−1)rnxn\frac{1}{(1-rx)^{j}} = \sum_n \binom{n+j-1}{j-1} r^n x^n, each such term contributes rinr_i^n times a polynomial in nn of degree ei−1e_i - 1 to ana_n. This exactly matches the repeated-root case of the characteristic-root method from Solving Linear Recurrences.

How is this related to solving recurrences via the characteristic polynomial directly?

They are the same theorem viewed from two directions. The characteristic-root method guesses an=rna_n = r^n as an ansatz and finds that rr must be a root of tk−c1tk−1−⋯−ckt^k - c_1t^{k-1}-\cdots-c_k. The generating function method derives, without any ansatz, that A(x)A(x) is rational with denominator Q(x)=xkχ(1/x)Q(x) = x^k\chi(1/x) where χ\chi is exactly that characteristic polynomial. Partial fractions then automatically produce the same exponential terms rinr_i^n, so the generating function approach can be seen as a proof, from first principles, of why the ansatz method works.

Can this method handle inhomogeneous recurrences, like an=2an−1+1a_n = 2a_{n-1} + 1?

Yes, with a small extension: write F(x)=∑fnxnF(x) = \sum f_n x^n for the forcing sequence (here fn=1f_n=1 for all nn, so F(x)=1/(1−x)F(x) = 1/(1-x)), and the same coefficient-matching argument gives Q(x)A(x)=P(x)+xkF(x)⋅(correction from where forcing enters)Q(x)A(x) = P(x) + x^{k}F(x)\cdot(\text{correction from where forcing enters}), more simply derived case by case exactly as in the proof, just tracking the extra additive term. The resulting A(x)A(x) is still rational, now with possibly an extra pole coming from F(x)F(x)'s own denominator (e.g. an extra factor (1−x)(1-x) from the constant forcing term), and partial fractions proceed identically.

Does the method require the initial conditions to match the order of the recurrence exactly?

Yes — the theorem as stated needs exactly kk initial values a0,…,ak−1a_0,\dots,a_{k-1} to pin down the numerator P(x)P(x), whose degree is at most k−1k-1, matching the kk unknown coefficients of PP. Too few initial conditions leave P(x)P(x) underdetermined (infinitely many sequences would share the same Q(x)Q(x)); the derivation in part (1) explicitly computes each coefficient of P(x)P(x) from a0,…,ak−1a_0,\dots,a_{k-1}, so exactly kk conditions are needed and are always sufficient.

Why does convolution appear at all when just solving a single recurrence?

Convolution is silently used every time we multiply A(x)A(x) by Q(x)Q(x) or by xix^i: the coefficient extraction [xn] Q(x)A(x)=an−c1an−1−⋯[x^n]\,Q(x)A(x) = a_n - c_1a_{n-1}-\cdots is literally the convolution formula applied to the two series Q(x)Q(x) and A(x)A(x). It becomes explicitly visible, rather than implicit, when combining two different generating functions, as in Example 2, where B(x)=T(x)2B(x) = T(x)^2 directly encodes "split the object into two independent Fibonacci-tiled pieces" — the same algebraic operation, made combinatorially vivid.

Before this

Where this leads