Generating Function Calculator

Use this Generating Function Calculator to enter values, adjust options, and review results in a compact responsive workspace.

Results are calculated automatically as you enter data.

Input mode

Terms a(0), a(1), ...

Sequence mode returns the exact finite polynomial supplied here. Matching infinite patterns are shown only as unproved candidate continuations.

Coefficient count Coefficient explorer

Coefficient matching and templates

Generating function G(x) appears here.

Disclaimer: All tools on this site are intended for educational and informational purposes only. Estimate only; not professional advice. Verify units, assumptions, precision, and method before relying on results. See our Terms of Use.

Assumptions and limitations

This Generating Function Calculator is for general educational use. Results are estimates or mathematical outputs based on the inputs and stated assumptions, not professional engineering, safety, financial, legal, or academic advice. Check units, rounding, formulas, and limitations before using results for important work. For professional, safety-sensitive, construction, engineering, official, or high-cost uses, verify results with an appropriate method, current standards, required tolerances, and a qualified professional. Use of this calculator is subject to our Terms of Use.

▼ See explanations and tips below ▼

Related Calculators

What Are Ordinary Generating Functions?

An ordinary generating function is a way to package a sequence into a power series. Instead of looking at the sequence as a list,

$$ a_0,\ a_1,\ a_2,\ a_3,\ldots $$

you place those terms next to powers of a variable $x$:

