練習問題

母関数 \(F(x)\) に対して、その \(x^{n}\) の係数は \([x^{n}] F(x)\) と表記される。次に示す式の中で \([x^{n}]4x G(x)\) と等しいものを全て選べ:

• \(4 [x^{n}] x G(x)\)
• \(4x [x^{n}] G(x)\)
• \([x^{n-1}] 4 G(x)\)
• \(([x^{n}] 4x) \cdot [x^{n}] G(x)\)
• \(([x] 4x) \cdot [x^{n}] x G(x)\)
• \([x^{n+1}] 4x^{2} G(x)\)

次に示す母関数の \(x^{n}\) の係数を求めよ:

花束を買おうと考えていたあなたは、ユリ、バラ、チューリップからなる花束を作成できるオンラインサービスを見つけた。それぞれの花の本数は次の条件を満たす必要があるという:

• ユリは \(1\) 本以下

• バラは \(2\) 本以上

• チューリップの本数は奇数

例えば、\(0\) 本のユリ、\(5\) 本のバラ、\(3\) 本のチューリップからなる花束は条件を満たす。

\(n\) 本の花からなる花束の選び方の個数の母関数 \(B(x)\) を多項式 (または多項式の積) の比として表せ。比を表す式を単純化する必要はない。

冪級数展開の係数の列が次の列である母関数を閉形式の式で表せ:

1. \((0,\, 0,\, 1,\, 1,\, 1,\, \ldots)\)
2. \((1,\, 0,\, 1,\, 0,\, 1,\, 0,\, 1,\, \ldots)\)
3. \((1,\, 2,\, 3,\, 4,\, 5,\, \ldots)\)
4. \((1,\, 4,\, 9,\, 16,\, 25,\, \ldots)\)
5. \((1,\, 1,\, 1/2,\, 1/6,\, 1/24,\, 1/120,\, \ldots)\)

\(\displaystyle A(x) = \sum_{n=0}^{\infty} a_{n} x^{n}\) とする。容易に分かるように次の等式が成り立つ:

ただし \(A^{(n)}\) は \(A\) の \(n\) 次導関数を表す。この事実を (証明せずに) 利用して、畳み込み則 (第 16.2.3 項) を使わずに次の等式を示せ:

ここから、bookkeeper 則 (規則 15.6.3) を知らなくても上記の計算と母関数に対する畳み込み則があれば証明できると分かる。

1. 母関数 \(S(x)\) を次のように定める:

   \[ S(x) ::= \frac{x^{2} + x}{(1 - x)^{3}} \]

   \(S(x)\) の冪級数展開の \(x^{n}\) の係数を求めよ。

2. \(S(x)/(1 - x)\) が整数の二乗和の母関数である理由を説明せよ。つまり、\(S(x)/(1 - x)\) を冪級数展開すると \(x^{n}\) の係数が \(\sum_{k=1}^{n} k^{2}\) になると示せ。

3. ここまでの結果を使って次の等式を示せ:

   \[ \sum_{k=1}^{n} k^{2} = \frac{n(n + 1)(2n + 1)}{6} \]

ペニー (\(1\) セント硬貨)、ニッケル (\(5\) セント硬貨)、ダイム (\(10\) セント硬貨)、クオーター (\(25\) セント硬貨)、ハーフダラー (\(50\) セント硬貨) が使えるとき \(n\) セントの代金を支払う方法の個数はいくつだろうか？ 母関数を使って求めてみよう。

1. ペニーだけを使って \(n\) セントの代金を支払う方法の個数の母関数 \(P(x)\) を書け。

2. ニッケルだけを使って \(n\) セントの代金を支払う方法の個数の母関数 \(N(x)\) を書け。

3. ペニーとニッケルだけを使って \(n\) セントの代金を支払う方法の個数の母関数を書け。

4. ペニー、ニッケル、ダイム、クオーター、ハーフダラーだけを使って \(n\) セントの代金を支払う方法の個数の母関数を書け。

5. \(\text{(d)}\) の解答を使って \(50\) ドルの代金を支払う方法の個数を求める方法を説明せよ。実際に求める必要はない。

第 16.2.6 項 で考えた「不条理な」数え上げ問題の解答はそれほど複雑ではなかった。この問題を数え上げの考え方を使って (母関数を使わずに) 直接解け。

様々な制約の下で \(n\) 個のドーナツを選択する異なる方法の個数の母関数を考えよう。\(\text{(a)}\)-\(\text{(e)}\) に示す制約のそれぞれについて、対応する母関数を閉形式で示せ:

1. 全てのドーナツはチョコレートであり、少なくとも \(3\) 個のドーナツを選ぶ必要がある。

2. 全てのドーナツはグレーズであり、最大でも \(2\) 個しか選べない。

3. 全てのドーナツはココナッツであり、ちょうど \(2\) 個または \(0\) 個しか選べない。

4. 全てのドーナツはプレーンであり、選ぶドーナツの個数は \(4\) の倍数である必要がある。

5. チョコレート、グレーズ、ココナッツ、プレーンのドーナツが選択できる。選択されるドーナツの個数は \(\text{(a)}\)-\(\text{(d)}\) の制約を全て満たす必要がある。

6. 最後に、全ての制約を満たすように \(4\) 種類のドーナツの中から \(n\) 個を選ぶ方法の個数を閉形式で表せ。

McGillicuddyマクギリカディ 嬢は外出するとき必ずペットを連れて行く。彼女には次のルールに従う:

• スズメは必ず連れて行く。さらに、スズメの羽数は常に偶数である。

• ワニの Freddyフレディ は連れて行くこともあれば連れて行かないこともある。

• \(2\) 匹以上のネコを連れて行く。

• 合わせて \(2\) 匹以上のチワワとプードルを紐付きの首輪で一列にして連れて行く。

このルールに従って合計 \(n\) 匹のペットを選ぶ異なる方法の個数を \(P_{n}\) とする。ただし、チワワとプードルの並び順が異なる選び方は異なるものとみなす。

例えば、\(6\) 匹のペットを選ぶ方法は次の \(4\) 通りなので、\(P_{6} = 4\) が分かる:

• スズメ \(2\) 羽、ネコ \(2\) 匹、チワワ \(2\) 匹

• スズメ \(2\) 羽、ネコ \(2\) 匹、プードル \(2\) 匹

• スズメ \(2\) 羽、ネコ \(2\) 匹、チワワ \(1\) 匹の後ろにプードル \(1\) 匹

• スズメ \(2\) 羽、ネコ \(2\) 匹、プードル \(1\) 匹の後ろにチワワ \(1\) 匹

1. McGillicuddy 嬢が \(n\) 匹のペットの選ぶ方法の個数の母関数を \(P(x)\) とする:

   \[ P(x) ::= P_{0} + P_{1} x + P_{2} x^{2} + P_{3} x^{3} + \cdots \]

   次の等式が成り立つことを確かめよ:

   \[ P(x) = \frac{4x^{6}}{(1 - x)^{2}(1 - 2x)} \]

2. \(P_{n}\) を閉形式で表せ。

超豪華なボート旅を計画している U-Pain は、何を持っていくかを考えている:

• \(1\) 個以上のハンバーガーを持っていく必要がある。お気に入りのハンバーガーは \(6\) 個セットでしか売っていないので、持っていく個数は \(6\) の倍数でなければならない。

• 彼と \(2\) 人の友人は、旅でフォーマルな服を着るべきかどうかを決めかねている。そのため、持っていくサングラスは \(0\) 個または \(3\) 個である。

• スーツケースにタオルを入れる空間は少ししかない。最大で \(2\) 枚のタオルを入れられる。

• ボート旅を真に豪華なものにするために、航海っぽい柄のパシュミナ・アフガンを \(1\) 枚以上持っていく。

1. \(n\) 個のハンバーガー、サングラス、タオル、パシュミナ・アフガンを選択する個数の母関数をそれぞれ \(B(x)\), \(F(x)\), \(T(x)\), \(A(x)\) とする。それぞれを簡単な式で表せ。

2. U-Pain がボート旅に \(n\) 個の持ち物 (ハンバーガー、サングラス、タオル、パシュミナ・アフガン) を持ち込む異なる方法の個数を \(g_{n}\) とする。その母関数 \(\sum_{n=0}^{\infty} g_{n} x^{n}\) を \(G(x)\) とするとき、次の等式が成り立つと示せ:

   \[ G(x) = \frac{x^{7}}{(1 - x)^{2}} \]

3. \(g_{n}\) を簡単な式で表せ。

Dangerousデンジャラス Danダン は危険と隣り合わせの毎日を送っている:

• Dan は朝食のシリアルをキーボードにぶちまけるかもしれない。この事故が起こるのは \(0\) 回または \(1\) 回である。

• Dan は自宅を出たとき玄関前の外階段で転ぶかもしれない。この事故が起こるのは \(0\) 回または \(1\) 回である。

• Dan は足の指をどこかにぶつけるかもしれない。この事故は \(0\) 回以上起こる可能性がある。

• Dan は口をすべらせて馬鹿なことを言うかもしれない。この事故は偶数回だけ起こる可能性がある。

Dan が一日に \(n\) 個の事故に見舞われる方法の個数を \(T_{n}\) とする。例えば、\(3\) 個の事故に見舞われる方法は次の \(7\) 通りなので \(T_{3} = 7\) が分かる:

1. 次の母関数 \(T(x)\) を多項式の比として表せ:

   \[ T(x) ::= T_{0} + T_{1} x + T_{2} x^{2} + \cdots \]

2. 次の式の空欄に正しい整数を書き入れよ:

   \[ T(x) = \frac{\boxed{\mathstrut \quad}}{1 - x} + \frac{\boxed{\mathstrut \quad}}{(1 - x)^{2}} \]

3. \(T(x)\) を閉形式で表せ。

\(b\), \(c\), \(a_{0}\), \(a_{1}\), \(a_{2}\), \(\ldots\) を次の等式を満たす実数とする:

また、無限列 \((a_{0}, a_{1}, \ldots)\) の母関数を \(G(x)\) とする。

1. \(bxG(x)\) の冪級数展開における \(x^{n}\) (\(n \geq 1\)) の係数を \(b\) と適当な \(i\) に対する \(a_{i}\) を使って表せ。

2. \(cx/(1-x)\) の冪級数展開における \(x^{n}\) (\(n \geq 1\)) の係数は何か？

3. ここまでの結果を使って、\(G(x) - bxG(x) - cx/(1 - x)\) に等しい非常に簡単な式を求めよ。

4. 部分分数分解を使うと、次の等式を満たす実数 \(d\), \(e\) を見つけられる:

   \[ G(x) = \frac{d}{L(x)} + \frac{e}{M(x)} \]

   \(L(x)\) と \(M(x)\) を答えよ。

高名な数学者 Fibonacciフィボナッチ は、未来の大学生を苦しめる新種の数列を考える研究の合間にウサギの繁殖を始めることにした。Fibonacci は (数学者として当然) \(0\) か月目に繁殖場をオープンし、\(1\) か月目に \(1\) つがいのウサギをもらい受ける。ウサギは産まれて \(1\) か月で繁殖可能になり、それからは毎月 \(1\) つがいのウサギを産むとする。ウサギと資金が不足しないように、Fibonacci は毎月の終わり (ウサギの繁殖が済んだ後) に \(3\) か月前に繁殖場にいたウサギと同数のウサギを売りに出すことにした。こうすればウサギが尽きることはないだろうと彼は考えた。

1. Fibonacci が \(n\) か月目 (ウサギの売却を済ませた後) に保有するウサギのつがいの数 \(r_{n}\) が満たす再帰方程式を示せ。つまり、\(i < n\) を満たすいくつかの \(r_{i}\) を使って \(r_{n}\) を表せ。

2. ウサギのつがいの数の母関数を \(R(x)\) とする:

   \[ R(x) ::= r_{0} + r_{1} x + r_{2} x^{2} + \cdots \]

   \(R(x)\) を多項式の比として表せ。

3. \(R(x)\) の部分分数分解を求めよ。

4. \((c)\) で求めた部分分数分解を使って、Fibonacci が \(n\) か月目に保有するウサギのつがいの数を表す閉形式の式を求めよ。

Sheboyganシボイガン の塔問題 (Tower of Sheboygan problem) は Hanoi の塔問題ほど知名度はないものの同程度に興味深い。\(3\) 個の棒と \(n\) 枚の円盤からなる装置が登場し、操作の開始時点で左端の棒に全ての円盤が積み上げられ、最も大きなものが一番下、最も小さなものが一番上になるように大きさ順に積み上がっているのは Hanoi の塔問題と同様である。また、円盤は一つずつしか移動できず、移動先の棒の一番上にある円盤は移動される円盤より大きくなければならない点も変わらない。

Sheboygan の塔問題では、全ての円盤を中央の棒に移動させることが目標となる。さらに、左端から中央、中央から右端、右端から左端にしか円盤の移動ができない制約が課される。例えば円盤を左端から右端に移動させることはできない。

1. Sheboygan の塔問題の再帰的な解答を示す: 左端の棒に積まれた \(n\) 個の円盤を右隣の (中央の) 棒に移動させるには、上から \(n - 1\) 個の円盤を再帰的に右隣に \(2\) 回移動させ、最も大きな円盤を中央の棒に移動させ、最後にまた \(n - 1\) 個の円盤を右隣に \(2\) 回移動させればよい。この手続きの実行に必要なステップ数を \(s_{n}\) とする。\(s_{n}\) が満たす簡単な線形再帰方程式を示せ。

2. 無限列 \((s_{0}, s_{1}, \ldots)\) の母関数を \(S(x)\) とする。次の等式を注意深く示せ:

   \[ S(x) = \frac{x}{(1 - x)(1 - 4x)} \]

3. \(s_{n}\) を表す簡単な式を求めよ。

4. これより優れた Sheboygan の塔問題の解答 (実際には最適だが、この問題では最適性を証明しない) を次に示す: この解答は二つの相互再帰的な手続きからなる。\(P_{1}(n)\) は \(n\) 個のリングを右隣に移動させ、\(P_{2}(n)\) は \(n\) 個のリングを左隣に (右隣への移動 \(2\) 回分) 移動させる。二つの操作は \(n = 0\) のとき自明であり、\(n > 0\) に対しては次のように定義される:

   • \(P_{1}(n)\): 上から \(n - 1\) 個の円盤を \(P_{2}(n-1)\) で左隣に移動させる。それから最も大きな円盤を右隣に移動させる。その後 \(P_{2}(n-1)\) で \(n - 1\) 個の円盤をもう一度左隣に (最も大きな円盤の上に) 移動させる。

   • \(P_{2}(n)\): 上から \(n - 1\) 個の円盤を \(P_{2}(n-1)\) で左隣に移動させ、最も大きな円盤を右隣に移動させる。それから \(P_{1}(n-1)\) で \(n - 1\) 個の円盤を右隣 (最初の位置) に移動させ、最も大きな円盤をもう一度右隣に移動させる。最後に \(P_{2}(n-1)\) で \(n - 1\) 個の円盤を左隣に (最も大きな円盤の上に) 移動させる。

   手続き \(P_{1}(n)\) の実行に必要なステップ数を \(t_{n}\) とする。\(n > 1\) に対して次の再帰方程式が成り立つと示せ:

   \[ t_{n} = 2t_{n-1} + 2t_{n-2} + 3 \tag{16.22}\]

   ヒント: \(P_{2}(n)\) の実行に必要なステップ数を \(u_{n}\) とする。\(t_{n}\) と \(u_{n}\) の両方を \(t_{n-1}\) と \(u_{n-1}\) の線形結合として表し、\(t_{n}\) について解く。

5. 次の等式を満たす \(a\), \(b\), \(c\), \(\alpha\), \(\beta\) を求めよ:

   \[ t_{n} = a \alpha^{n} + b \beta^{n} + c \]

   \(t_{n} = o(s_{n})\) と結論付けよ。

母関数の微分を取ると有用な結果が得られることが多い。微分は項ごとに実行できる。つまり

なら、次の等式が成り立つ:

例えば \(1/(1-x) = 1 + x + x^{2} + \cdots\) を微分すると次の等式が得られる:

この結果からは、非負整数を順に並べた無限列 \((0, 1, 2, \ldots)\) の母関数が次の \(H(x)\) だと分かる:

この定義を微分すれば次を得る:

よって、非負整数の二乗を並べた無限列 \((0, 1, 4, 9, \ldots)\) の母関数は次の関数である:

1. 全ての \(k \in \mathbb{N}\) に対して、非負整数の \(k\) 乗を並べた無限列の母関数が多項式の比だと示せ。つまり、任意の \(k \in \mathbb{N}\) に対して次の条件を満たす多項式 \(R_{k}(x)\) と \(S_{k}(x)\) が存在すると示せ:

   \[ [x^{n}] \left( \frac{R_{k}(x)}{S_{k}(x)} \right) = n^{k} \tag{16.23}\]

   ヒント: 多項式の比の微分が多項式の比である事実を利用する。\(R_{k}\) と \(S_{k}\) を実際に求める必要はない。

2. 非負整数上の関数 \(f(n)\) が \(a, b, c, \alpha \in \mathbb{C}\) と複素多項式 \(p\) を使って次の式で再帰的に定義されるとする:

   \[ f(n) = a f(n - 1) + bf(n - 2) + cf(n - 3) + p(n) \alpha^{n} \]

   このとき無限列 \((f(0),\, f(1),\, \ldots)\) の母関数が \(x\) の多項式の比となること、そして \(f(n)\) の閉形式の式が存在することを示せ。

   ヒント: \(\displaystyle \frac{R_{k}(\alpha x)}{S_{k}(\alpha x)}\) を考える。

