【母関数マスター講座 第12回】漸化式を母関数で解き伏せる〜フィボナッチ数列の一般項〜

第3部（第8回〜第11回）では、等比級数・負の二項定理・微分という計算道具を揃えました。

今回からの第4部では、それらの道具を使って「漸化式」を母関数で解くテクニックに挑みます。題材は、フィボナッチ数列です。

母関数マスター講座の全体像、シラバスは以下の記事でご覧ください。

https://note.com/goukalize/n/ne5f45c351ab2

LINE追加でまとめPDF配布中！
ㅤ
公式LINEを追加して「母関数マスター講座」と送信していただいた方に、講座全体をまとめたPDF（全63ページ）を無料でお配りしています。
ㅤ
自動送信のため、送信文は 「母関数マスター講座」 と正確にお送りください。
ㅤ
https://line.me/R/ti/p/@965ezfgt?oat_content=url

1. フィボナッチ数列と母関数の出会い

フィボナッチ数列を次のように定義します。

$$
\begin{aligned}
f_0 = 0, \quad f_1 = 1, \quad f_n = f_{n-1} + f_{n-2} \quad (n \geq 2) \tag{①}
\end{aligned}
$$

最初のいくつかの項は $${0, 1, 1, 2, 3, 5, 8, 13, 21, \dots}$$ です。この数列の一般項を求めたい。教科書的には特性方程式を使いますが、母関数なら漸化式をまるごと「代数の計算」に変換して解けます。

2. 母関数を定義して漸化式を翻訳する

フィボナッチ数列の母関数を次のように定義します。

$$
\begin{aligned}
F(x) = \sum_{n=0}^{\infty} f_n x^n = f_0 + f_1 x + f_2 x^2 + f_3 x^3 + \cdots \tag{②}
\end{aligned}
$$

漸化式 $${f_n = f_{n-1} + f_{n-2}}$$ を母関数の言葉に翻訳するために、 $${xF(x)}$$ と $${x^2 F(x)}$$ を作ります。

$${xF(x) = f_0 x + f_1 x^2 + f_2 x^3 + \cdots}$$ は、各 $${f_n}$$ の添字を「1つずらした」ものです。同様に $${x^2 F(x)}$$ は「2つずらした」ものになります。

漸化式 $${f_n = f_{n-1} + f_{n-2}}$$ の両辺に $${x^n}$$ を掛けて $${n = 2}$$ から $${n = \infty}$$ まで足し合わせると、

$$
\begin{aligned}
F(x) - f_0 - f_1 x = x(F(x) - f_0) + x^2 F(x) \tag{③}
\end{aligned}
$$

$${f_0 = 0, f_1 = 1}$$ を代入して整理します。

$$
\begin{aligned}
F(x) - x &= xF(x) + x^2 F(x) \\
F(x)(1 - x - x^2) &= x \\
F(x) &= \frac{x}{1 - x - x^2} \tag{④}
\end{aligned}
$$

④のように、漸化式が「 $${F(x)}$$ についての方程式」に変わり、母関数の閉じた形が求まりました。

3. 部分分数分解で一般項を読み取る

$${1 - x - x^2 = 0}$$ の解は $${x = \frac{-1 \pm \sqrt{5}}{2}}$$ です。ここで $${\alpha = \frac{1+\sqrt{5}}{2}}$$ 、 $${\beta = \frac{1-\sqrt{5}}{2}}$$ と置くと、 $${1 - x - x^2 = -(x - \frac{1}{\alpha})(x - \frac{1}{\beta}) \cdot \alpha\beta}$$ と因数分解できます。 $${\alpha\beta = -1}$$ なので、

$$
\begin{aligned}
1 - x - x^2 = (1 - \alpha x)(1 - \beta x) \tag{⑤}
\end{aligned}
$$

したがって④は、

$$
\begin{aligned}
F(x) = \frac{x}{(1 - \alpha x)(1 - \beta x)} \tag{⑥}
\end{aligned}
$$

