【离散数学】笔记-台湾清华赵启超15A15B Generating Functions

这是台湾清华赵启超教授离散数学14A14B课程的笔记。

应用：

Generating Functions for Solving Recurrence Relations

Example 1 Fibonacci numbers
$F_n=F_{n-1}+F_{n-2},n\ge 2$ with $F_0=0, F_1=1$
Let the generating function for $F_n$ be $F(x)$

$\sum _{n\ge 2}F_nx^n-\sum _{n\ge 2}F_{n-1}x^n-\sum _{n\ge 2} F_{n-2}x^n=0$

$(F(x)-F_0-F_1x)-x(F(x)-F_0)-x^2F(x)=0$

$F(x)(1-x-x^2)=F_0+(F_1-F_0)x=x$

$F(x)=\frac{x}{1-x-x^2}$

(partial fraction expansion)

$F(x)=\frac{\alpha _1}{1-\lambda _1x}+\frac{\alpha _2}{1-\lambda _2x}$

where $\lambda _1=\frac{1+\sqrt{5}}{2}$ and $\lambda _2=\frac{1-\sqrt{5}}{2}$.

$\alpha _1=\frac{1}{\sqrt{5}}$

$\alpha _2=-\frac{1}{\sqrt{5}}$

Therefore $F_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n],n\ge 0$