征解问题[18] 递推数列（已解决）

某校举行百年校庆的庆典活动，在某项仪式中，要求在操场事先画好的$2\times n$的带型网格中插上小红旗，并且每个$1\times 1$的方格最多插$1$面旗，任何$2\times 2$的“田”字格中不能插满旗．以$a_n$来表示满足条件的不同的插红旗的方法数，例如，$a_1$表示在$2\times 1$的网格中插红旗所有满足要求的方法数，易知$a_1=4$．

（1）求$a_2$，$a_3$；

（2）求证：$a_n$（$n \geqslant 2\land n\in \mathcal N$）是$3$的倍数；

（3）当$n=2015$时，若$a_{2015}=3^k\cdot m$（$k,m\in\mathcal N^*$），求$k$的最大值．

---

（1）解    $a_1=4$，$a_2=15$，$a_3=57$．

（2）证明    将$a_n$种满足条件的不同的插红旗的方法分为两类： 第一类，以两面红旗结尾的，记为$b_n$种； 第二类，不以两面红旗结尾的，记为$c_n$种． 例如当$n=1$时，$a_1=4$，$b_1=1$，$c_1=3$． 这样，容易得到数列$\{b_n\}$和$\{c_n\}$的递推关系：

$$\begin{cases} b_{n+1}=c_n,\\c_{n+1}=3(b_n+c_n),\end{cases}$$ 这样，我们就得到了当$n\geqslant 2\land n\in \mathcal N^*$时，有递推关系 $$\begin{split} a_{n+1}&=b_{n+1}+c_{n+1}\\&=3b_n+4c_n\\&=3a_n+c_n\\&=3a_n+3a_{n-1}, \end{split}$$ 因此$a_n$（$n \geqslant 2\land n\in \mathcal N$）是$3$的倍数．

（3）解    考虑使用三进制解决问题：

记题中$a_n$对应的$k=[a_n]$，给出引理：

引理    对于$[\quad]$运算，若$[m]>[n]$，其中$m,n\in\mathcal N^*$，那么

$$[m+n]=[n].$$ 证明留给读者．

接下来归纳证明：当$n=2k-1$时，$[a_n]=k-1$；当$n=2k$时，$[a_n]\geqslant k$，其中$k\in\mathcal N^*$．

当$k=1$时，$[a_1]=[4]=0$，$[a_2]=[15]=1$，命题成立；

假设命题对$k$成立，则

$$[a_{2k-1}]=k-1,[a_{2k}]\geqslant k,$$ 欲证明 $$[a_{2k+1}]=k,[a_{2k+2}]\geqslant k+1.$$ 事实上，由递推关系，有 $$\begin{split} [a_{2k+1}]&=[3a_{2k}+3a_{2k-1}]\\&=[a_{2k}+a_{2k-1}]+1\\&=[a_{2k-1}]+1\\&=k, \end{split}$$ 其中用到了引理． 同时 $$\begin{split} [a_{2k+2}]&=[3a_{2k+1}+3a_{2k}]\\&=[a_{2k+1}+a_{2k}]+1\\&\geqslant k+1.\end{split}$$ 因此命题对任意正整数$k$均成立，于是$[a_{2015}]=1007$．