Generating Functions: linking Sequence & Series

Math Online Tom Circle

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.

image

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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