Roots of unity filterというテクニック
はじめに
Roots of unity filterは級数を求める際、母関数の係数の和を1の原始乗根を使って求めるテクニックです。
Roots派とRoot派がいるんですがRootsで統合、日本語の記事が見当たらなかったので作ってみました。
すごく短い記事なってしまったので、後で追記をする可能性が微レ存
Roots of unity filter
$n$を正整数とし、$\omega_n = e^{\frac{2\pi i}{n}}$を1の原始$n$乗根とする。
このとき、多項式$f(x) = \sum_{k=0}^{m} a_k x^k$に対して、 $$\sum_{k \equiv r \pmod{n}} a_k = \frac{1}{n}\sum_{j=0}^{n-1} f(\omega_n^j) \cdot \omega_n^{-jr}$$
多項式$f(x) = \sum_{k=0}^{m} a_k x^k$に対して、
$$\sum_{j=0}^{n-1} f(\omega^j) \cdot \omega^{-jr} = \sum_{j=0}^{n-1} \left(\sum_{k=0}^{m} a_k \omega^{jk}\right) \omega^{-jr} = \sum_{j=0}^{n-1} \sum_{k=0}^{m} a_k \omega^{j(k-r)} = \sum_{k=0}^{m} a_k \sum_{j=0}^{n-1} \omega^{j(k-r)}$$
ここで、$\sum_{j=0}^{n-1} \omega^{j(k-r)}$は$k \equiv r \pmod{n}$のときのみ$n$となり、それ以外は$0$となる。したがって、
$$\sum_{k=0}^{m} a_k \sum_{j=0}^{n-1} \omega^{j(k-r)} = n \sum_{k \equiv r \pmod{n}} a_k$$
両辺を$n$で割ると、
$$\sum_{k \equiv r \pmod{n}} a_k = \frac{1}{n}\sum_{j=0}^{n-1} f(\omega^j) \cdot \omega^{-jr}$$
問題
$(x+1)^{12}$の$x$の次数が$3$の倍数の項の係数の合計を求めよ
$f(x)=(x+1)^{12},\ n=3$とすると
$$\frac{1}{3} \sum_{k=0}^2 f(\omega_3^k) = \frac{1}{3}(4096+1+1) = 1366$$
$$\sum_{n=0}^\infty \frac{1}{(6n)!!} = \frac{\sqrt{e}}{3} + \frac{2}{3 \sqrt[4]{e}} \cos \theta, \quad \text{where } 0 \le \theta \le \pi.$$
$f(x) = e^{\frac{x}{2}} =\sum_{n=0}^\infty \frac{x}{2^n n!},\ n=3$とすると
$$\sum_{k=0}^\infty \frac{1}{(6k)!!} = \frac{1}{3} \sum_{j=0}^2 f(\omega_3^j) = \frac{1}{3}(e^{\frac{1}{2}} + e^{\frac{\omega}{2}} + e^{\frac{\omega^2}{2}}) = \frac{\sqrt{e}}{3} + \frac{1}{3} e^{-\frac{1}{4}}(e^{\frac{\sqrt{3}}{4}i} + e^{-\frac{\sqrt{3}}{4}i}) = \frac{\sqrt{e}}{3} + \frac{2}{3 \sqrt[4]{e}} \cos ({\frac{\sqrt{3}}{4}})$$
よって$\theta = {\frac{\sqrt{3}}{4}}$
この記事を高評価した人
この記事に送られたバッジ
投稿者
