递推方法及其应用（递推方法在计数中的应用之三）

递推方法及其应用（递推方法在计数中的应用之三）证明4：(下标全部变为偶数再用特征方程)证明3：(用特征方程)由上证得①式，且有a1=a2=1，a3=2，a4=4，证明1：(找规律)利用①及初始值可以得到下表：可找到规律：证明2：(找规律)先用归纳法证明下式成立：

今天继续讲解递推方法在竞赛中的应用，看相关的几个数学联赛试题：

1、设an是下述自然数N的个数：N的各位数字之和为n且每位数字只能取1、3或4．

求证：a2n是完全平方数．这里，n=1，2，…．（1991年全国高中数学联赛二试第三题）

思路分析：本题很显然是用递推的思路，递推公式也不难得到。本题难点在于如何证明结果，要么求出通项公式，要么列举发现规律，用数学归纳法证明。当然不难发现本题与斐波那契数列有着深刻的联系，最近几乎必须转化为斐波那契数列的性质去解决。下面展示五种解法：

证明1：(找规律)利用①及初始值可以得到下表：

可找到规律：

证明2：(找规律)先用归纳法证明下式成立：

证明3：(用特征方程)由上证得①式，且有a1=a2=1，a3=2，a4=4，

证明4：(下标全部变为偶数再用特征方程)

证明5：(变形、转化为斐波那契数列的性质)

注：本题是当年联赛的压轴题，难度颇高。想到了递推方法后递推公式不难得到。难点在于如何证明偶数项为完全平方数。五种证法各有千秋，证法一、二相当于列举很多项发现规律，然后用数学归纳法证明。是大智若愚、大巧若拙的办法。难点在于如何发现规律，需要列举很多项，直到找到规律为止。证法三、四都是利用特征方程。不过一个四次、一个三次，计算量还是挺大的。证法五算是折中的一种办法，先通过变形转化为斐波那契数列。把递推公式由四阶简化为二阶。后面应该问题不大，除了上述累加以外，还可以考虑待定系数等方法。当然本题解决的关键是发现其与斐波那契数列的关系。本质上本题是斐波那契数学的性质。

注：本题是1998年联赛试题的压轴题，是我当年的题目，我没有做出来。据说此题国内做出来的人应该不多。但是此题确实是一个难得的好题，综合了很多的代数知识数列、函数、不等式，而且还有明显的数论和组合的味道。当然解决本题最核心的思想就是递推，最关键的步骤就是飞跃——得到一般化的结果。

下面两题也是某两年联赛的：

4、在一个正六边形的六个区域栽种观赏植物（如图），要求同一块中种同一种植物，相邻的两块种不同的植物．现有4种不同的植物可供选择，则有 种栽种方案．（2001年全国高中数学联赛第12题）

5、某情报站有A、B、C、D四种互不相同的密码，每周使用其中的一种密码，且每周都是从上周未使用的三种密码中等可能地随机选用一种．第一周使用A种密码，那么第7周也使用A种密码的概率是______ （2012年全国高中数学联赛第8题）

提示：显然两题都是第二篇第一题经典问题的变形，不难用递推或者直接带入公式得到答案。分别是 732与61/243。本文略去.

最后两题再次说明了深入而准确理解经典模型的重要性，所谓“无可奈何花落去、似曾相识燕归来”，许多联赛题目往往是经典模型的变式或加深，掌握好常见模型，就不难将其转化为经典模型，从而迅速准确的解决问题。