$$ G(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots $$

In compact notation, this is written as:

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

The important idea is that the coefficient of $x^n$ is the sequence term $a_n$. For example,

$$ 3+5x+8x^2+13x^3+\cdots $$

represents the sequence $3,5,8,13,\ldots$ because the coefficient of $x^0$ is $3$, the coefficient of $x^1$ is $5$, the coefficient of $x^2$ is $8$, and so on.

Generating functions are especially useful in discrete mathematics and combinatorics because they let you work with sequences using algebra. A recurrence relation, a counting pattern, or a familiar sequence may turn into a compact expression such as

$$ \frac{1}{1-x},\qquad \frac{x}{1-x-x^2},\qquad \frac{1-\sqrt{1-4x}}{2x} $$

Those expressions do not replace the sequence. They encode it.

Why Ordinary Generating Functions Matter

Generating functions matter because many sequences are easier to understand through a power series than through a term-by-term list.

They are used to:

describe sequences compactly;
extract individual terms from a power series;
solve recurrence relations;
identify familiar patterns such as geometric, arithmetic, Fibonacci, binomial, and Catalan sequences;
prove identities involving coefficients;
turn counting problems into algebraic problems.

A generating function is not always the simplest way to compute a small number of terms. Its strength is that it shows structure. Once a sequence is written as $G(x)$, you can often see shifts, sums, recurrences, and coefficient patterns that are hard to see from the raw list of numbers.

Key Terms to Know

Sequence: An ordered list of terms, usually written $a_0,a_1,a_2,\ldots$.
Coefficient: The number multiplying a power of $x$ in a power series. In $7x^3$, the coefficient of $x^3$ is $7$.
Ordinary generating function: A power series of the form $G(x)=\sum_{n=0}^{\infty}a_nx^n$.
Coefficient extraction: The process of finding the coefficient of a specific power of $x$.
$[x^n]G(x)$: Notation meaning “the coefficient of $x^n$ in $G(x)$.”
Formal power series: A power series treated mainly as an algebraic object, not necessarily as a function to evaluate at a numerical value of $x$.
Recurrence relation: A rule that defines later sequence terms from earlier ones, such as $a_n=a_{n-1}+a_{n-2}$.
Zero-based indexing: Indexing where the first term is $a_0$, not $a_1$.

How Ordinary Generating Functions Work

The basic rule is simple:

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

So the coefficient of $x^n$ is:

$$ a_n=[x^n]G(x) $$

For example, suppose

$$ G(x)=4+9x+16x^2+25x^3+\cdots $$

Then:

$$ [x^0]G(x)=4 $$

$$ [x^1]G(x)=9 $$

$$ [x^2]G(x)=16 $$

The exponent tells you the index. The coefficient tells you the sequence value.

The geometric pattern

The geometric series is one of the most important generating-function building blocks:

$$ 1+x+x^2+x^3+\cdots=\frac{1}{1-x} $$

Replacing $x$ with $rx$ gives:

$$ 1+rx+r^2x^2+r^3x^3+\cdots=\frac{1}{1-rx} $$

So a geometric sequence of the form

$$ a_n=a_0r^n $$

has ordinary generating function

$$ G(x)=\frac{a_0}{1-rx} $$

For example, the sequence $1,2,4,8,16,\ldots$ has $a_0=1$ and $r=2$, so:

$$ G(x)=\frac{1}{1-2x} $$

The arithmetic pattern

An arithmetic sequence has a constant difference. If

$$ a_n=a_0+dn $$

then its ordinary generating function can be written as:

$$ G(x)=\frac{a_0}{1-x}+\frac{dx}{(1-x)^2} $$

The first part accounts for the constant starting level $a_0$. The second part accounts for the steady increase by $d$ each time the index increases.

For example, the sequence $1,3,5,7,9,\ldots$ has $a_0=1$ and $d=2$, so:

$$ G(x)=\frac{1}{1-x}+\frac{2x}{(1-x)^2} $$

The binomial-coefficient pattern

Powers of $\frac{1}{1-x}$ generate familiar coefficient patterns. For a positive integer $k$,

$$ \frac{1}{(1-x)^k}=\sum_{n=0}^{\infty}\binom{n+k-1}{k-1}x^n $$

That means:

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

For example,

$$ \frac{1}{(1-x)^3}=1+3x+6x^2+10x^3+15x^4+\cdots $$

The coefficients $1,3,6,10,15,\ldots$ are triangular-number-style values. If $k=0$, the expression $\frac{1}{(1-x)^0}$ is simply $1$, so the only nonzero coefficient is the constant term.

The Fibonacci pattern

The Fibonacci sequence with $F_0=0$ and $F_1=1$ satisfies:

$$ F_n=F_{n-1}+F_{n-2} $$

Its ordinary generating function is:

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

The denominator reflects the recurrence. A second-order recurrence that depends on the previous two terms often produces a denominator involving $1$, $x$, and $x^2$.

The related generating function

$$ \frac{1}{1-x-x^2} $$

has coefficients $1,1,2,3,5,8,\ldots$, which are the Fibonacci numbers shifted by one index.

The Catalan pattern

The Catalan numbers begin:

$$ 1,\ 1,\ 2,\ 5,\ 14,\ 42,\ldots $$

Their ordinary generating function is commonly written as:

$$ C(x)=\frac{1-\sqrt{1-4x}}{2x} $$

So:

$$ C(x)=1+x+2x^2+5x^3+14x^4+\cdots $$

Catalan numbers appear in many counting problems, including polygon triangulations, binary bracketings, certain trees, and paths. The square root in the generating function is a signal that the sequence is not just geometric or rational in the simplest sense; it comes from a quadratic relationship in the underlying counting structure.

Recurrences and generating functions

Generating functions are especially helpful for recurrence relations. Suppose a sequence starts with $a_0$ and satisfies the first-order recurrence

$$ a_n=r\,a_{n-1}+c $$

for $n\ge 1$. Its ordinary generating function satisfies:

$$ G(x)=a_0+rxG(x)+\frac{cx}{1-x} $$

Solving for $G(x)$ gives:

$$ G(x)=\frac{a_0+\frac{cx}{1-x}}{1-rx} $$

For a Fibonacci-style recurrence with initial values $a_0$ and $a_1$,

$$ a_n=a_{n-1}+a_{n-2} $$

for $n\ge 2$, the ordinary generating function is:

$$ G(x)=\frac{a_0+(a_1-a_0)x}{1-x-x^2} $$

These formulas show why recurrence relations and generating functions fit together so naturally: shifting a sequence by one or two indices corresponds to multiplying and rearranging the power series.

Examples of Ordinary Generating Functions in Practice

Example 1: Reading coefficients from a power series

Suppose

$$ G(x)=6-2x+9x^2+0x^3+11x^4+\cdots $$

Then the first terms of the sequence are:

$$ a_0=6,\qquad a_1=-2,\qquad a_2=9,\qquad a_3=0,\qquad a_4=11 $$

The zero coefficient matters. The term $0x^3$ means the coefficient of $x^3$ is $0$, so $a_3=0$.

Example 2: A geometric sequence

Take the sequence:

$$ 5,\ 15,\ 45,\ 135,\ldots $$

Here $a_0=5$ and the common ratio is $r=3$. The ordinary generating function is:

$$ G(x)=\frac{5}{1-3x} $$

The expansion begins:

$$ \frac{5}{1-3x}=5+15x+45x^2+135x^3+\cdots $$

So:

$$ [x^2]G(x)=45 $$

Example 3: A Fibonacci recurrence

Let $F_0=0$, $F_1=1$, and

$$ F_n=F_{n-1}+F_{n-2} $$

The generating function is:

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

Its expansion begins:

$$ F(x)=0+x+x^2+2x^3+3x^4+5x^5+8x^6+\cdots $$

So:

$$ [x^6]F(x)=8 $$

This means $F_6=8$.

Example 4: An arithmetic sequence

Take the sequence:

$$ 4,\ 7,\ 10,\ 13,\ldots $$

Here $a_0=4$ and $d=3$. The ordinary generating function is:

$$ G(x)=\frac{4}{1-x}+\frac{3x}{(1-x)^2} $$

The first fraction supplies the baseline $4,4,4,4,\ldots$. The second fraction supplies $0,3,6,9,\ldots$. Adding them term by term gives $4,7,10,13,\ldots$.

Example 5: An exact finite generating polynomial

If only a short list of terms is known, such as

$$ 2,\ 5,\ 10,\ 17 $$

the exact finite polynomial represented by those supplied coefficients is:

$$ G(x)=2+5x+10x^2+17x^3 $$

This does not prove that the sequence stops or that it has no infinite pattern. It only represents the terms that were supplied. More terms or more context may be needed to identify a deeper rule.

How to Interpret the Result

The main result, $G(x)$, is the ordinary generating function. It tells you how the sequence is encoded as coefficients of powers of $x$.

The selected coefficient is written in coefficient-extraction notation:

$$ [x^n]G(x)=a_n $$

This means “look at the coefficient of $x^n$ in the expansion of $G(x)$.” The result is the sequence value at index $n$.

A power-series preview shows the beginning of the expansion, such as:

$$ G(x)=1+2x+4x^2+8x^3+\cdots $$

This preview is useful because it connects the compact formula back to the visible sequence terms.

A coefficient table lists each index $n$, the coefficient $a_n$, and the corresponding series term $a_nx^n$. A chart helps you see whether coefficients are growing, alternating signs, staying constant, or following another visible pattern.

In sequence mode, the main result is always the exact finite polynomial represented by the supplied coefficients. Exact arithmetic, geometric, Fibonacci, or Catalan matches may be listed separately as candidate infinite continuations, but a finite prefix does not prove any of them. Function and recurrence modes describe explicitly requested infinite generating functions.

Common Mistakes and Misconceptions

Starting at $a_1$ instead of $a_0$

Ordinary generating functions usually start at $n=0$:

$$ G(x)=a_0+a_1x+a_2x^2+\cdots $$

If you enter a sequence as though the first term were $a_1$, every coefficient may be shifted by one position. That changes the generating function.

Confusing ordinary and exponential generating functions

An ordinary generating function uses:

$$ \sum_{n=0}^{\infty}a_nx^n $$

An exponential generating function uses:

$$ \sum_{n=0}^{\infty}a_n\frac{x^n}{n!} $$

They are different tools. The calculator discussed here works with ordinary generating functions.

Expecting every expression to be accepted

Some generating-function tools are template-based. That means they recognize specific forms such as:

$$ \frac{1}{1-rx},\qquad \frac{1}{(1-x)^k},\qquad \frac{x}{1-x-x^2},\qquad \frac{1-\sqrt{1-4x}}{2x} $$

A mathematically valid expression may still be unsupported if it is outside the recognized templates.

Treating a finite preview as a proof of the full sequence

An exact finite generating polynomial records only the terms supplied. For example,

$$ 1+2x+4x^2+8x^3 $$

matches the first four terms of a geometric sequence, but by itself it is still only a four-term polynomial. A different sequence could share those first four terms and then continue differently.

Ignoring zero coefficients

A missing power of $x$ has coefficient $0$. For example,

$$ 3+7x^2 $$

means:

$$ a_0=3,\qquad a_1=0,\qquad a_2=7 $$

Do not skip the missing power when reading the sequence.

Rounding too early

Some displayed numeric outputs may be rounded or shown in scientific notation. For exact symbolic work, keep the formula and the coefficient definition in mind, not just the formatted decimal display.

When to Use Ordinary Generating Functions

Use ordinary generating functions when you want to:

encode a sequence as a power series;
find the coefficient associated with a specific index;
recognize common sequence patterns;
connect a recurrence relation to a compact formula;
compare two sequences by comparing their generating functions;
study sequences in combinatorics, discrete mathematics, and recurrence problems.

They are especially helpful when the index $n$ is central to the problem and when sequence terms are naturally tied to powers $x^n$.

Limitations and Things to Keep in Mind

Generating functions are powerful, but they do not remove the need to understand the sequence.

Important limitations include:

Ordinary generating functions are not the same as exponential generating functions.
The first coefficient is $a_0$, so indexing must be handled carefully.
A template-based calculator may recognize only selected generating-function forms.
A short sequence can match more than one possible rule, so detected continuations are candidates rather than automatic answers.
A recurrence relation needs enough initial values to determine the generated terms.
Numeric entries support exact rational forms—integers, decimals, scientific notation, and simple fractions—but not arbitrary symbolic constants or complex numbers.
Exact fractions remain available in formulas and coefficient tables; decimal approximations and charts are secondary displays.
A coefficient chart is a visual aid, not a proof of a pattern.

For mathematical proofs, coursework, research, or published work, use the result as a guide and verify the formulas independently.

How to Use This Calculator

Choose sequence, function, or recurrence mode.
In sequence mode, enter numeric terms separated by commas, spaces, or semicolons.
In function mode, enter one of the recognized ordinary generating-function templates.
In recurrence mode, enter a supported recurrence rule and the required initial terms.
Enter a coefficient count from $4$ to $40$.
Use the slider, chart, or table to choose the index $n$ you want to inspect.
Review $G(x)$, the detected source, the expansion preview, the selected coefficient, and the coefficient table.
Use example presets to load sample Fibonacci, binomial, Catalan, geometric, or sequence inputs.
When a coefficient chart is shown, use the graph download option if you need a PNG copy.

Frequently Asked Questions

What does $[x^n]G(x)$ mean?

The notation $[x^n]G(x)$ means “the coefficient of $x^n$ in $G(x)$.” If $G(x)=2+5x+9x^2$, then $[x^2]G(x)=9$.

Why does the sequence start at $a_0$?

The power series starts with $x^0$, and $x^0=1$, so the constant term naturally corresponds to $a_0$. This is why ordinary generating functions commonly use zero-based indexing.

Is $x$ supposed to be a real number?

In many generating-function problems, $x$ is treated as a formal variable. The main goal is to track coefficients, not necessarily to plug in a numerical value for $x$.

What is the difference between $G(x)$ and $a_n$?

$G(x)$ is the whole generating function. The value $a_n$ is one coefficient from that function, found by extracting the coefficient of $x^n$.

Why does $\frac{1}{1-rx}$ generate a geometric sequence?

Because the geometric-series expansion gives:

$$ \frac{1}{1-rx}=1+rx+r^2x^2+r^3x^3+\cdots $$

The coefficient of $x^n$ is $r^n$. Multiplying by $a_0$ gives coefficients $a_0r^n$.

What does $\frac{1}{(1-x)^k}$ generate?

For a positive integer $k$, it generates the coefficients

$$ \binom{n+k-1}{k-1} $$

at index $n$. These coefficients appear in many counting problems, especially those involving combinations with repetition.

Why does the Fibonacci generating function have denominator $1-x-x^2$?

The Fibonacci recurrence uses the two previous terms. When the sequence is encoded as a power series, those shifted terms produce an algebraic equation whose denominator is $1-x-x^2$.

What does the exact finite polynomial mean?

It means the entered coefficients have been represented directly as a finite polynomial, such as $a_0+a_1x+a_2x^2$. It does not prove an infinite continuation. Any exactly matching supported continuation is displayed separately as an unproved candidate.

Can negative or decimal coefficients be used?

Negative and decimal numeric terms can be meaningful in ordinary generating functions when the tool accepts them as finite numbers. However, symbolic constants, complex numbers, and algebraic expressions may not be supported in numeric sequence or recurrence inputs.

Why might a geometric sequence with zero terms not be detected?

A common ratio is found by dividing one term by the previous term. If a needed previous term is zero, that division is not valid, so geometric detection may not apply even if the surrounding terms look patterned.

Sources and References

Books and Textbooks

Herbert S. Wilf. generatingfunctionology. 2nd ed., Academic Press, 1994. Chapters 1 and 2, especially introductory generating-function examples, ordinary power-series generating functions, coefficient extraction, and recurrence methods. Internet edition hosted by the University of Pennsylvania.
Oscar Levin. Discrete Mathematics: An Open Introduction. OpenMathBooks, Section 5.1, “Generating Functions.” Used for the introductory explanation of generating functions, coefficient reading, geometric-series examples, and basic sequence interpretation. Read online.

Online and Reference Sources

Eric W. Weisstein. “Catalan Number.” Wolfram MathWorld, accessed June 28, 2026. Used for Catalan-number formulas, generating-function form, and examples of Catalan-number applications. Read online.

Generating Function Calculator