text: # 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, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series; 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.
  
  ## 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
  
  $\displaystyle 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
  
  $\displaystyle 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
  
  $\displaystyle EG(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}.$
  
  ### Lambert series
  
  The Lambert series of a sequence an is
  
  $\displaystyle 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.
  
  ### Bell series
  
  The Bell series of an arithmetic function f(n) and a prime p is
  
  $\displaystyle f_p(x)=\sum_{n=0}^\infty f(p^n)x^n.$
  
  ### 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
  
  $\displaystyle DG(a_n;s)=\sum _{n=1}^{\infty} \frac{a_n}{n^s}.$
  
  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
  
  $\displaystyle DG(a_n;s)=\prod_{p} f_p(p^{-s}).$
  
  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
  
  $\displaystyle 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. See the main article generalized Appell polynomials for more information.
  
  ## Examples
  
  Generating functions for the sequence of square numbers an = n2 are:
  
  ### Ordinary generating function
  
  $\displaystyle G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n=\frac{x(x+1)}{(1-x)^3}$
  
  ### Exponential generating function
  
  $\displaystyle EG(n^2;x)=\sum _{n=0}^{\infty} \frac{n^2x^n}{n!}=x(x+1)e^x$
  
  ### Bell series
  
  $\displaystyle f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}$
  
  ### Dirichlet series generating function
  
  $\displaystyle DG(n^2;s)=\sum_{n=1}^{\infty} \frac{n^2}{n^s}=\zeta(s-2)$
  
  ## Another example
  
  Generating functions can be created by extending simpler generating functions. For example, starting with
  
  $\displaystyle G(1;x)=\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$
  
  and replacing $\displaystyle x$ with $\displaystyle 2x$ , we obtain
  
  $\displaystyle G(1;2x)=\frac{1}{1-2x} = 1+(2x)+(2x)^2+\ldots+(2x)^n+\ldots=G(2^n;x).$
  
  ## More detailed example — Fibonacci numbers
  
  Consider the problem of finding a closed formula for the Fibonacci numbers fn defined by f0 = 0, f1 = 1, and fn = fn−1 + fn−2 for n ≥ 2. We form the ordinary generating function
  
  $\displaystyle f = \sum_{n \ge 0} f_n X^n$
  
  for this sequence. The generating function for the sequence (fn−1) is Xf and that of (fn−2) is X2f. From the recurrence relation, we therefore see that the power series Xf + X2f agrees with f except for the first two coefficients. Taking these into account, we find that
  
  $\displaystyle f = Xf + X^2 f + X$
  
  (this is the crucial step; recurrence relations can almost always be translated into equations for the generating functions). Solving this equation for f, we get
  
  $\displaystyle f = \frac{X} {1 - X - X^2}$
  
  The denominator can be factored using the golden ratio φ1 = (1 + √5)/2 and φ2 = (1 − √5)/2, and the technique of partial fraction decomposition yields
  
  $\displaystyle f = \frac{1 / \sqrt{5}} {1-\phi_1 X} - \frac{1/\sqrt{5}} {1- \phi_2 X}$
  
  These two formal power series are known explicitly because they are geometric series; comparing coefficients, we find the explicit formula
  
  $\displaystyle f_n = \frac{1} {\sqrt{5}} (\phi_1^n - \phi_2^n).$
  
  ## Applications
  
  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.