- 追加された行はこの色です。
- 削除された行はこの色です。
%indent
* 設問 [#t8f3168d]
////////////////////////////////////////////////////////////////
前提条件として、以下のように指数関数と対数関数を設定する：
#ceq(e)
$$ f(x) $ \equiv $ - \log $ (1-x) $$
#ceq(e)
$$ g(y) $ \equiv $ \exp $ y $$
#ceq(end)
;,$$ h(x) $ \equiv $ g\big(f(x)\big) $$とすると、指数計算により$$ \log $$と$$ \exp $$が打消し、簡単な式になる：
#ceq(e)
$$ h(x) = $ \exp $ \Big({-\log} (1-x) \Big) $ = $ \exp $ \Big( \log (1-x)^{-1} \Big) $ = $ \cancel{\exp\!\mathstrut} $ \cancel{\log\!\mathstrut} $ \ffd{1}{1-x} $$
;, $$ = $ \ffd{1}{1-x} $$
#ceq(end)
;,$$ \ffd{1}{1-x} $$をデーラー展開すると、係数が全て１の級数が得られる。
#ceq(e)
$$ h(x) = $ \sum_{k=0}^{\infty} $ x^k $$
#ceq(a)
;,ただし、成立するためには、収束条件$$ |x| < 1 $$が課される
#ceq(end)
;,一方で、$$ f(x) $$と$$ g(y) $$を級数展開しても$$ h(x) $$の級数展開が求まる：
#ceq(e)
$$ f(x) $ = $ -\log $ (1-x) $ = $ -\log $ \Big(1+(-x)\Big) $$
;, $$ = $ \cancel{-} $ \sum_{n=0}^{\infty} $ \ffd{(\cancel{-}1)^{n+1}}{n} $ (\cancel{-}x)^n $$
;, $$ = $ \sum_{n=0}^{\infty} $ \ffd{1}{n} $ x^n $$
#ceq(a)
;,一般に、
;,$$ \log(1+x) $ = $ \sum_{n=0}^{\infty} $ \ffd{(-1)^{n+1}}{n} $ x^n $$
;,ただし、成立するためには、
;,収束条件$$ |x| < 1 $$が課される
#ceq(e)
;,$$ g(y) $ = $ \exp $ y $$
;, $$ = $ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ y^m $$
#ceq(a)
;,一般に、
;,$$ \exp $ x $ = $ \sum_{n=0}^{\infty} $ \ffd{1}{n!} $ x^n $$
#ceq(end)
;,$$ f(x) $$を$$ g(y) $$に代入して：
#ceq(e)
$$ h(x) $ = $ g\big(f(x)\big) $ = $ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \Big(f(x)\Big)^m $$
;, $$ = $ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \bigg( $ \sum_{n=0}^{\infty} $ \ffd{1}{n} $ x^n $ \bigg)^m $$
#ceq(end)
;,よって、上で求めた$$ h(x) $ = $ \ffd{1}{1-x} $$と合わせて、次の等式が成り立つことになる。
#ceq(e)
$$ \sum_{k=0}^{\infty} $ x^k $ = $ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \bigg( $ \sum_{n=0}^{\infty} $ \ffd{1}{n} $ x^n $ \bigg)^m $$
#ceq(end)
;,ここで係数比較をすると、任意の$$ k $ = $ n $ + $ m $$について$$ x^k $$の係数が１でなければならない結論に至る。
;,この関係式は指数・対数、そしてテーラー展開を経由しているが、単なる級数展開でも導けるはず。
;,しかし、無限級数の入子が含まれているため、簡単には導けない。
;,したがって、問題：
#ceq(e)
指数・対数を経由せずに$$ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \bigg( $ \sum_{n=0}^{\infty} $ \ffd{1}{n} $ x^n $ \bigg)^m $$の係数が全て１であることを証明せよ
#ceq(end)
%bodynote
* 展開 [#u4d4f4cf]
////////////////////////////////////////////////////////////////
;,問題は係数の証明であるため、$$ x^k $$を作るべく、$$ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \bigg( $ \sum_{n=0}^{\infty} $ \ffd{1}{n} $ x^n $ \bigg)^m $$を展開する。
;,雰囲気を掴めるため、とりあえず具体的な数値で展開してみる。
#ceq(e)
$$ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \bigg( $ \sum_{n=0}^{\infty} $ \ffd{1}{n} $ x^n $ \bigg)^m $$
;,$$ = $ \ffd{1}{1!} $ \bigg( $ \ffd{x^1}{1} + \ffd{x^2}{2} + \ffd{x^3}{3} + \cdots $ \bigg)^1 $$
;,$$ + $ \ffd{1}{2!} $ \bigg( $ \ffd{x^1}{1} + \ffd{x^2}{2} + \ffd{x^3}{3} + \cdots $ \bigg)^2 $$
;,$$ + $ \ffd{1}{3!} $ \bigg( $ \ffd{x^1}{1} + \ffd{x^2}{2} + \ffd{x^3}{3} + \cdots $ \bigg)^3 $$
;,$$ + $ \ffd{1}{4!} $ \bigg( $ \ffd{x^1}{1} + \ffd{x^2}{2} + \ffd{x^3}{3} + \cdots $ \bigg)^4 $$
;,$$ + $ \ffd{1}{5!} $ \bigg( $ \ffd{x^1}{1} + \ffd{x^2}{2} + \ffd{x^3}{3} + \cdots $ \bigg)^5 $$
;,$$ + $ \cdots $$
#ceq(end)
$$ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \bigg(\sum_{n=0}^{\infty} $ \ffd{1}{n} x^n \bigg)^m $$について、
$$ \bigg(\sum_{n=0}^{\infty} $ \ffd{1}{n} x^n \bigg)^m $$の部分は$$ n $$次多項式の$$ m $$乗展開を意味する。
;,このため、直接多項式展開の記述$$ \sum_{k=0}^{\infty} $ \prod_{\{i | \sum_i n_i = k\}}^m \!\!\!\ffd{1}{n_{i_j}} x^k $$に置き換えできる。
;,$$ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \bigg(\sum_{n=0}^{\infty} $ \ffd{1}{n} x^n \bigg)^m $$
$$ = $$
$$ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \bigg( $ \sum_{k = 0}^{\infty} $ \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} $ \bigg) $ x^k $$
$$ = $$
$$ \sum_{k=0}^{\infty} $ \bigg( $ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} $ \bigg) $ x^k $$
;,$$ x^k $$の係数を抜き出すと、任意の$$ k $$について以下の式が成り立つ。
#ceq(e)
$$ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} $ = $ 1 $$
#ceq(end)
;,式中の総乗$$ \prod_{\{i | \sum n_i = k\}}^m $$の条件式は、正整数範囲で$$ k $$について$$ [n_i] $$に加数分解を行う意味である。
;,総乗の上限$$ m $$は、加数分解結果より$$ n_i $$項数が決まり、$$ i $$の上限である$$ m $$が逆に制限されることを意味する。
;,例えば、具体的に$$ k = 4 $$の場合、$$ 4 $$を以下のように加数分解を行い、$$ n_i $$と$$ m $$を決まる：
|*l:表１： $$ k = 4 $$の場合の加数分解|<|<|h
|l: |l=:l: | |c
|*加数分解 |*$$ [n_i] $$|*$$ m $ = $ \dim[n_i] $$|t=:
|*$$ 4 = 4 $$| $$ [4] $$| $$ 1 $$|t=:
|*$$ 4 = 3 + 1 $$| $$ [3, 1] $$| $$ 2 $$|
|*$$ 4 = 2 + 2 $$| $$ [2, 2] $$| $$ 2 $$|
|*$$ 4 = 2 + 1 + 1 $$| $$ [1, 1, 1] $$| $$ 3 $$|
|*$$ 4 = 1 + 3 $$| $$ [1, 3] $$| $$ 2 $$|
|*$$ 4 = 1 + 2 + 1 $$| $$ [1, 2, 1] $$| $$ 3 $$|
|*$$ 4 = 1 + 1 + 2 $$| $$ [1, 1, 2] $$| $$ 3 $$|
|*$$ 4 = 1 + 1 + 1 + 1 $$| $$ [1, 1, 1, 1] $$| $$ 4 $$|
;,ところが、この総乗も厄介なもので先に進めない。
;,そこで、総乗を回避するべく、$$ k $$についての漸化式を見いだして数学的帰納法を使う方法を検討してみる。
////////////////////////////////////////////////////////////////
* 帰納法のための漸化式 [#yd2a839e]
** 冪の漸化式 [#p9ea733a]
;,これまでの調べで、項の数が正整数範囲での$$ k $$の加数分解のパターン数であると分かった。
;,このため、項の数、および、漸化式作りに適する項の順番を次の発想で決められる。
;,例えば$$ k = 4 $$の場合、冪$$ x^4 $$は４つの$$ x $$の積を意味する。
#ceq(e)
$$ x $ \cdot $ x $ \cdot $ x $ \cdot $ x $$
#ceq(end)
;,ここで、４の加数分解は、$$ x $$のグルーピングと解釈できる。
;,図形的に見ると、上式の「$$ \cdot $$」に任意に仕切り「$$ | $$」を入れる操作と等価である。
;,それぞれの「$$ \cdot $$」について「$$ | $$」を「入れる」または「入れない」の２択であるため、
;,３ヵ所で$$ 2^3 = 8 $$通り出来て、表１の８つの項に対応する。
;,一般化すると、$$ k $$個の$$ x $$の間という$$ k-1 $$ヶ所に「$$ | $$」を入れることになるため、
;,全部で$$ 2^{k-1} $$個の項が出来る。
;,また、先頭の$$ x $$を除き、「$$ \cdot x $$」を「$$ 0 $$」に、「$$ | x $$」を「$$ 1 $$」に符号化すると、
;,$$ k = 4 $$の場合、$$ x $$に続く３桁の２進数が現れる。それも８通り＝３桁の２進数の全部が出揃う。
|*l:表２： $$ x^k $$の符号化|<|<|<|h
|l: |l=:l: | | |c
|*加数分解 |*$$ [n_i] $$|*$$ x $$分割表現 |*２進数字列表現|t=:
|*$$ 4 = 4 $$| $$ [4] $$| $$ x $ \cdot $ x $ \cdot $ x $ \cdot $ x $$| $$ x000 $$ |t=:
|*$$ 4 = 3 + 1 $$| $$ [3, 1] $$| $$ x $ \cdot $ x $ \cdot $ x $ \pipe $ x $$| $$ x001 $$ |
|*$$ 4 = 2 + 2 $$| $$ [2, 2] $$| $$ x $ \cdot $ x $ \pipe $ x $ \cdot $ x $$| $$ x010 $$ |
|*$$ 4 = 2 + 1 + 1 $$| $$ [2, 1, 1] $$| $$ x $ \cdot $ x $ \pipe $ x $ \pipe $ x $$| $$ x011 $$ |
|*$$ 4 = 1 + 3 $$| $$ [1, 3] $$| $$ x $ \pipe $ x $ \cdot $ x $ \cdot $ x $$| $$ x100 $$ |
|*$$ 4 = 1 + 2 + 1 $$| $$ [1, 2, 1] $$| $$ x $ \pipe $ x $ \cdot $ x $ \pipe $ x $$| $$ x101 $$ |
|*$$ 4 = 1 + 1 + 2 $$| $$ [1, 1, 2] $$| $$ x $ \pipe $ x $ \pipe $ x $ \cdot $ x $$| $$ x110 $$ |
|*$$ 4 = 1 + 1 + 1 + 1 $$| $$ [1, 1, 1, 1] $$| $$ x $ \pipe $ x $ \pipe $ x $ \pipe $ x $$| $$ x111 $$ |
;,$$ k $$は２進数の桁数に対応するため、$$ k $$から$$ k + 1 $$に進めることは、１桁増やすことを意味する。
;,２進数であるため、１桁増やすことは末尾に「$$ 0 $$」か「$$ 1 $$」を付けることになる。
;,この規則を利用すると、$$ k $$桁の数字列から$$ k+1 $$桁の数字列を過不足無く作り出せる。
|*l:表３： 漸化式的な$$ x^k $$|<|<|<|<|<|<|<|<|h
| |l=:c: |l3px#EEE:c: |l3px#EEE:c: |l3px#EEE:c: |l3px#EEE:c: |l3px#EEE:c: |l3px#EEE:c: |l3px#EEE:c: |c
|*$$ k = 1 $$|$$ x $$|< |< |< |< |< |< |< |t=:
|*$$ k = 2 $$|$$ x $ \cdot $ x $$|< |< |< |$$ $ x $ \pipe $ x $$|< |< |< |
|*$$ k = 3 $$|$$ x $ \cdot $ x $ \cdot $ x $$|< |$$ x $ \cdot $ x $ \pipe $ x $$|< |$$ $ x $ \pipe $ x $ \cdot $ x $$|< |$$ x $ \pipe $ x $ \pipe $ x $$|< |
|*$$ k = 4 $$|$$ x $ \cdot $ x $ \cdot $ x $ \cdot $ x $$|$$ x $ \cdot $ x $ \cdot $ x $ \pipe $ x $$|$$ x $ \cdot $ x $ \pipe $ x $ \cdot $ x $$|$$ $ x $ \cdot $ x $ \pipe $ x $ \pipe $ x $$|$$ $ x $ \pipe $ x $ \cdot $ x $ \cdot $ x $$|$$ x $ \cdot $ x $ \cdot $ x $ \pipe $ x $$|$$ x $ \pipe $ x $ \pipe $ x $ \cdot x $$|$$ x $ \pipe $ x $ \pipe $ x $ \pipe $ x $$|
|*$$ \cdots $$|$$ \cdots \cdots $$|< |< |< |< |< |< |< |
;,これから、$$ k = c $$のとき、$$ m $$分割される$$ [n_i] $$について考え、漸化式を作る。
;,$$ [n_i] $ = $ [n_1, n_2, \cdots, n_m] $$とおくと、$$ k = c+1 $$について対応する次の２項を作り出せる：
#ceq(e)
$$ [n_{i;0}] $ = $ [n_1, n_2, \cdots, n_m \iro[ak]{+} 1] $$ （$$ m $$分割のまま）
#ceq(e)
$$ [n_{i;1}] $ = $ [n_1, n_2, \cdots, n_m\ \iro[ak]{,}\ 1] $$ （$$ m+1 $$分割に増える）
#ceq(end)
%bodynote
////////////////////////////////////////////////////////////////
** 係数の漸化式 [#z18dd70a]
;,「係数の抽出」の節で得られた結果より、$$ x^k $$の係数は$$ \sum_{m=1}^{\infty} $ \ffd{1}{m!} $ \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} $$。
;,「冪の漸化式」の節で得られた結果より、$$ x^k $$となる項は全部で$$ 2^k $$個現れる。
;,このため、総和記号$$ \sum_{m=1}^{\infty} $$の上限は実際$$ 2^k $$で止まり
(($$ h(x) $$の無限級数では、元々外に$$ \sum_{k=0}^{\infty} $$が付いており、$$ k $ \to $ \infty $ \Rightarrow $ 2^k $ \to $ \infty $$になるため辻褄は合っている。))、
$$ x^k $$の係数は$$ \sum_{m=1}^{2^k} $ \ffd{1}{m!} $ \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} $$になる。
;,さらに、総和記号$$ \sum_{m=1}^{2^k} $$を落とすと、
$$ [n_i] $ = $ [n_1, n_2, \cdots, n_m] $$のように分割される$$ x^k $$の係数$$ a_{[n_i]} $$が得られる：
#ceq(e)
$$ a_{[n_i]} $ = $ \ffd{1}{m!} $ \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} $$
#ceq(end)
同様に、$$ [n_i] $$に対応する$$ k + 1 $$次の係数は以下のようになる。
#ceq(e)
$$ [n_{i;0}] $ = $ [n_1, n_2, \cdots, n_{\iro[ak]{m-1}}, \iro[ak]{n_m + 1}] $$： $$ a_{[n_{i;0}]} $ = $ \ffd{1}{(m\iro[ao]{+0})!} $ \bigg( \prod_{\{i | \sum_i n_i = k\}}^{\iro[ak]{m-1}} \!\!\!\ffd{1}{n_i} \bigg) $ \cdot $ \ffd{1}{\iro[ak]{n_m + 1}} $$
#ceq(e)
$$ [n_{i;1}] $ = $ [n_1, n_2, \cdots, n_{ m-1} , n_m\ ,\ \iro[ak]{1}] $$： $$ a_{[n_{i;1}]} $ = $ \ffd{1}{(m\iro[ao]{+1})!} $ \bigg( \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} \bigg) $ \cdot $ \ffd{1}{\iro[ak]{ 1}} $$
#ceq(end)
;,共に分母分子を調節して、$$ [n_i] $$を作り出すと係数の漸近式になる：
#ceq(e)
$$ a_{[n_i]} $ = $ \ffd{1}{m!} $ \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} $$
#ceq(e)
$$ a_{[n_{i;0}]} $ = $ \cancelto{a_{[n_i]}}{\ffd{1}{m!} \bigg( \prod_{\{i | \sum_i n_i = k\}}^{m-1} \!\!\!\ffd{1}{n_i} \bigg) \cdot \ffd{1}{\iro[ao]{n_m}}} \;\; \cdot \ffd{\iro[ao]{n_m}}{n_m + 1} $$
#ceq(c)
$$ = $ \ffd{n_m}{n_m + 1} a_{[n_i]} $$
#ceq(e)
$$ a_{[n_{i;1}]} $ = $ \ffd{1}{\iro[ao]{m+1}} $ \cdot $ \cancelto{a_{[n_i]}}{\ffd{1}{\iro[ao]{m!}} \bigg( \prod_{\{i | \sum_i n_i = k\}}^{m} \!\!\!\ffd{1}{n_i} \bigg)}\;\;\;\;\;\;\;\, $$
#ceq(c)
$$ = $ \ffd{1}{m + 1} a_{[n_i]} $$
#ceq(end)
%bodynote
////////////////////////////////////////////////////////////////
** 最終漸化式 [#l7b6b35d]
////////////////////////////////////////////////////////////////
* 数学的帰納法 [#b76698d7]
** k = 1 [#s7c4b4ed]
** k = c + 1 [#q4b478b1]
** 結論 [#d584ccd8]
%bodynote
////////////////////////////////////////////////////////////////
* まとめ [#k28935fc]
%bodynote
![[PukiWiki]](image/NekoPunch.png "[PukiWiki]")
