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

View original post 512 more words

## Author: tomcircle

Math amateur

This site uses Akismet to reduce spam. Learn how your comment data is processed.