How to Find a Closed Form for an nth Term Using Generating Functions

A generating function can convert a recurrence into an algebraic equation. Once you solve that equation, extracting the coefficient of $x^n$ gives the sequence’s nth term. For many linear recurrences with constant coefficients, this leads to a formula involving powers of a few roots.

There is no single closed-form formula that works for every generating function. The method is to derive the function correctly and then choose a coefficient-extraction technique that fits its form.

Encode the sequence

For a sequence $a_0,a_1,a_2,\ldots$, its ordinary generating function is

$$A(x)=\sum_{n=0}^{\infty}a_nx^n.$$

The coefficient of $x^n$ in $A(x)$ is $a_n$, written $[x^n]A(x)=a_n$. A recurrence for $a_n$ creates relations among shifted versions of this series. For example,

$$\sum_{n\geq 0}a_{n+1}x^n=\frac{A(x)-a_0}{x}, \qquad \sum_{n\geq 0}a_{n+2}x^n=\frac{A(x)-a_0-a_1x}{x^2}.$$

These identities are useful because they express shifted sequence terms using $A(x)$ and the initial values.

A step-by-step method

1. Choose the indexing. Decide whether the sequence starts at $n=0$ or $n=1$, and define $A(x)$ accordingly.
2. Multiply and sum the recurrence. If the recurrence is valid for $n\geq 0$, multiply each side by $x^n$ and sum over those indices. Use shifted-series identities, keeping the initial terms separate.
3. Solve for $A(x)$. Rearrange the resulting equation. A linear recurrence with constant coefficients usually gives a rational function.
4. Extract $[x^n]A(x)$. Factor the denominator, use partial fractions, or apply a known series expansion.
5. Check initial terms. Compare the formula with the given starting values and, if practical, substitute it into the recurrence.

Worked example: the Fibonacci sequence

Let $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$ for $n\geq 0$. Define

$$F(x)=\sum_{n\geq 0}F_nx^n.$$

Summing the recurrence after multiplying by $x^n$ gives

$$\sum_{n\geq 0}F_{n+2}x^n = \sum_{n\geq 0}F_{n+1}x^n+ \sum_{n\geq 0}F_nx^n.$$

The left side is $(F(x)-F_0-F_1x)/x^2$, and the first sum on the right is $(F(x)-F_0)/x$. Substituting $F_0=0$ and $F_1=1$ yields

$$\frac{F(x)-x}{x^2}= \frac{F(x)}{x}+F(x).$$

Multiplying by $x^2$ and collecting the terms in $F(x)$ gives

$$F(x)=\frac{x}{1-x-x^2}.$$

Let $\phi=(1+\sqrt{5})/2$ and $\psi=(1-\sqrt{5})/2$. Since $\phi+\psi=1$ and $\phi\psi=-1$, the denominator factors as

$$1-x-x^2=(1-\phi x)(1-\psi x).$$

Partial fractions give

$$F(x)=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\phi x}-\frac{1}{1-\psi x}\right).$$

Using the geometric-series identity $1/(1-rx)=\sum_{n\geq 0}r^nx^n$, compare coefficients of $x^n$ to obtain

$$F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}.$$

This is a closed form for every $n\geq 0$. Although it contains square roots and can look non-integer, its value is an integer because it equals the Fibonacci number defined by the recurrence.

Why partial fractions work

A common piece of a rational generating function has the form $C/(1-rx)^k$, where $k$ is a positive integer. Its coefficient is

$$[x^n]\frac{C}{(1-rx)^k} =C\binom{n+k-1}{k-1}r^n.$$

Thus, for a proper rational function whose denominator factors into linear terms, partial fractions produce a finite sum of terms that are polynomials in $n$ times powers of constants. If the rational function has a polynomial part, that part contributes only finitely many coefficients and must be included separately. Repeated roots account for the polynomial factors in $n$. If the denominator has irreducible quadratic factors over the real numbers, the resulting expression can instead be written using complex roots or equivalent trigonometric terms.

Common mistakes

• Dropping initial terms: A shifted series such as $\sum_{n\geq 0}a_{n+1}x^n$ is not simply $A(x)/x$. The missing starting terms must be subtracted.
• Starting the sum at the wrong index: A recurrence may hold only for $n\geq 1$ or later. The range changes which initial terms appear in the generating-function equation.
• Mixing ordinary and exponential generating functions: This article uses $\sum a_nx^n$. An exponential generating function uses $\sum a_nx^n/n!$ and has different shift rules.
• Assuming every answer is elementary: A generating function may have coefficients expressible only through a more advanced function, or the phrase “closed form” may not have a universally agreed boundary. A useful result can still be a coefficient formula or an exact recurrence.

When the generating function is not rational

The same principle still applies: the nth term is the coefficient $[x^n]A(x)$. But a non-rational generating function may require methods such as the binomial theorem, known series expansions, or contour integration to extract that coefficient. First simplify the function and identify a series expansion valid around $x=0$; then read off the coefficient matching the chosen indexing.