循环节的推导
\(\displaystyle Q_n=\sum_{k\le 2^n}{\binom{2^n-k}{k}}(-1)^k, n\in \mathbb{N^+}\)
试求 \(Q_{1000000}\) 。
观察到 \(n\) 只以 \(2^n\) 的形式出现过，设 \(m=2^n\)
\[\begin{aligned} Q_n=R_m&=\sum_{k\le m}{\binom{m-k}{k}(-1)^k}\\ &=\sum_{k\le m}{\binom{m-1-k}{k}(-1)^k}+\sum_{k\le m}{\binom{m-1-k}{k-1}(-1)^k}\\ &=\sum_{k\le m-1}{\binom{m-1-k}{k}(-1)^k}+\binom{-1}{m}(-1)^m-\sum_{k+1\le m}{\binom{m-2-k}{k}(-1)^{k}}\\ &=R_{m-1}+\binom{-1}{m}(-1)^m-\sum_{k\le m-2}{\binom{m-2-k}{k}(-1)^{k}}-\binom{-1}{m-1}(-1)^{m-1}\\ &=R_{m-1}-R_{m-2}+\binom{-1}{m}(-1)^m+\binom{-1}{m-1}(-1)^{m-1}\\ &=R_{m-1}-R_{m-2}+(-1)^{2m}+(-1)^{2(m-1)}\\ &=R_{m-1}-R_{m-2} \end{aligned} \]考察 \(R\) 的前几项的值： \(R_0=0,R_1=1,R_2=1\)
手玩可以得到：
\[\left\{ \begin{aligned} R_0 &=0\\ R_1 &=1\\ R_2 &=1\\ R_3 &=0\\ R_4 &=-1\\ R_5 &=-1\\ R_6 &= 0\\ R_7 &= 1\\ \end{aligned} \right. \]观察发现，每六个数为一个循环节。
当然，考虑更严谨的证明：
\(R_m=R_{m-1}-R_{m-2}=(R_{m-2}-R_{m-3})-R_{m-2}=-R_{m-3}=R_{m-6}\) 。
这样 \(Q_n=R_{2^n}\) 就可以很轻易的求出了。
标签：begin,le,end,二十二日,sum,九月,binom,aligned,日记 From： https://www.cnblogs.com/mklzc/p/16721440.html