３．母関数の応用～一般項の導出

３．母関数の応用～一般項の導出

前へ　戻る　次へ

 母関数を利用した一般項の導出

前頁までは母関数の基本的な内容について触れた。ここからは例題形式で応用例をみていこう。

高校数学の知識だけで導出するなら、特性方程式を利用して$2$次方程式の解の公式から導出することになるが、母関数によれば一味違った導出が可能となる。まず答えを示しておこう。$$F_n={\displaystyle \frac{1}{\sqrt{5}}}\{{\left({\displaystyle \frac{1+\sqrt{5}}{2}}\right)}^n-{\left({\displaystyle \frac{1-\sqrt{5}}{2}}\right)}^n\}$$これを母関数を用いて導く。そのためにはまずフィボナッチ数列の母関数を求める必要がある。

$$\begin{array}{}\text{(A)}& f(x)& =F_{1}x+F_2{x}^2+F_3{x}^3+F_4{x}^4+F_5{x}^5+F_6{x}^6+\cdots \text{(B)}& xf(x)& =F_1{x}^2+F_2{x}^3+F_3{x}^4+F_4{x}^5+F_5{x}^6+\cdots \text{(C)}& x^{2}f(x)& =F_1{x}^3+F_2{x}^4+F_3{x}^5+F_4{x}^6+\cdots \end{array}$$ 漸化式より、$F_{n+2}-F_{n+1}-F_n=0$ であることを利用すると、$(\text{A})-((\text{B})+(\text{C}))$ として、$$(1-x-x^2)f(x)=x$$ $$\therefore f(x)={\displaystyle \frac{x}{1-x-x^2}}$$を得る。このままでは一般項を求められないので、これを部分分数分解する。$${\displaystyle \frac{x}{1-x-x^2}}={\displaystyle \frac{p}{1-qx}}+{\displaystyle \frac{r}{1-sx}}$$と置いて、これを恒等式として解くと$$\{\begin{array}{l}p+r=0\\ qr+ps=-1\\ q+s=1\\ qs=-1\end{array}$$を得る。これより $p={\displaystyle \frac{1}{q-s}}$、$r=-{\displaystyle \frac{1}{q-s}}$ となるから$$\begin{array}{rl}f(x)& ={\displaystyle \frac{1}{q-s}}({\displaystyle \frac{1}{1-qx}}-{\displaystyle \frac{1}{1-sx}})\\ & ={\displaystyle \frac{1}{q-s}}\{(1+qx+q^2{x}^2+\cdots )-(1+sx+s^2{x}^2+\cdots )\}\\ & ={\displaystyle \frac{q-s}{q-s}}x+{\displaystyle \frac{q^2-s^2}{q-s}}{x}^2+{\displaystyle \frac{q^3-s^3}{q-s}}{x}^3+\cdots \end{array}$$となる（ただし、途中で等比数列の和の公式を利用している）。$x^n$の係数が$F_n$であるから、これより$$F_n={\displaystyle \frac{q^n-s^n}{q-s}}$$と求められる。$q、s$は $q+s=1$、$qs=-1$ を満たすから二次方程式 $t^2-t-1=0$ の２解であり、$t={\displaystyle \frac{1\pm \sqrt{5}}{2}}$ なので代入して、$$\begin{array}{rl}{F}_n& ={\displaystyle \frac{{\left({\displaystyle \frac{1+\sqrt{5}}{2}}\right)}^n-{\left({\displaystyle \frac{1-\sqrt{5}}{2}}\right)}^n}{({\displaystyle \frac{1+\sqrt{5}}{2}}-{\displaystyle \frac{1-\sqrt{5}}{2}})}}\\ & ={\displaystyle \frac{1}{\sqrt{5}}}\{{\left({\displaystyle \frac{1+\sqrt{5}}{2}}\right)}^n-{\left({\displaystyle \frac{1-\sqrt{5}}{2}}\right)}^n\}\end{array}$$となる。

これでめでたくフィボナッチ数列の一般項を求めることができた。母関数を使えばこの他の関係式も求めることができる。例えば次のような$n$項目までのフィボナッチ数の和の公式や、畳み込みの公式も導くことができる。

フィボナッチ数の和の公式：
$\begin{array}{rl}& {\displaystyle \sum _{k=1}^n{F}_k}\\ & ={\displaystyle \frac{1}{\sqrt{5}}}\{{\left({\displaystyle \frac{1+\sqrt{5}}{2}}\right)}^{n+2}-{\displaystyle \frac{1+\sqrt{5}}{2}}-{\left({\displaystyle \frac{1-\sqrt{5}}{2}}\right)}^{n+2}+{\displaystyle \frac{1-\sqrt{5}}{2}}\}\\ & =F_{n+2}-1\end{array}$

フィボナッチ数の畳み込みの公式：
$\begin{array}{rl}& {\displaystyle \sum _{k=0}^n{F}_k{F}_{n-k}}\\ & ={\displaystyle \frac{1}{5}}(n-{\displaystyle \frac{1}{\sqrt{5}}}){\left({\displaystyle \frac{1+\sqrt{5}}{2}}\right)}^n+{\displaystyle \frac{1}{5}}(n+{\displaystyle \frac{1}{\sqrt{5}}}){\left({\displaystyle \frac{1-\sqrt{5}}{2}}\right)}^n\end{array}$

いずれも見かけはかなり厳つい式だが、母関数によれば比較的簡単に導出できる。もっとも、和の公式に関しては母関数などという「大道具」を使うまでもなく、いわゆる「望遠鏡和」(telescoping sum) の手法で瞬時に導くことができるのではあるが。

---

この関係式は言わずもがな、畳み込みの関係式である。前頁の$(1.10)$式の利用を考えよう。カタラン数の母関数$f(x)$の平方は以下のように表される。$$\{f(x){\}}^2=C_1+C_{2}x+C_3{x}^2+\cdots$$よって、$$\begin{array}{}\text{(A)}& f(x)& =C_0+C_{1}x+C_2{x}^2+C_3{x}^3+\cdots \text{(B)}& x\{f(x){\}}^2& =C_{1}x+C_2{x}^2+C_3{x}^3+\cdots \end{array}$$より、$(\text{B})-(\text{A})$ として、$$x\{f(x){\}}^2-f(x)=-1(\because C_0=1)$$二次方程式を解く要領で$$\therefore f(x)={\displaystyle \frac{1\pm \sqrt{1-4x}}{2x}}$$を得る。ここで、$f(x)={\displaystyle \frac{1+\sqrt{1-4x}}{2x}}$ とした場合、$C_0=1$ とはなり得ない（$x\to +0$ とすると$f(x)$は発散してしまう）ので、$$f(x)={\displaystyle \frac{1-\sqrt{1-4x}}{2x}}$$と分かる。分子 $\sqrt{1-4x}$ を二項展開したときの$x^{k+1}$の係数は$$\begin{array}{rl}& {\displaystyle \frac{{\displaystyle \frac{1}{2}}({\displaystyle \frac{1}{2}}-1)\cdots ({\displaystyle \frac{1}{2}}-k)}{(k+1)!}}\cdot (-4{)}^{k+1}\\ & ={\displaystyle \frac{1\cdot 1\cdot 3\cdot 5\cdots (2k-1)}{2^{k+1}(k+1)!}}\cdot (-1{)}^{2k+1}\cdot 4^{k+1}\end{array}$$となる（※$\sqrt{1-4x}=(1-4x{)}^{\frac{1}{2}}$ として拡張された二項定理を適用した）。これに ${\displaystyle \frac{2\cdot 4\cdot 6\cdots 2k}{2^{k}k!}}(=1)$ を掛けると$$\begin{array}{rl}& =-{\displaystyle \frac{(2k)!}{(k+1)!k!}}\cdot 2\\ & =-{\displaystyle \frac{2\cdot {}_{2k}{\mathrm{C}}_k}{k+1}}\end{array}$$と簡単になる。これより、母関数$f(x)$における$x^k$の係数は$$\begin{array}{rl}& {\displaystyle \frac{1}{2}}\cdot {\displaystyle \frac{2\cdot {}_{2k}{\mathrm{C}}_k}{k+1}}\\ & ={\displaystyle \frac{{}_{2k}{\mathrm{C}}_k}{k+1}}\end{array}$$となり、これは $k=0$ でも成り立つ（∵${}_0{\mathrm{C}}_0=1$ ）。よって求めるカタラン数の一般項は$$C_n={\displaystyle \frac{{}_{2n}{\mathrm{C}}_n}{n+1}}$$となる。

---

因みにカタラン数は次のような問題の場合の数として現れる。

 

 

また、カタラン数は$$C_{n+1}={\displaystyle \frac{2(2n+1)}{n+2}}{C}_n$$という漸化式を満たす。また、カタラン数の一般項は単純に場合の数による計算からも導出可能である。

 

 練習課題

以下、学習のための練習課題として幾つかの問題を提示しておこう。

---

 

---

 

---

 

---

これでも飽き足らないという人は以下の発展例題にチャレンジしてみよう。

 

---

前へ　戻る　次へ