3.母関数の応用~一般項の導出


3.母関数の応用~一般項の導出

前へ 戻る 次へ


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

 《例題1》
$$F_1=F_2=1,\ F_{n+2}=F_{n+1}+F_{n} \ (n \geqq 0)$$で定まるフィボナッチ数列の一般項を求めよ。

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

$$\begin{align}
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 \tag{A}\\
xf(x)&=\ \ \ \ \ \ \ \ \ \ \ F_1 x^2+F_2 x^3+F_3 x^4+F_4 x^5+F_5 x^6+\cdots \tag{B}\\
x^2 f(x)&=\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ F_1 x^3+F_2 x^4+F_3 x^5+F_4 x^6+\cdots \tag{C} \end{align}$$ 漸化式より、$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)=\color{red}{\dfrac{x}{1-x-x^2}}$$を得る。このままでは一般項を求められないので、これを部分分数分解する。$$\dfrac{x}{1-x-x^2}=\dfrac{p}{1-qx}+\dfrac{r}{1-sx}$$と置いて、これを恒等式として解くと$$\begin{cases} p+r=0 \\ qr+ps=-1 \\ q+s=1 \\ qs=-1 \end{cases}$$を得る。これより $p=\dfrac{1}{q-s}$、$r=-\dfrac{1}{q-s}$ となるから$$\begin{align}f(x)&=\dfrac{1}{q-s}\left(\dfrac{1}{1-qx}-\dfrac{1}{1-sx}\right) \\ &=\dfrac{1}{q-s}\{(1+qx+q^2 x^2+\cdots)-(1+sx+s^2 x^2+\cdots)\} \\ &=\dfrac{q-s}{q-s}x+\dfrac{q^2-s^2}{q-s}x^2+\dfrac{q^3-s^3}{q-s}x^3+\cdots \end{align}$$となる(ただし、途中で等比数列の和の公式を利用している)。$x^n$の係数が$F_n$であるから、これより$$F_n=\dfrac{q^n-s^n}{q-s}$$と求められる。$q、s$は $q+s=1$、$qs=-1$ を満たすから二次方程式 $t^2-t-1=0$ の2解であり、$t=\dfrac{1 \pm \sqrt{5}}{2}$ なので代入して、$$\begin{align} F_n&=\dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\left(\dfrac{1+\sqrt{5}}{2}-\dfrac{1-\sqrt{5}}{2}\right)} \\ &=\color{red}{\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}} \end{align}$$となる。

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

フィボナッチ数の和の公式
$\begin{align}&\ \ \ \ \ \displaystyle \sum_{k=1}^{n} F_k \\ &=\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+2}-\dfrac{1+\sqrt{5}}{2}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+2}+\dfrac{1-\sqrt{5}}{2}\right\} \\ &=F_{n+2}-1 \end{align}$

フィボナッチ数の畳み込みの公式
$\begin{align}&\ \ \ \ \ \displaystyle \sum_{k=0}^{n} F_k F_{n-k} \\ &=\dfrac{1}{5}\left(n-\dfrac{1}{\sqrt{5}}\right)\left(\dfrac{1+\sqrt{5}}{2}\right)^n+\dfrac{1}{5}\left(n+\dfrac{1}{\sqrt{5}}\right)\left(\dfrac{1-\sqrt{5}}{2}\right)^n \end{align}$

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


 《例題2》
$$C_0=C_1=1,C_{n+1}=\displaystyle \sum_{k=0}^{n} C_k C_{n-k} \ (n \geqq 1)$$で定まるカタラン数$C_n$の一般項を求めよ。

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


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

(問題)

裏表の出る確率が同様に確からしい硬貨を用いてコイントスゲームをする。プレイヤーの最初の持ち点を$1$点として、硬貨が表なら$1$点を加算、裏なら1点を減点し、持ち点が$0$になった時点でゲームを終了する。$2n+1$ 回のコイントスでゲームがちょうど終了するとき、硬貨の表裏の出方の総数を求めよ。

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

 

●   ●   ●   ●   ●

 

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


《練習課題1》
$$L_0=2,L_1=1,\ L_{n+2}=L_{n+1}+L_{n} \ (n \geqq 0)$$で定まるリュカ数列の一般項を母関数から求めよ。

» 母関数はこちら

$L_{n}$の母関数は $\color{red}{f(x)=\dfrac{2-x}{1-x-x^2}}$ である。

» 閉じる

» 一般項はこちら

リュカ数列の一般項は $\color{red}{L_n=\left(\dfrac{1+\sqrt{5}}{2}\right)^n+\left(\dfrac{1-\sqrt{5}}{2}\right)^n}$ で与えられる。

式の形を見て分かる通り、リュカ数はフィボナッチ数との関係が深いことが理解できる。それもそのはずで、リュカ数という数列はフランスの数学者であるエドゥアール・リュカ(François Édouard Anatole Lucas(1842~1891))がフィボナッチ数列を考察する際に導入した数列である。

» 閉じる

 


《練習課題2》
$$\dfrac{(1+x)^3}{(1-x)^5}$$を母関数に持つ数列$a_n$の一般項を求めよ。

» 一般項はこちら

$a_n$の一般項は $\color{red}{a_n=\dfrac{1}{3}(n^2+2n+3)(n+1)^2}$ である。

» 閉じる

 


《練習課題3》
$$S_n=1^2+2^2+3^2+\cdots+n^2 \ (n \geqq 1)$$で定まる数列$S_n$の第$n$項目までの和$\displaystyle \sum_{k=1}^{n} S_k$を$T_n$とするとき、数列$T_n$の一般項を母関数から求めよ。

» 母関数はこちら

$T_n$の母関数は $\color{red}{f(x)=\dfrac{x(1+x)}{(1-x)^5}}$ である。

» 閉じる

» 一般項はこちら

一般項は $\color{red}{T_n=\dfrac{1}{12}n(n+1)^2 (n+2)}$ である。

» 閉じる

 


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

《発展例題》
$$P_0=3, P_1=0,P_2=2,P_n=P_{n−2}+P_{n−3} \ (n \geqq 3)$$で定まるペラン数列の一般項を求めよ。

» 母関数はこちら

母関数は $\color{red}{f(x)=\dfrac{3-x^2}{1-x^2-x^3}}$ である。

» 閉じる

» 一般項はこちら

3次方程式 $x^3-x-1=0$ の3解のうち$p$を実数解、$q、r$を共役複素数解とするとき、ペラン数列の一般項は$$\color{red}{P_n=p^n+q^n+r^n}$$で与えられる。この実数解$p$は特に「プラスチック数」と呼ばれ、$$\begin{align} p&=\sqrt[3]{\dfrac{1}{2}+\dfrac{\sqrt{69}}{18}}+\sqrt[3]{\dfrac{1}{2}-\dfrac{\sqrt{69}}{18}} \\ &=1.3247179572447… \end{align}$$という値をもつ。

» 閉じる

 


前へ 戻る 次へ