# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Generating function

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

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

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

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

### Exponential generating function

The exponential generating function of a sequence an is

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

### Lambert series

The Lambert series of a sequence an is

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

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

### 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

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

Dirichlet series generating functions are especially useful for multiplicative functions, when they have an Euler product expression. 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

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

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

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

### Exponential generating function

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

### Dirichlet series generating function

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

## 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.