[数列] 染色&递推数列

hbghlyj

将一个$2\times n$个方格组成的带形的某些方格染色，使得其中任何$2\times2$的四个方格都没有全染，以$P_n$来记所有满足要求的染色方案数，求证$P_{1989}$为3的倍数并$P_{1989}$所含3的次幂

2019-11-2 22:35

（如果有坛友配一下解答图就好了，我不懂技术，这是用系统自带的画图工具作的，略显简陋）
思路
记$a_n$为最后一列全染的方案数，$b_n$为最后一列不全染的方案数，$a_n$所计每个方案的最后一列有1种可能，倒数第二列不能全染，故$a_n=b_{n-1}$.$b_n$所计每个方案的最后一列有$2\times2-1=3$种可能，由于最后一列和倒数第二列的四个方格不会全染，前n-1列的染色方案等于$P_{n-1}$，故$a_n=b_n=3P_{n-1}$，代入$P_n=a_n+b_n$得$P_n=3(P_{n-1}+P_{n-2})$
现在转化为一个递推数列问题
$P_n=3(P_{n-1}+P_{n-2})，P_2=15,P_3=9+48=57$，求证$P_{1989}$为3的倍数并$P_{1989}$所含3的次幂

1. IntegerExponent[LinearRecurrence[{3, 3}, {15, 57}, 100], 3]
   
2. {1, 1, 3, 2, 3, 3, 4, 4, 6, 5, 6, 6, 7, 7, 10, 8, 9, 9, 10, 10, 12, \
   
3. 11, 12, 12, 13, 13, 15, 14, 15, 15, 16, 16, 19, 17, 18, 18, 19, 19, \
   
4. 21, 20, 21, 21, 22, 22, 24, 23, 24, 24, 25, 25, 29, 26, 27, 27, 28, \
   
5. 28, 30, 29, 30, 30, 31, 31, 33, 32, 33, 33, 34, 34, 37, 35, 36, 36, \
   
6. 37, 37, 39, 38, 39, 39, 40, 40, 42, 41, 42, 42, 43, 43, 46, 44, 45, \
   
7. 45, 46, 46, 48, 47, 48, 48, 49, 49, 51, 50}

复制代码

如果将奇数项,偶数项分开，就看出规律了：

1. First[Multicolumn[IntegerExponent[LinearRecurrence[{3,3}, {15, 57}, 100], 3], {2,Automatic}]]

复制代码

输出
{{1, 3, 3, 4, 6, 6, 7, 10, 9, 10, 12, 12, 13, 15, 15, 16, 19, 18, 19, 21, 21, 22, 24, 24, 25, 29, 27, 28, 30, 30, 31, 33, 33, 34, 37, 36, 37, 39, 39, 40, 42, 42, 43, 46, 45, 46, 48, 48, 49, 51},
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}}
奇数项$P_{2n+1}$含3的次幂为n（偶数项没发现什么规律，请高手指教）
这个规律容易用归纳法证明：$P_{2n+3}=3P_{2n+2}+3P_{2n+1},P_{2n+2}=3P_{2n+1}+3P_{2n},P_{2n+1}=3P_{2n}+3P_{2n-1}$,从以上三式消去两个偶次项得$P_{2n+3}=15P_{2n+1}-9P_{2n-1}$(这是不够的,因为$15P_{2n+1},9P_{2n-1}$由归纳假设含3的次幂都为n+1),以n-1代n,$P_{2n+1}=15P_{2n-1}-9P_{2n-3}$,消去$P_{2n+1}$,$P_{2n+3}=216P_{2n-1}-135P_{2n-3}$,因为$216P_{2n-1}$含3的次幂为n-1+3=n+2,$135P_{2n-3}$含3的次幂为n-2+3=n+1,所以$P_{2n+3}$含3的次幂为n+1，由归纳原理命题对一切正整数n成立
所以本题答案为$\frac{1989-1}2=994$

hbghlyj

希望此贴不沉。。重复一遍问题：
如何证明$a_n-n$等于n+1含3的次幂？

2019-11-4 22:40

hbghlyj

$P_{2n}$含3的次幂记为$a_n$，$a_n$ - n：
= 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0
n含3的次幂记为$b_n$，$b_n$：
0, <0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0>, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 4, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1