我們轉移到附近的咖啡店，草草點完單後又繼續開始剛才的數列的話題。抓住數列的要害究竟是怎麼回事呢？兩個王國又到底是什麼呢？聽了我的問題，米爾嘉推了推眼鏡說：「嗯，是啊。」
4.2.1 斐波那契數列
是啊。這個比喻可能不太符合邏輯，太誇張了。「在兩個王國裡穿梭漫步，抓住數列的要害」其實就是「運用生成函數來求數列的通項」呀。
現在給你看看「旅行地圖」吧。首先，求得與數列相對應的生成函數。其次，將生成函數變形，求出生成函數的有限項代數式。然後再將有限項式根據冪級數展開，最終求得數列的通項。也就是說，通過生成函數來找出數列的通項。
「運用生成函數來求數列的通項」的「旅行地圖」
例如，以數列中的斐波那契數列為例。你知道斐波那契數列吧？
這個數列從第三項開始，每一項都等於前兩項之和。
這個數列也有從 1 開始的情況，但是這裡我們從 0 開始。
我們假設 Fn 為斐波那契數列的通項。F0 和 0 相等，F1 和 1 相等，當 n ≥ 2 時，則 
，所以 Fn 就被定義為表示各項間關係的推導公式。
斐波那契數列的定義（推導公式）
「從第三項開始，每一項都等於前兩項之和」——斐波那契數列的這個性質在這個定義中得到了充分的體現。另外，還可以像 F0, F1, F2, ... 這樣計算出斐波那契數列。但是，Fn 沒有表現為「關於 n 的有限項代數式」。也就是說，通項公式 Fn 中並未使用 n，不是關於 n 的直接代數式。這也就是我所說的「沒有抓住數列的要害」狀態。
現在我們假設要求斐波那契數列的第 1000 項是多少。一般情況下，我們就用 F0 + F1 來求 F2，用 F1 + F2 來求 F3，…… 如此重複計算後，最後通過求 F998 + F999 的和才能算出 F1000 的值。如果靠推導公式來計算 Fn 的話，那麼要進行 n - 1 次加法計算。這實在太無聊了。我想將 Fn 表示成「關於 n 的有限項代數式」。「關於 n 的有限項代數式」究竟是什麼意思呢？粗略地說，它就是「將大家都知道的運算方法在有限的次數內進行組合後得到的代數式」。
我很想將 Fn 表示成「關於 n 的有限項代數式」，抓住斐波那契數列的要害。
問題 4-1
將斐波那契數列的通項 Fn 表示成「關於 n 的有限項代數式」。
4.2.2 斐波那契數列的生成函數
那麼，接下來我們就將與斐波那契數列相對應的生成函數稱為 F(x)。也就是說，我們將其對應關係表現為以下形式。
在函數 F(x) 中，如果將 xn 這一項的係數用 Fn 來表示，那麼整個函數就可以用以下式子表示出來。這樣，我們就可以向生成函數的王國過渡了。
接下來，我想調查一下函數 F(x) 的性質。函數 F(x) 的係數 Fn 是斐波那契數列的通項，如果好好利用這點的話，我們很快就能找到關於函數 F(x) 的有趣性質。
斐波那契數列的性質究竟是什麼呢？當然我們剛才已經求得推導公式 ，如果我們好好利用這個表示各項間關係的推導公式的話，
這樣的係數就可以在 F(x) 的計算過程中出現。如下所示。
我想把係數 
和 
相加試試看，但是 x 的冪次方互不相同，所以不能合併同類項。那該怎麼辦呢？
◎ ◎ ◎
米爾嘉看看我。嗯。x 的冪次方確實不同，不能將它們的係數直接相加。因為它們不是同類項，所以不能合併。將數列和生成函數相互對應，真的會發生有趣的現象嗎？——終於，從米爾嘉嘴裡吐出了一句：「很簡單哦。」
4.2.3 封閉表達式
很簡單哦。
x 的冪次方如果互不相同的話，將不同的部分乘上 x 就好了。同底數冪相乘，底數不變指數相加，也就是所謂的指數運算法則。
例如，
乘以 x2 的話得 
。如下所示，如果巧妙地進行乘法運算的話，就可以統一為 xn 的形式。為了使形式統一，我們將 1 寫作 x0。
這樣一來，我們就可以運用與函數 F(x) 相對應的斐波那契數列的推導公式了。好，我們將 F(x) 分別和 x2, x1, x0 相乘後的式子寫下來看看。
這樣就統一了冪次項。利用式子 A、式子 B、式子 C，我們接著進行計算。這樣一來，我們就可以運用同類項係數 Fn 的推導公式。
式子A +式子B -式子C
在進行計算的時候，式子左邊就變成了以下形式。
然後，式子右邊變為以下形式。
式子右邊經計算就只剩下起始部分 
，其他部分全都抵消了。為什麼這麼說呢？這是因為根據斐波那契數列的推導公式，
這部分等於 0，任何數乘以 0 都會馬上消失。
我們已經沒什麼必要寫成 x0 和 x1 的形式了，直接寫 1 和 x 就可以了。那麼，F0 就可以寫成 0，F1 就可以寫成 1。於是，我們得到了以下式子。
兩邊同時除以 
，整理後就能求得 F(x) 的有限項代數式。這就是 F(x) 的廬山真面目哦。
我看到斐波那契數列的生成函數變形成了這樣一個簡單的有限項代數式，心中雀躍無比。因為這個代數式包括了無限延續下去的斐波那契數列的全部內容，是一個高度濃縮的式子。
斐波那契數列的生成函數 F(x) 的封閉表達式
4.2.4 用無窮級數來表示
我們思考討論了斐波那契數列的生成函數 F(x)。如果用 x 來表示 F(x) 的有限項代數式，x 的 n 次方前的係數應該是 Fn。
所以，接下來我們的目標是想辦法將 
用 x 的無窮級數來表示。
我們曾經用下面的分式形式來表現過關於 x 的無窮級數。
比如說，我們能否想辦法將 變成與 
類似的形式呢？如果可能的話，我們就能從生成函數的王國回到數列的王國了。回去的時候當然不能空手，請帶一件生成函數王國的「土特產」噢。那就是斐波那契數列的通項公式。你覺得如何？
◎ ◎ ◎
米爾嘉盯著我的眼睛。啊，對了，接下來只要把生成函數 F(x) 寫成無窮級數的形式，就可以求得斐波那契數列的通項公式了吧。我一直盯著生成函數的形式看，徹底弄清了其結構。
分母 
是個二次代數式。首先，先試試將 因式分解。我在練習本上又開始計算起來。米爾嘉一直在旁邊盯著看。
假設有未知常數 r 和 s，式子 便可分解成以下形式。
如果照上述式子那樣分解的話，通過求下面式子的分數和，在通分的時候分母就正好可以變形成 的形式了。
計算這個式子，當它變形成 的形式後，再求出 r 和 s 就可以了。
嗯，只要我們順利計算出 r 和 s 的值，分母 
就有可能變成 的形式。但是，分子 
卻很難變形為 x 的形式，因為常數 2 無法被抵消。
當我在嘀咕時，米爾嘉在一旁提示說：「如果用這種方法，就能順利進行下去哦。」
4.2.5 解決
如果用這種方法，就能順利進行下去哦。
我們在分子裡放入參數。也就是說，假設有 4 個未知常數 R，S，r，s，接著思考以下式子就好了。
計算此式。
如果要使以下式子成立，只要確定常數 R，S，r，s 分別為多少就可以了。
比較等式左右兩邊後，只要解出以下聯立方程組就可以了。
4 個未知數配有 4 個獨立的等式。我們試著解一下這個聯立方程組。
首先，將 R 和 S 分別轉化成只含有 r 和 s 的關係式。
這樣一來，就找到了用無窮級數來表示 F(x) 的頭緒。我們先暫且不求出 r 和 s 具體為多少，繼續推導下去。
這裡將 
，
代入。
再將 
用 
代入，將 
用 
代入。
然後整理一下。
於是，我們就求得了用 r 和 s 所表示的斐波那契數列的通項公式。
接下來只剩計算 r 和 s 的值這一步了。關於 r 和 s 的聯立方程組為
用通常解聯立方程組的方法當然也可以，不過既然 r、s 的和為 1，積為 -1，那麼就可以說它們是方程 
的解。也就是說，解這道題的關鍵就是要知道「一元二次方程的解與係數的關係」。為什麼這麼說呢？因為我們可以將這個一元二次方程分解為以下形式。
換句話說，根據 r + s = 1，rs = -1 這個條件，我們可以得出二次方程的解就是 r 和 s。
運用一元二次方程的求根公式可以得到 x 的值。
假設 r 大於 s，可得
因為 
，所以
因此，我們就能求出斐波那契數列的通項公式了，如下所示。
好了，這樣問題就告一段落了。
解答 4-1 （斐波那契數列的通項公式）