小数展開にフィボナッチ数列 etc. が出てくる分数（後編）

日曜数学 Advent Calendar 2021 の2日目の記事です。

昨日の記事の後編として、小数展開に色々な数列が登場するような分数を生み出していきたいと思います！

f:id:tsujimotter:20211130182234p:plain:w480

さてここで問題です！

以下の４つの分数は、それぞれどんな数列が出てくる分数でしょうか？

$\displaystyle \frac{10000}{9799}$
$\displaystyle \frac{1010000}{999899}$
$\displaystyle \frac{2999900}{999899}$
$\displaystyle \frac{10100}{970299}$

（答えは記事の中で紹介します。）

前編の記事をまだ読んでいない方は、前編の記事をぜひご覧になってください。
tsujimotter.hatenablog.com

前回に続いて、分数の小数展開には以下のページをご活用ください！
tsujimotter.info

いろいろな数列が出てくる分数

前編で紹介したフィボナッチの母関数を使う方法は結構有名な事実です。

一方で、フィボナッチ数列でなくても、まったく同じ考え方で小数展開に登場させることができそうだと気づきました。

というわけで、やってみたいと思います！

たとえば、以下のような名前のついている数列を考えてみましょう：

ペル数列： $a_n = 2 a_{n-1} + a_{n-2}, \;\; a_0=1, \; a_1=2$
パドヴァン数列： $a_n = a_{n-2} + a_{n-3}, \;\; a_0=1, \; a_1=1, \; a_2=1$
ペラン数列： $a_n = a_{n-2} + a_{n-3}, \;\; a_0=3, \; a_1 =0, \; a_2 = 2$

それぞれの母関数は

ペル数列の母関数： $\displaystyle f_1(X) = \frac{1}{1-2X-X^2}$
パドヴァン数列の母関数： $\displaystyle f_2(X) = \frac{1+X}{1-X^2-X^3}$
ペラン数列の母関数： $\displaystyle f_3(X) = \frac{3-X^2}{1-X^2-X^3}$

となります。

フィボナッチ数列のときと同様に、これらの母関数に $X = 1/100$ を入れてみましょう。

ペル数列の場合は

$\displaystyle f_1(1/100) = \frac{1}{1 - 2\cdot \frac{1}{100} - \left(\frac{1}{100}\right)^2} = \frac{10000}{10000 - 200 - 1} = \frac{10000}{9799} \tag{19}$

となります。（分母分子に10000をかけるのがポイントですね。）

これを展開すると

$\require{color} \displaystyle \frac{10000}{9799} = {\color[rgb]{1.0,0.0,0.2}1.02051229}7173\ldots \tag{20}$

となります。これで、ペル数列の

$a_0 = {\color[rgb]{1.0,0.0,0.2}1}, \; a_1 = {\color[rgb]{1.0,0.0,0.2}2}, \; a_2 = {\color[rgb]{1.0,0.0,0.2}5}, \; a_3 = {\color[rgb]{1.0,0.0,0.2}12}, \; a_4 = {\color[rgb]{1.0,0.0,0.2}29} \tag{21}$

が復元できたことになりますね！

ほかもまったく同様です。

パドヴァン数列の場合は

$\displaystyle f_2(1/100) = \frac{1 + \frac{1}{100}}{1 - \left(\frac{1}{100}\right)^2 - \left(\frac{1}{100}\right)^3} = \frac{100^3 + 100^2}{100^3 - 100 - 1} = \frac{1010000}{999899} \tag{22}$

となります。展開すると

$\displaystyle \frac{1010000}{999899} = {\color[rgb]{1.0,0.0,0.2} 1.01010202030405070912162128374965}8715\ldots \tag{22}$

となります。これで、パドヴァン数列の

${\color[rgb]{1.0,0.0,0.2}1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65}$

までが復元できます。

ペラン数列の場合は

$\displaystyle f_3(1/100) = \frac{3 - \left(\frac{1}{100}\right)^2}{1 - \cdot \left(\frac{1}{100}\right)^2 - \left(\frac{1}{100}\right)^3} = \frac{3\cdot 100^3 - 100}{100^3 - 100 - 1} = \frac{2999900}{999899} \tag{23}$

となります。展開すると

$\displaystyle \frac{2999900}{999899} = {\color[rgb]{1.0,0.0,0.2} 3.000203020505071012172229395168}9120\ldots \tag{24}$

