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 ”
“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
