**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…**

View original post 512 more words