Generating function

From Academic Kids

In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers.

There are various types of generating functions - definitions and examples are given below. Every sequence has a generating function of each type. The particular generating function that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed.

Generating functions are often expressed in closed form as functions of a formal argument x. Sometimes a generating function is evaluated at a specific value of x. However, it must be remembered that generating functions are formal power series, and they will not necessarily converge for all values of x.

Contents

Definitions

A generating function is a clothesline on which we hang up a sequence of numbers for display. -- Herbert Wilf, generatingfunctionology (1994)

Ordinary generating function

The ordinary generating function of a sequence an is

<math>G(a_n;x)=\sum_{n=0}^{\infty}a_nx^n.<math>

When generating function is used without qualification, it is usually taken to mean an ordinary generating function.

If an is the probability mass function of a discrete random variable, then its ordinary generating function is called a probability-generating function.

The ordinary generating function can be generalised to sequences with multiple indexes. For example, the ordinary generating function of a sequence am,n (where n and m are natural numbers) is

<math>G(a_{m,n};x,y)=\sum_{m,n=0}^{\infty}a_{m,n}x^my^n.<math>

Exponential generating function

The exponential generating function of a sequence an is

<math>EG(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}.<math>

Lambert series

The Lambert series of a sequence an is

<math>LG(a_n;x)=\sum _{n=1}^{\infty} a_n \frac{x^n}{1-x^n}.<math>

Note that in a Lambert series the index n starts at 1, not at 0.

Bell series

The Bell series of an arithmetic function f(n) and a prime p is

<math>f_p(x)=\sum_{n=0}^\infty f(p^n)x^n.<math>

Dirichlet series generating functions

Dirichlet series are often classified as generating functions, although they are not strictly formal power series. The Dirichlet series generating function of a sequence an is

<math>DG(a_n;s)=\sum _{n=1}^{\infty} \frac{a_n}{n^s}.<math>

The Dirichlet series generating function is especially useful when an is a multiplicative function, when it has an Euler product expression in terms of the function's Bell series

<math>DG(a_n;s)=\prod_{p} f_p(p^{-s}).<math>

If an is a Dirichlet character then its Dirichlet series generating function is called a Dirichlet L-series.

Polynomial sequence generating functions

The idea of generating functions can be extended to sequences of other objects. Thus, for example, polynomial sequences of binomial type are generated by

<math>e^{xf(t)}=\sum_{n=0}^\infty {p_n(x) \over n!}t^n<math>

where pn(x) is a sequence of polynomials and f(t) is a function of a certain form. Sheffer sequences are generated in a similar way.

Examples

Generating functions for the sequence of square numbers an = n2 are:

Ordinary generating function

<math>G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n=\frac{x(x+1)}{(1-x)^3}<math>

Exponential generating function

<math>EG(n^2;x)=\sum _{n=0}^{\infty} \frac{n^2x^n}{n!}=x(x+1)e^x<math>

Bell series

<math>f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}<math>

Dirichlet series generating function

<math>DG(n^2;s)=\sum_{n=1}^{\infty} \frac{n^2}{n^s}=\zeta(s-2)<math>

Another example

Generating functions can be created by extending simpler generating functions. For example, starting with

<math>G(1;x)=\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}<math>

and replacing <math>x<math> with <math>2x<math>, we obtain

<math>G(1;2x)=\frac{1}{1-2x} = 1+(2x)+(2x)^2+\ldots+(2x)^n+\ldots=G(2^n;x).<math>

Uses

Generating functions are used to

  • Find recurrence relations for sequences - the form of a generating function may suggest a recurrence formula.
  • Find relationships between sequences - if the generating functions of two sequences have a similar form, then the sequences themselves are probably related.
  • Explore the asymptotic behaviour of sequences.
  • Prove identities involving sequences.
  • Solve enumeration problems in combinatorics.
  • Evaluate infinite sums.

See also

References

  • Wilf, Herbert S. (1994) generatingfunctionology (Second Edition). Academic Press. ISBN 0127519564. For a downloadable version provided by Herbert Wilf and Academic Press, see this link: Download the book Generatingfunctionology (http://www.math.upenn.edu/%7Ewilf/DownldGF.html)

External links

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools