roots of unity filter

hbghlyj

参见Roots of Unity (Ray Li)、Finite Fourier analysis
计算 $\sum_{n=0}^{\infty} \frac{x^{2n}}{(2n)!}$
$$\frac{e^x+e^{-x}}2=\sum_{n=0}^\infty\frac{1^n+(-1)^n}2\cdot\frac{x^n}{n!}=\sum_{n=0}^{\infty} \frac{x^{2n}}{(2n)!}$$
计算 $\sum_{n=0}^{\infty} \frac{x^{3n}}{(3n)!}$
$$\frac{e^x+e^{ωx}+e^{ω^2x}}3=\sum_{n=0}^\infty\frac{1^n+ω^n+(ω^2)^n}3\cdot\frac{x^n}{n!}=\sum_{n=0}^\infty\frac{x^{3n}}{(3n)!}$$
其中 $ω=\cos (2\pi/3)+i\sin (2\pi/3)$. MSE

---

计算 $\sum_{n=0}^\infty \frac {x^{5n}} {(5n)!}$ MSE
Clearly
$$
\frac{1}{5}\sum_{j=1}^5\mathrm{e}^{\omega^j x}=\sum_{n=0}^\infty\frac{x^{5n}}{(5n)!}
$$
where $\omega=\mathrm{e}^{2\pi i/5}$, since
$$
\sum_{j=1}^5 \omega^{jn}=\left\{\begin{array}{ccc} 5&\text{if}& 5\mid n, \\ 0&\text{if} &5\not\mid n. \end{array}\right.
$$
But
$$
\omega=\cos (2\pi/5)+i\sin (2\pi/5), \,\,\omega^2=\cos (4\pi/5)+i\sin (4\pi/5),
\,\,\omega^3=\overline{\omega^2},\,\,\omega^4=\overline{\omega},
$$
and so
$$
\sum_{n=0}^\infty\frac{x^{5n}}{(5n)!}=\frac{1}{5}\sum_{j=1}^5\mathrm{e}^{\omega^j x}=\frac{1}{5}\left(\mathrm{e}^x+2\mathrm{e}^{x\cos(2\pi/5)}\cos\big(\sin(2\pi/5)\big)+2\mathrm{e}^{x\cos(4\pi/5)}\cos\big(\sin(4\pi/5)\big)\right).
$$

hbghlyj

Things Fourier - Power Overwhelming - Evan Chen 2016/06/03
计算$\displaystyle \binom{1000}{0} + \binom{1000}{3} + \dots + \binom{1000}{999}$.
We can consider the function
$$w : \mathbb Z/3 \rightarrow \mathbb C.$$
such that $w(0) = 1$ but $w(1) = w(2) = 0$. By abuse of notation we will also think of $w$ as a function $w : \mathbb Z \twoheadrightarrow \mathbb Z/3 \rightarrow \mathbb C$. Then the sum in question is
\begin{aligned} \sum_n \binom{1000}{n} w(n) &= \sum_n \binom{1000}{n} \sum_{k=0,1,2} \widehat w(k) \omega^{kn} \\ &= \sum_{k=0,1,2} \widehat w(k) \sum_n \binom{1000}{n} \omega^{kn} \\ &= \sum_{k=0,1,2} \widehat w(k) (1+\omega^k)^n. \end{aligned}In our situation, we have $\widehat w(0) = \widehat w(1) = \widehat w(2) = \frac13$, and we have evaluated the desired sum. More generally, we can take any periodic weight $w$ and use Fourier analysis in order to interchange the order of summation.

hbghlyj

TravorLZH的回答
In general, it is possible for us to extract components of power series by playing with roots of unity. Particularly, let's say
$$
f(z)=\sum_{n=0}^\infty c_nz^n
$$
converges absolutely for some $z\in\mathbb C$. If we set $\zeta=e^{2\pi i/q}$ then
$$
\frac1q\sum_{r=0}^{q-1}\zeta^{-ra}f(\zeta^rz)=\sum_{k=0}^\infty c_{qk+a}z^{qk+a}\tag1
$$
Consequently, we get
$$
\sum_{k=0}^\infty{z^{3k+1}\over(3k+1)!}=\frac13\sum_{r=0}^2 e^{-2\pi ir/3}\exp(e^{2\pi ir/3}z)
$$
Proof for (1):

Given $f$ converges absolutely at $z$, we can plug in the power series expansion for $f(z)$ to get
\begin{aligned}
\sum_{r=0}^{q-1}\zeta^{-ra}\sum_{n=0}^\infty c_n\zeta^{rn}z^n
&=\sum_{n=0}^\infty c_nz^{n}\left(\sum_{r=0}^{q-1}\zeta^{r(n-a)}\right)
\end{aligned}If $n\equiv0\pmod q$, then
$$
\sum_{r=0}^{q-1}\zeta^{r(n-a)}=\sum_{r=0}^{q-1}1=q
$$
Otherwise we have $\zeta^{n-a}\ne1$:
$$
\sum_{r=0}^{q-1}\zeta^{r(n-a)}={\zeta^{q(n-a)}-1\over\zeta^{n-a}-1}=0
$$
Consequently, the purpose of sum of roots of unity in (1) is to extract coefficients from power series.

kuing

与《撸题集》P.796~798 题目 5.6.38 思路类似。