式子

化简下面的式子

$$\frac{\sum_{i=0}^{n}\binom{n}{i} [(n-2i)\%3=0] }{2^n}$$

只需计算分式上面的。

根据单位根反演

$$\frac{1}{n} \sum_{i=0}^{n-1} \omega^{ij} = [n|j]$$

有

$$[3 | (n-2i)] = \frac{1}{3} (1 + \omega_3^{n-2i} + \omega_3^{2(n-2i)})$$

分开计算

$$\sum_{i=0}^{n} \binom{n}{i} = 2^n$$ $$\begin{aligned} \sum_{i=0}^{n} \binom{n}{i} \omega_3^{n-2i} &= \omega_3^{n} \sum_{i=0}^{n} \binom{n}{i} (\frac{1}{\omega_3^2})^i \\ &= \omega_3^{n}(1+\frac{1}{\omega_3^2})^n \\ &= (\omega_3 + \frac{1}{\omega_3})^n \end{aligned}$$

根据单位根的性质，有 $\omega_3^3=1,1 + \omega_3 + \omega_3^2 = 0$，那么

$$(\omega_3 + \frac{1}{\omega_3})^n = (\omega_3+\omega_3^2)^n = (-1)^n$$

同理

$$\sum_{i=0}^{n} \binom{n}{i} \omega_3^{2(n-2i)} = (-1)^n$$

那么

$$\frac{\sum_{i=0}^{n}\binom{n}{i} [(n-2i)\%3=0] }{2^n} = \frac{2^n + 2 \times (-1)^n}{3 \times 2^n}$$