形式的べき級数の逆元を使った無限和圧縮

逆元

$ A = \sum_{n=0}^\infty x^n

$ B = 1-x

この時$ A \times B = 1が成り立つ

$ A = 1 + x + x^2 + \ldots (1)

$ xA = x + x^2 + \ldots (2)

$ (1-x)A = 1 (1) - (2)

等比数列の和の計算でよくやるテクニック

一般にFが$ [x^0]F = 0 であるような定数項を持たない形式的べき級数の時、

$ (1-F) \times (\sum_{n=0}^\infty F^n) = 1

この証明には形式的べき級数環に位相を定義して、収束を定義する必要がある

【問題】Nを正の整数の和として表す方法を数え上げよ。ただし、和の順序の違いは区別する。

$ F = \sum_{n=1}^\infty x^n,$ G = \sum_{n=0}^\infty F^nとした時

$ [x^n]G が答え

Gの無限和を逆元で置き換える

$ G = \sum_{n=0}^\infty F^n = \frac{1}{1 - F}

Fの無限和も逆元で置き換える

$ F = \sum_{n=1}^\infty x^n = \sum_{n=0}^\infty x^{n+1} = x\sum_{n=0}^\infty x^n = \frac{x}{1-x}

FをGに代入する

$ G = \frac{1}{1 - F} = \frac{1}{1-\frac{x}{1-x}} = (1-x) \frac{1}{1-2x}

ここで$ 2xの部分は形式的べき級数なので無限和に戻すことができる、これをJと呼ぶことにする

$ J = \frac{1}{1-2x} = \sum_{n=0}^\infty (2x)^n

$ [x^n]J = 2^n である

ここから$ [x^n] G = [x^n](1-x)J = [x^n]J - [x^{n-1}]J = 2^n - 2^{n-1} = 2^{n-1}