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

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

• 多項式・形式的べき級数（２）式変形による解法の導出 | maspyのHPの一節を自分に理解できるところまで噛み砕いたもの

• 逆元

  • $A={\sum }_{n=0}^{\infty }{x}^n$
  • $B=1-x$
  • この時$A\times B=1$が成り立つ
    • $A=1+x+x^2+\dots$ (1)
    • $xA=x+x^2+\dots$ (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}$