已知有穷数列{an}共有m项（m≥3，m∈N*），对于每个i（i=1，2，3，…，m）均有ai∈{1，2，3}，且首项a1与末项am不相等，同时任意相邻两项不相等．记符合上述条件的所有数列{an}的个数为f（m）

Question

已知有穷数列{a_n}共有m项（m≥3，m∈N^*），对于每个i（i=1，2，3，…，m）均有a_i∈{1，2，3}，且首项a₁与末项a_m不相等，同时任意相邻两项不相等．记符合上述条件的所有数列{a_n}的个数为f（m）．
（1）写出f（3），f（4）的值；
（2）写出f（m）的表达式，并说明理由．

Answer 1

（1）f（3）=3×2×1=6，
f（4）=3×2×2+3×3×1×1=18种，
（2）f（m）=2^m+2•（-1）^m，（*）
理由如下：当m=3时，f（3）=6，符合（*）式，
①假设当m=k时，（*）成立，即f（k）=2^k+2•（-1）^k，
那么m=k+1时，
因为a₁有3种取法，a₂有2种取法，…，a_k有2种取法，a_k+1若仅与a_k不同，则有2种取法，
一种与a₁数不同，符合要求，有f（k+1）个，
一种与a₁数相同，不符合要求，当相当与k项有穷数列的个数，有f（k）个，则有3×2^k=f（k+1）+f（k），
∴a_k+1=-a_k+3×2^k=-2^k-2（-1）^k+3×2^k=2^k+1+2（-1）^k+1，
即n=k+1时，（*）也成立，
由①②可知，（*）成立．