Generating Function

An irrelevant Biblical reference to illustrate that multiplication is prevalent in Combinatorics

Introduction                          

We'll explore some series. Then we introduce a powerful method in combinatorics called Generating Function. We apply it to extract an explicit formula for the Fibonacci series. This series is well-known, and a search on Google will yield bunch of results, so detailed explanation is unnecessary. The series is originally developed to count the number of rabbit offsprings. So if you have the slightest care about bunnies, continue reading.

Geometric Series

A special case of generating function is geometric series. The simplest geometric series takes the form:

$G(x)=x+x^2+x^3+x^4+...+x^n$

We're interested in finding its sum through cancelling out as much as possible. Note

$  G(x)=x+x^2+x^3+x^4+...+x^n$

$xG(x)= \quad   x^2+x^3+x^4+...+x^n+x^{n+1}$

$G(x)-xG(x)=x-x^n$ (wow, all the middle terms just cancelled)

$G(x)(1-x)=x-x^n$

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

More Series
It is a way to represent different possibilities as sum of variables. For example, if we have to choose four candies from four different brands, let call them $x,y,z$. The generating function of all possible outcome would be:

$ (x+y+z)(x+y+z)(x+y+z)(x+y+z)=(x+y+z)^4$, with $x^4$ meaning that we selecting four candies of brand $x$. $x^2yz$ means that we select $2$ $x's$ and one each for $y$ and $z$. This should not be a radical different idea from what we already know about Multiplication Principle and Multinomial Theorem in Multinomial Theorem

A harder example:
We toss a fair coin some number of times with the probability of heads being $\displaystyle \frac{1}{2}$ and tails $\displaystyle \frac{1}{2}$. What is the possibility that we get all heads?
Let the probability we get heads in any given toss be $x=\displaystyle \frac{1}{2}$. So the question becomes what is the result of this sum:
$S=x+x^2+x^3+x^4+...+x^n+...$
This is because there are infinite possibilities. We can toss the coin once, twice, or $n$ times and get all heads. The sum is all of those possibilities. We can easily calculate this sum using the geometric formula: $S=\displaystyle \lim_{n \to \infty}\frac{x-x^{n+1}}{1-x} =  \frac{x}{1-x} \quad (1)$

Generating Function and Binet Formula

The form of generating function we're interested in is $\sum a_ix^i$ where $a_i$ is the number containing the information we want and $x^i$ just helps the manipulation. It'll be clear in a minute once we do the Fibonacci.

Fibonacci series is defined as this $F_n=F_{n-1}+F_{n-2} \quad (2)$. That is any number in the series is the sum of the two previous terms.

The list is $0,1,1,2,3,5,8,13,21,...$, where $F_0 =0$ and $F_1=1$ by definition.

We're interested in finding the formula for $F_n$ that does not make us calculate $F_{n-1}$ and $F_{n-2}$. So we let the coefficient of the generating function be Fibonacci numbers:
$S=F_0+F_1x+F_2x^2+F_3x^3+F_4x^4+...$
Because we have the $(2)$ nice recursive, linear relation. We should use the same trick we do for geometric series to simplify $S$.
    $S=F_0+F_1x+F_2x^2+F_3x^3+F_4x^4+...$
  $xS=     \quad \quad   F_0x+F_1x^2+F_2x^3+F_3x^4.+..$
$x^2S=   \quad \quad  \quad \quad  F_0x^2+F_1x^3+F_2x^4+...$

$\Rightarrow xS+x^2S+F_0+F_1x=S+F_0x$

$ S(x+x^2-1)=-x \Rightarrow S= \displaystyle \frac{-x}{x^2+x-1} \quad (3)$

We now officially lose sight of the coefficients, which we're going after. So the plan is to separate the single term in $(3)$ into two linear terms, and then use the geometric formula to bring back coefficients.

See MathDoctorBob(Youtube) for more info.