⑥を部分分数分解します。

$$
\begin{aligned}
F(x) = \frac{1}{\alpha - \beta} \left( \frac{1}{1 - \alpha x} - \frac{1}{1 - \beta x} \right) \tag{⑦}
\end{aligned}
$$

⑦の各分数は等比級数の公式（第8回）で展開できます。

$$
\begin{aligned}
\frac{1}{1 - \alpha x} = \sum_{n=0}^{\infty} \alpha^n x^n, \quad \frac{1}{1 - \beta x} = \sum_{n=0}^{\infty} \beta^n x^n \tag{⑧}
\end{aligned}
$$

⑦⑧を組み合わせると、 $${x^n}$$ の係数が $${f_n}$$ ですから、

$$
\begin{aligned}
f_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} \tag{⑨}
\end{aligned}
$$

⑨がフィボナッチ数列の一般項（ビネの公式）です。漸化式を母関数に翻訳し、分数式にして、部分分数分解で等比級数に戻す。この一連の流れが、母関数で漸化式を解く基本パターンです。

まとめ

母関数を使えば、漸化式は $${F(x)}$$ についての代数方程式に変わります。閉じた形を求め、部分分数分解し、等比級数で展開する。この手順は、3項間漸化式に限らず、さらに複雑な漸化式にも応用できます。

次回、第13回では医学部入試で頻出の「確率の連立漸化式」に母関数で挑みます。

【無料相談受付中】医学部・獣医学部受験対策はゴウカライズにおまかせを！

「一般入試の勉強だけでも大変なのに、面接や小論文までどう準備すればいいかわからない…」
「医学部や獣医学部のような専門性の高い入試に、本当に今の対策で足りるのか不安…」

そんな悩みをお持ちの受験生・保護者の皆様、医学部・獣医学部専門塾 ゴウカライズにご相談ください！

医学部受験・獣医学部受験は、学科試験だけでなく、面接、小論文、志望理由書など学部特有の対策が必要になる入試です。
ゴウカライズでは、それぞれの志望校や受験方式に合わせて、合格に必要なすべてをトータルサポートします。

【一般入試】完全オーダーメイドの学習計画 ：
医学部・獣医学部の一般入試は、わずかな失点が合否を分けることもあります。
あなたの現状と志望校の出題傾向を分析し、合格ラインに到達するための最短ルートを設計します。
日々の進捗管理で、学習の遅れも見逃さず、適宜ルートを最適に修正します。

【推薦・総合型選抜】面接・小論文もプロが対応 ：
推薦入試や総合型選抜で必須となる「面接・小論文・志望理由書」の対策もお任せください。
医学部・獣医学部特有のテーマに対応できるプロ講師が、合格レベルの答案作成と受け答えを指導します。

プロ講師・優秀学生講師の個別指導 ：
学習管理だけでなく、経験豊富なプロ講師や、高倍率から選抜された優秀な学生講師による完全個別指導も提供。
苦手科目の克服や過去問解説など、あなたのニーズに合わせた1対1の指導が可能です。

【医学部・獣医学部対策】特殊な対策に完全対応 ：
医学部入試、獣医学部入試は、どちらも特殊な対策が必要です。
面接などがある入試形式の場合、学科試験以外の準備も侮れません。
そんな入試に精通したプロがゴウカライズには多数在籍しています。
ゴウカライズ代表の大北も医学部・獣医学部受験の指導経験は15年を超える大ベテランです。

まずは無料相談で、あなたの合格までのロードマップを一緒に描きませんか？
無理な勧誘は一切ありません。
予備校選びに迷っているなどの相談でも、客観的にアドバイスを行います。

公式LINEでいつでも無料相談を受け付けています！

https://goukalize.com/

https://line.me/R/ti/p/@965ezfgt?oat_content=url

#医学部専門予備校 #入試数学 #大学受験 #オンライン塾