となります。これで、ペラン数列の

${\color[rgb]{1.0,0.0,0.2}3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68}$

までが復元できます。

いやー、面白いですね！！

このセクションでは、漸化式

$a_n = 2 a_{n-1} + a_{n-2}$ （ペル数列）
$a_n = a_{n-2} + a_{n-3}$ （パドヴァン数列・ペラン数列）

で表されるような数列について、母関数が $X$ についての有理式で表せることを示しました。

より一般には、次のような事実が知られているそうです。

事実：
「ある数列の通常型母関数が有理式で表されるための必要十分条件は、その数列が線型漸化式を持つことである」
（引用元：２．数列と母関数 | 理系のための備忘録）

つまり、線型漸化式を持つ数列を考えれば、原理的には $X$ の有理式で表すことができ、 $X$ に $10^{-n}$ を代入することで所望の分数が得られるというわけですね。

平方数が出てくる分数

もう一つ、母関数を作るのにちょっとしたテクニックが必要なものについて考えてみましょう。

ここでは

$a_n = n^2$

という、平方数の数列について考えてみたいと思います。

すなわち

$\displaystyle \sum_{n=0}^\infty n^2 X^n = 0 + X + 4X^2 + 9X^3 + 16X^4 + \cdots \tag{24}$

という母関数について、閉じた式を求めてみたいと思います。

いったいどうやって考えたらよいでしょうか？

これを求めるには少しテクニックが必要です。よろしければ少し考えてみてください。

それでは求め方に行きたいと思います。

まず、最も基本的な $a_n = 1$ の母関数

$\displaystyle \sum_{n=0}^{\infty} X^n = \frac{1}{1-X} \tag{25}$

から始めます。

この両辺を2乗することを考えたいと思います。つまり

$\displaystyle \left(\sum_{n=0}^{\infty} X^n\right)^2 = \frac{1}{(1-X)^2} \tag{26}$

を考えるわけですね。右辺は良いとして、左辺を展開するとどんな式になるでしょうか。

つまり

$\displaystyle \left(\sum_{n=0}^{\infty} X^n\right) \times \left(\sum_{n=0}^{\infty} X^n\right) \tag{27}$

という母関数の積を考えたいわけですね。

次数が小さい方から確定していきましょう。

定数項は、第1因子と第2因子からそれぞれ $X^0$ を取り出してかければ良いので、係数は $1$ になります。

$X^1$ の係数は

第1因子から $X^0$ 、第2因子から $X^1$ を取り出してかけた $X^0 X^1$
第1因子から $X^1$ 、第2因子から $X^0$ を取り出してかけた $X^1 X^0$

を取り出して足し合わせれば良いので、 $X^0 X^1 + X^1 X^0 = 2X$ となり、係数は $2$ となります。

$X^2$ の係数は

第1因子から $X^0$ 、第2因子から $X^2$ を取り出してかけた $X^0 X^2$
第1因子から $X^1$ 、第2因子から $X^1$ を取り出してかけた $X^1 X^1$
第1因子から $X^2$ 、第2因子から $X^0$ を取り出してかけた $X^2 X^0$

を取り出して足し合わせれば良いので、 $X^0 X^2 + X^1 X^1 + X^2 X^0 = 3X^2$ となり、係数は $3$ となります。

同様に、 $X^n$ の係数は $(n+1)$ になるので、以下の式が得られるというわけですね。

$\displaystyle \sum_{n=0}^{\infty} (n+1) X^n = \frac{1}{(1-X)^2} \tag{28}$

係数の $n+1$ ですが、これは「 $0, 1, 2, \ldots, n$ という $n+1$ 個の中から、1個の数を選ぶ場合の数」ということになります。

続いて、式 $(25)$ の基本的な母関数を、今度は3乗してみましょう。

この場合は

$\displaystyle \left(\sum_{n=0}^{\infty} X^n\right) \times \left(\sum_{n=0}^{\infty} X^n\right)\times \left(\sum_{n=0}^{\infty} X^n\right) = \frac{1}{(1-X)^3} \tag{29}$

となるわけですが、左辺の展開が問題です。

一気に $X^n$ の係数を考えたいと思います。これはつまり、第1因子から $X^a$ 、第2因子から $X^b$ 、第3因子から $X^c$ を

$a+b+c = n$ （ $0\leq a, b, c \leq n$ ）