母関数は括弧のバランスが取れた文字列の個数を数え上げる興味深い手段を提供する。それを説明するには、優れたカウントを持つ文字列全体の集合 \(\text{GoodCount}\) (問題 7.21) を考える必要がある。

文字列の括弧のバランスが取れているかどうかを正確に確かめる一つの方法として、カウンターを \(0\) で初期化してから文字列を一文字ずつ左から右に読み、開き括弧を読むたびにカウンターを \(1\) 増やし、閉じ括弧を読むたびにカウンターを \(1\) 減らす手続きを使う方法がある。この手続きを二つの文字列に対して実行したときのカウンターの値の変化を次に示す:

この手続き全体でカウンターの値が負にならず、かつ最後の値が \(0\) のとき、文字列は優れたカウント (good count) を持つと言うことにする。上に示した二つ目の文字列は優れたカウントを持つのに対して、一つ目の文字列はカウンターの値が負になる箇所があるので優れたカウントを持たない。また、次のように集合 \(\text{GoodCount}\) を定める:

空文字列は優れたカウントを持つと定める。つまり \(\lambda \in \text{GoodCount}\) とする。問題 7.21 で見たように、括弧のバランスの取れた文字列は優れたカウントを持つ文字列に等しい。

ちょうど \(n\) 個の開き括弧を持つ \(\text{GoodCount}\) の要素の個数を \(c_{n}\) として、無限列 \((c_{0},\, c_{1},\, \ldots)\) の母関数を \(C(x)\) とする:

1. 文字列 \(s\) のラップ (wrap) を、\(s\) を括弧で包んだ文字列 \({\color{red} \,\textbf{\textsf{[}}\,} s {\color{blue} \,\textbf{\textsf{]}}\,}\) と定義する。優れたカウントを持つ文字列のラップの個数の母関数が \(x C(x)\) である理由を説明せよ。

   ヒント: 優れたカウントを持つ文字列のラップは優れたカウントを持つ: カウントが \(0\) となるのは最初と最後だけで、それ以外の場所では常に正である。

