淺談生成函數推導斐波那契數列以及特征函數

淺談生成函數推導斐波那契數列以及特征函數

一次數學課，尊敬的Mr.ZHU與L先生提出了一個叫做特征函數的東西，作為前競賽生的Marcelo Jin 一驚，這不正是生成函數的化簡版嘛，于是他決定，周日的時候再來好好回顧一下這個有趣的算法。

一.關于生成函數

1.數列的多項式表示法

對于一個數列\(a_n\),我們可以利用一個多項式來表示它，即\(A(x)=\Sigma a_i x^i\)

舉個例子，對于數列\(a_n=n\),它的多項式表示法就是\(A(x)=x+2x^2+3x^3+...\)

這裡的多項式是形式幂級數，也就是變量隻是一個符号，我們不關心它取值帶來的影響，隻關心它所攜帶的資訊。

因為本篇着眼于文化課上的生成函數應用，是以暫且不提指數型生成函數

2.生成函數的封閉形式

再舉個例子，對于序列\(<1,1,1,1...>\)，它的生成函數要寫成一個多項式的形式，十分不直覺，我們可以考慮把它的生成函數寫成一個封閉的形式。

這裡，分享兩個方法。

設該數列的生成函數為\(A(x)\)

Solution 1：

根據我們國小就學過的等比數列求和公式，

\(

A(x)=\frac{x^n-1}{x-1}

\)

是以\(lim_{n\rightarrow+\infty} A(x)=\frac{1}{1-x}\)

Solution 2:

\(A(x)⋅x+1=A(x)\)

\(So\) \(we\) \(have\) \(A(x)=\frac{1}{1-x}\)

推廣一下，又有

\(\frac{1}{1-kx}=1+kx+k^2x^2+k^3x^3...\)

也就是說，生成函數為\(\frac{1}{1-kx}\)的數列的通項公式為\(a_n=k^n\)

3.生成函數的應用

生成函數一般有兩個用途

1.對于給定的遞推公式，求其通項公式

2.解決一些計數類問題

二.斐波那契數列通項公式的推導

我們設斐波那契數列的通項公式為\(f_n\)，設其生成函數為\(F(x)\)，那麼

F(x)=\Sigma{f_ix^i}=f_1x+ \Sigma_{i\geq2}{f_ix^i}

=x+\Sigma_{i\geq2}(f_{i-2}+f_{i-1})x^i

=x+x^2\Sigma_{i\geq2}f_{i-2}x^{i-2}+x\Sigma_{i\geq2}f_{i-1}x^{i-1}

=x+x^2F(x)+xF(x)

三.關于特征函數