となるように選ぶ場合の数に相当します。 $a, b$ の2つが決まると、 $c$ は自動的に決まってしまいますので、これは $n+1$ 個の中から2個選ぶ重複組合せになりますね。

これは ${}_{n+2} \operatorname{C}_{2}$ ということになります。したがって

$\displaystyle \sum_{n=0}^{\infty} {}_{n+2} \operatorname{C}_{2} X^n = \frac{1}{(1-X)^3} \tag{30}$

が得られました。二項係数を具体的に計算すると

$\displaystyle {}_{n+2} \operatorname{C}_{2} = \frac{(n+2)(n+1)}{2} = \frac{n^2 + 3n + 2}{2}$

なので

$\displaystyle \sum_{n=0}^{\infty} \frac{n^2 + 3n + 2}{2} X^n = \frac{1}{(1-X)^3} \tag{31}$

となります。

以上の議論により

$\displaystyle F(X) = \sum_{n=0}^{\infty} X^n = \frac{1}{1-X} \tag{25再掲}$

$\displaystyle G(X) = \sum_{n=0}^{\infty} (n+1) X^n = \frac{1}{(1-X)^2} \tag{28再掲}$

$\displaystyle H(X) = \sum_{n=0}^{\infty} \frac{n^2 + 3n + 2}{2} X^n = \frac{1}{(1-X)^3} \tag{31再掲}$

なる基本的な母関数が得られました。

あとは、係数が $n^2$ になるように適当に定数倍して足し引きすれば良いわけです。

実際

$\displaystyle 2H(X) - 3G(X) + F(X) = \sum_{n=0}^{\infty} \left\{(n^2 + 3n + 2) - (3n+3) + 1 \right\} X^n = \sum_{n=0}^{\infty} n^2 X^n \tag{32}$

となり、これが平方数の数列の母関数ということになります。

あとは、 $F(X), G(X), H(X)$ の閉じた式を使って

$\displaystyle \begin{align} \sum_{n=0}^{\infty} n^2 X^n &= 2H(X) - 3G(X) + F(X) \\ &= \frac{2}{(1-X)^3} - \frac{3}{(1-X)^2} + \frac{1}{1-X} \\ &= \frac{2 - 3(1-X) + (1-X)^2}{(1-X)^3} \\ &= \frac{X+X^2}{(1-X)^3} \end{align} \tag{33}$

となり、これにて平方数の数列の母関数の閉じた式が得られました！

最後に、 $X = 1/100$ を入れると

$\displaystyle \frac{\frac{1}{100}+\left(\frac{1}{100}\right)^2}{\left(1-\frac{1}{100}\right)^3} = \frac{100^2 + 100}{(100-1)^3} = \frac{10100}{970299} \tag{34}$

となり、これが平方数を生み出す分数になります。

実際、

$\displaystyle \frac{10100}{970299} = {\color[rgb]{1.0,0.0,0.2} 0.0104091625364964}8201\ldots \tag{35}$

となります。これで、平方数を

${\color[rgb]{1.0,0.0,0.2}0, 1, 4, 9, 16, 25, 36, 49, 64}$

まで復元できたことになります。面白いですね！！

微分を使った母関数の求め方

上では、平方数の数列の母関数を組合せ論的に考えました。実は、微分を使ってもう少しスマートに実行することもできます。

まず、基本的な母関数

$\displaystyle \sum_{n=0}^{\infty} X^n = \frac{1}{1-X} \tag{25再掲}$

からはじめます。

この両辺を $X$ で微分してみましょう。

$\displaystyle \sum_{n=1}^{\infty} n X^{n-1} = \frac{1}{(1-X)^2} \tag{36}$

両辺に $X$ をかけると

$\displaystyle \sum_{n=1}^{\infty} n X^{n} = \frac{X}{(1-X)^2} \tag{37}$

が得られて、これは数列 $a_n = n$ の母関数となります。

さらにこれを $X$ で微分すると

$\displaystyle \begin{align} \sum_{n=1}^{\infty} n^2 X^{n-1} &= \frac{(1-X)^2 + 2X(1-X)}{(1-X)^4} \\ &= \frac{(1 - 2X + X^2) + 2X - 2X^2)}{(1-X)^4} \\ &= \frac{1 - X^2)}{(1-X)^4} \\ &= \frac{(1 - X)(1 + X)}{(1-X)^4} \\ &= \frac{1 + X}{(1-X)^3} \end{align} \tag{38}$