2. 優れたカウントを持つ任意の文字列 \(s\) に対して、優れたカウントを持つ文字列のラップからなる一意な列 \(s_{1}\), \(\ldots\), \(s_{k}\) が存在して \(s = s_{1} \cdots s_{k}\) が成り立つと示せ。例えば、文字列 \(r ::= {\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{blue} \,\textbf{\textsf{]}}\,} \in \text{GoodCount}\) に対しては \(s_{1} ::= {\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}\), \(s_{2} ::= {\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}\), \(s_{3} ::= {\color{red} \,\textbf{\textsf{[}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{red} \,\textbf{\textsf{[}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}{\color{blue} \,\textbf{\textsf{]}}\,}\) と定めると \(s = s_{1} s_{2} s_{3}\) が成り立ち、優れたカウントを持つ文字列のラップの連結として \(r\) を表す方法は他に存在しない。

3. 次の等式が成り立つと結論付けよ:

   \[ C = 1 + xC + (xC)^{2} + \cdots + (xC)^{n} + \cdots \tag{i} \]

\(\text{(c)}\) の結果から

つまり

が分かる。

\(D(x) ::= 2x C(x)\) と定義する。\(D\) の冪級数展開を

とすれば、次の等式が成り立つ:

4. \(\text{(iii)}\) と \(\text{(iv)}\) を使って次の等式が成り立つと結論付けよ:

   \[ D(x) = 1 - \sqrt{1 - 4x} \]

5. 次の等式を示せ:

   \[ d_{n} = \frac{(2n - 3)(2n - 5) \cdots 5 \cdot 3 \cdot 1 \cdot 2^{n}}{n!} \]

   ヒント: \(d_{n} = D^{(n)}(0)/n!\) が成り立つ。

6. 次の等式が成り立つと結論付けよ:

   \[ c_{n} = \frac{1}{n + 1} \binom{2n}{n} \]

無限列 \((r_{0},\, r_{1}, r_{2},\, \ldots)\) を次の規則で定義する:

この無限列の母関数を \(R(x) ::= \sum_{i=0}^{\infty} r_{i} x^{i}\) とする。\(R(x)\) を多項式の比または多項式の積として表せ。\(r_{n}\) を閉形式で表す必要はない。

Alyssaアリッサ Hackerハッカー がアップロードした動画は森林火災のような速さで UToobユートゥーブ ネットワークに広まった。アップロードした日 (\(0\) 日目とする) の視聴回数は \(0\) 回だった。しかし、\(2\) 日目以降の視聴回数 \(r_{n}\) は、\(1\) 日前の視聴回数の \(7\) 倍と \(2\) 日前の視聴回数の \(4\) 倍の和に \(3\) を加えた値に増えていった。例えば \(2\) 日目の視聴回数は \(7 \times 0 + 4 \times 0 + 3 = 3\) である。

1. \(r_{n}\) が満たす再帰方程式を示せ。

2. 母関数 \(R(x) ::= \sum_{i=0}^{n} r_{i} x^{i}\) を多項式の比または多項式の積として表せ。\(r_{n}\) を閉形式で表す必要はない。

次に示す命題論理の列を考える:

\(Q_{n}(x_{1}, x_{2}, \ldots, x_{n})\) が真になる \(x_{1}\), \(x_{2}\), \(\ldots\), \(x_{n}\) に対する異なる真理値割り当ての個数を \(T_{n}\) とする。例えば、次の表から分かるように \(Q_{2}(x_{1}, x_{2})\) が真になる \(x_{1}\), \(x_{2}\) に対する異なる真理値割り当ては \(3\) 個あるので \(T_{2} = 3\) が分かる:

なお、\(T_{0} = 1\) と定める。

1. \(n \geq 0\) とする。\(T_{n + 1}\) を \(T_{n}\) と \(n\) を使って表せ。

2. 母関数を利用して、\(n \geq 1\) のとき次の等式が成り立つと示せ:

   \[ T_{n} = \frac{2^{n+1} + (-1)^{n}}{3} \]

\(3\)-Fibonacci 数 (triple Fibonacci number) \(T_{0}\), \(T_{1}\), \(\ldots\) を次の規則で定義する:

1. \(3\)-Fibonacci 数は全て \(3\) の倍数だと示せ。

2. 隣り合う \(3\)-Fibonacci 数の最大公約数は常に \(3\) だと示せ。

3. \(3\)-Fibonacci 数を並べた無限列 \((T_{0},\, T_{1},\, \ldots)\) の母関数 \(T(x)\) を多項式の比として表せ。\([x^{n}] T(x)\) を閉形式で表す必要はない。

\(2\) 倍-Fibonacci 数 (double Fibonacci number) \(D_{0}\), \(D_{1}\), \(\ldots\) を次の規則で定義する:

1. \(2\) 倍-Fibonacci 数は全て奇数だと示せ。

2. 隣り合う \(2\) 倍-Fibonacci 数は常に互いに素だと示せ。

3. \(2\) 倍-Fibonacci 数を並べた無限列 \((D_{0},\, D_{1},\, \ldots)\) の母関数 \(D(x)\) を多項式の比として表せ。\([x^{n}] D(x)\) を閉形式で表す必要はない。

形式的冪級数の文脈では、実数 \(r\) は次の無限列を表すと解釈される:

例えば、実数 \(1\) は単位級数 \(I\) (に対応する無限列) を表し、実数 \(0\) は零級数 \(Z\) (に対応する無限列) を意味する。「\(r\)」が実数と無限列のどちらを意味するかは文脈から判断される。

形式的冪級数環で次の等式が成り立つと示せ:

ここから次の等式が分かる:

形式的冪級数 \(X\) を次のように定義する:

1. \(X\) が逆数を持たない理由を説明せよ。

   ヒント: \(x \cdot (g_{0} + g_{1} x + g_{2} x^{2} + \cdots)\) に関して何が言えるか？

2. 形式的冪級数の乗算 \(\otimes\) の定義を使って、次の等式を注意深く証明せよ:

   \[ X \otimes (g_{0},\, g_{1},\, g_{2},\, \ldots) = (0,\, g_{0},\, g_{1},\, g_{2},\, \ldots) \]

3. \(n \in \mathbb{N}\) に対する \(X^{n}\) を次の規則で再帰的に定義する:

   \[ \begin{aligned} X^{0} &::= I ::= (1, 0, 0, \ldots, 0, \ldots) \\ X^{n+1} &::= X \otimes X^{n} \quad (n > 0) \end{aligned} \]

   単項式 \(x^{n}\) が \(X^{n}\) と同じ冪級数を表すことを確認せよ。

「\(G ::= (g_{0},\, g_{1},\, \ldots)\) が形式的冪級数環で乗法逆元を持つ」と「\(g_{0} \neq 0\) が成り立つ」が同値だと示せ。