小马的世界

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

2021-08-13 · 3 min read
离散数学 数学

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

应用:

Generating Functions for Solving Recurrence Relations

Example 1 Fibonacci numbers
Fn=Fn1+Fn2,n2F_n=F_{n-1}+F_{n-2},n\ge 2 with F0=0,F1=1F_0=0, F_1=1
Let the generating function for FnF_n be F(x)F(x)

n2Fnxnn2Fn1xnn2Fn2xn=0\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)F0F1x)x(F(x)F0)x2F(x)=0(F(x)-F_0-F_1x)-x(F(x)-F_0)-x^2F(x)=0

F(x)(1xx2)=F0+(F1F0)x=xF(x)(1-x-x^2)=F_0+(F_1-F_0)x=x

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

(partial fraction expansion)

F(x)=α11λ1x+α21λ2xF(x)=\frac{\alpha _1}{1-\lambda _1x}+\frac{\alpha _2}{1-\lambda _2x}

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

α1=15\alpha _1=\frac{1}{\sqrt{5}}

α2=15\alpha _2=-\frac{1}{\sqrt{5}}

Therefore Fn=15[(1+52)n(152)n],n0F_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n],n\ge 0