有一种如下构造的密码锁：在正 $n$ 边形 $A_1A_2\cdots A_n$ 的每个顶点处选择一个数字 $0$ 或 $1$，并将它染上红或蓝的颜色，要求任何相邻两个顶点数字相同或颜色相同（可以同时相同），求可行的密码的个数．
【难度】
【出处】
无
【标注】
【答案】
当 $n$ 为奇数时，可行密码数为 $3^n+1$，当 $n$ 为偶数时，可行密码数为 $3^n+3$
【解析】
设 $n$ 边形对应的密码个数为 $a_n$，为解决递推中的困难，引入辅助量 $\{b_n\}$，$b_n$ 是使得 $A_1$ 与 $A_n$ 颜色，数字均不相同的方法，则$$a_n+b_n=4\cdot 3^{n-1},$$考虑 $n+1$ 个顶点，对 $A_1$ 与 $A_n$ 的情况讨论
情形一 $A_1,A_n$ 完全相同，$A_{n+1}$ 有 $3$ 种，$3a_{n-1}$（将 $A_1,A_n$ 合并为一块）；
情形二 $A_1,A_n$ 恰有一个相同，$A_{n+1}$ 有 $2$ 种，$2(a_n-a_{n-1})$；
情形三 $A_1,A_n$ 全不相同，$A_{n+1}$ 有 $2$ 种，$2b_n$．
故$$\begin{split} a_{n+1}&=3a_{n-1}+2(a_n-a_{n-1})+2b_n\\&=2(a_n+b_n)+a_{n-1}\\&=8\cdot 3^{n-1}+a_{n-1},\end{split}$$分奇偶递推可知$$a_n=\begin{cases} 3^n+1,2\nmid n,\\
3^n+3,2\mid n. \end{cases}$$
故$$\begin{split} a_{n+1}&=3a_{n-1}+2(a_n-a_{n-1})+2b_n\\&=2(a_n+b_n)+a_{n-1}\\&=8\cdot 3^{n-1}+a_{n-1},\end{split}$$分奇偶递推可知$$a_n=\begin{cases} 3^n+1,2\nmid n,\\
3^n+3,2\mid n. \end{cases}$$
答案
解析
备注
