Generating Functions: linking Sequence & Series

Donald Knuth, et al :
“The most powerful way to deal with sequences of numbers, …, is to manipulate infinite series that generate those sequences.” – “ Concrete Mathematics ”

“…to discover the equation in the first place, using the important method of generating functions, which is a valuable technique for solving so many problems.” – “The Art of Computer Programming Volume I”

Example:
Fibonacci sequence: {0, 1, 1, 2, 3, 5, 8, 13…}

Definition of the Fibonacci sequence as a recurrence relation:
$latex
boxed{
F_{n}=
begin{cases}
0, & text{for }n=0
1, & text{for }n=1
F_{n-2} + F_{n-1} , & text{for } n geq { 2}
end{cases}
}
$

This definition is not so useful in computation, we want to find a general term formula $latex F_{n}$ in terms of n.

Step 1: Find the generating function F(x)

The correspondence below:
Sequence $latex leftrightarrow $ Generating…