二項係数の問題を解く！

与式は、次の多項式の$x^{(3の倍数)}$の係数の和である.
$$(x+1)^n = {}_n \mathrm{ C }_0 + {}_n \mathrm{ C }_1 x + {}_n \mathrm{ C }_2 x^2 + \cdots {}_n \mathrm{ C }_n x^n$$

さてこの式を$f(x)$としよう.
$1$の$3$乗根のうち$1$でないものの一つを$\omega$とする。
この$\omega$には次のような性質がある

\begin{eqnarray} \omega^3 = 1 &\implies& \omega^3 - 1 = 0\\ &\implies& (\omega -1)(\omega ^2 +\omega + 1) = 0\\ &\implies& \omega^2 + \omega + 1 = 0 \quad (\because \omega \neq 1) \end{eqnarray}

さて、これを踏まえて次の値を考えてみよう
$$f(\omega) + f(\omega^2) + f(\omega^3)$$
とりあえず、筆算をしてみると
\begin{array}{} &&{}_n \mathrm{ C }_0 + {}_n \mathrm{ C }_1 \omega + {}_n \mathrm{ C }_2 \omega^2 +{}_n \mathrm{ C }_3 \omega^3+{}_n \mathrm{ C }_4 \omega^4 +\cdots+ {}_n \mathrm{ C }_n \omega^n \\ &&{}_n \mathrm{ C }_0 + {}_n \mathrm{ C }_1 \omega^2 + {}_n \mathrm{ C }_2 \omega^4 +{}_n \mathrm{ C }_3 \omega^6+{}_n \mathrm{ C }_4 \omega^8 +\cdots +{}_n \mathrm{ C }_n \omega^{2n} \\+\large{)}&&{}_n \mathrm{ C }_0 + {}_n \mathrm{ C }_1 \omega^3 + {}_n \mathrm{ C }_2 \omega^6 +{}_n \mathrm{ C }_3 \omega^9+{}_n \mathrm{ C }_4 \omega^{12} +\cdots +{}_n \mathrm{ C }_n \omega^{3n} \\\hline &&{}_n \mathrm{ C }_0 \cdot 3+0+0+{}_n \mathrm{ C }_3\cdot3+0+\cdots+{}_n \mathrm{ C }_n\cdot 3 \end{array}

$(\omega^k = \omega^{kを3で割ったあまり}に注意せよ)$
となり、${}_n \mathrm{ C }_{(3の倍数)}$の部分だけが出てきてくれる！

それぞれ$3$倍されているので、最終的に$3$で割れば目標の式が得られますね

$$ (与式) = \large{f(\omega) + f(\omega^2) + f(\omega^3) \over 3} $$

では、$f(\omega) , f(\omega^2) , f(\omega^3)$それぞれの値を求めていきましょう。

\begin{eqnarray} f(\omega^3) &=& f(1)\\ &=&(1+1)^n\\ &=&2^n \end{eqnarray}

\begin{eqnarray} f(\omega) &=& (\omega +1)^n\\ &=& (-\omega^2)^n 　\cdots (*)\\ &=& 1 \end{eqnarray}

\begin{eqnarray} f(\omega^2) &=& (\omega^2 +1)^n\\ &=& (-\omega)^n　\cdots (*)\\ &=& 1 \end{eqnarray}

$((*)では　\omega^2 + \omega + 1 = 0を変形させて使った)$
よって、
\begin{eqnarray} f(\omega) + f(\omega^2) + f(\omega^3) \over 3 &=& 1+1+2^n \over 3\\ &=& \huge{2+2^n \over 3} \end{eqnarray}