A formal variable that marks coefficient positions and need not be evaluated numerically.

A series interpreted through its coefficients and formal algebraic operations, without requiring convergence.

Exponential generating function (EGF)

For a sequence $a_0,a_1,\ldots$, the series $E(x)=\sum_{n\geq0}a_nx^n/n!$.

A series of the form $\sum_{n\geq1}a_nx^n/(1-x^n)$, whose coefficients encode divisor sums.

Discrete mathematicsLesson 3 of 3 in the course Number theory and recurrences

Generating Functions: Formal Series, Operations, and Applications

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course

Lesson progress

0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

A generating function packages a sequence into a single formal expression. This lets us study sequences using algebraic operations rather than handling every term separately.

For a sequence $a_0,a_1,a_2,\ldots$ , an ordinary generating function (OGF) is

$G(x)=\sum_{n=0}^{\infty}a_nx^n=a_0+a_1x+a_2x^2+\cdots.$

The coefficient of $x^n$ records the term $a_n$ . The variable $x$ is an indeterminate: it marks the position of each coefficient. A generating function is like a bag containing all the terms of a sequence, or a display line on which each term is hung at its indexed position.

All flashcards

Ordinary generating function (OGF): For a sequence $a_0,a_1,\ldots$ , the formal series $G(x)=\sum_{n\geq0}a_nx^n$ , with $a_n$ as the coefficient of $x^n$ .
Indeterminate: A formal variable that marks coefficient positions and need not be evaluated numerically.
Formal power series: A series interpreted through its coefficients and formal algebraic operations, without requiring convergence.
Exponential generating function (EGF): For a sequence $a_0,a_1,\ldots$ , the series $E(x)=\sum_{n\geq0}a_nx^n/n!$ .
Lambert series: A series of the form $\sum_{n\geq1}a_nx^n/(1-x^n)$ , whose coefficients encode divisor sums.

Quiz questions

What does the coefficient of $x^n$ in an ordinary generating function represent?Answer: The sequence term $a_n$ at index $n.
Must a formal power series converge at any nonzero numerical value of its variable?Answer: No; formal algebra does not require numerical convergence.
Which mathematician used generating functions in 1730 to solve linear recurrence problems?Answer: Abraham de Moivre.
Which expression is not an ordinary formal power series in nonnegative integer powers of $x$ ?Answer: $x^{-1}+1+x$
Why can one type of generating function be more useful than another for a particular sequence?Answer: Different types suit different sequence structures and mathematical operations.

Based on the Wikipedia article Generating function, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

All Discrete mathematics lessons

Discrete mathematicsBinary Relations: Operations, Properties, Functions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsPigeonhole Principle: Counting, Collisions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsDe Morgan's Laws in Logic, Set Theory, and Boolean Algebra5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsEulerian Routes: Criteria, Construction, and Extensions5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsNumber Theory: Integer Structure, Methods, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsBinomial Coefficients: Expansion, Counting, and Identities5 flashcards · 5 quiz questions · 4 gamesPlay free →

Summary

All flashcards

Quiz questions

More in Discrete mathematics