前两个问题较为简单, 下面分析第③题的算式递推推导过程.

设所求完全覆盖方法种数为Fn. 分两种情况.

①1, 2两格被一块1 X 2的多米诺骨牌盖住, 此时余下的2 X(n- 1)棋盘被n- 1块多米诺骨牌完全覆盖, 有Fn- 1种方法.

②1, 3两格被一块1 X 2的骨牌盖住, 此时2, 4两格也被1X 2的骨牌盖住, 而余下的2 X (n- 2)棋盘被n- 2张1 X2的骨牌完全覆盖, 有Fn- 2种方法. 因此, Fn= Fn– 1 + Fn- 2 (n≥3), 又显然F1= 1, F2 = 2.

上述三个问题, 都可以归结为如下数列

{y(n), n≥1}

的通项的求解, 即已知

y(1) = 1, y(2) = 1, y(n+ 2) = y(n+ 1) + y(n) (n≥1)

求y(n)的一般表达式. y(n)即为著名的斐波拉契(Fibonacci)数列.(斐波拉契数列的初始值可以为1, 1, 也可以为1, 2, 略有不同.)

卢开澄的《组合数学》(第4版, 清华大学出版社, 2006)采用母函数工具求解斐波拉契数列的通项. 另一种更常见的方法是特征方程法.

下面提供斐波拉契数列通项的四种求法, 其中第一种方法是中学生可以理解的方法, 用待定系数法“凑”等比数列,最后得到两个等式, 联立求解得到通项; 第二种方法就是最常见的特征方程法, 也是一般的《信号与系统》课程中介绍的时域求法; 第三、四种方法是《信号与系统》课程中介绍的变换域方法, 即z变换法, 一个是前向差分方程的z变换, 一个是后向差分方程的z变换. 四种方法的结果是一样的, 正所谓 “条条大道通罗马”.

为了介绍用变换域求解差分方程(即斐波拉契数列), 简单介绍一些背景知识, 即离散系统的z变换, 它是电子信息类专业本科必修专业基础课《信号与系统》的基本内容.

z变换是研究离散系统响应及系统特性的基本工具，z变换的地位和拉氏变换(又叫s变换)相似: 拉氏变换可以将微分方程变成代数方程求解, 而z变换可以将差分方程变成代数方程. 利用z变换求解差分方, 主要用到单边z变换的移位特性及逆z变换. 差分方程又分前向差分方程和后向差分方程, 两者基本是等价的, 在计算时略有不同.

下面是分别用前向差分方程和后向差分方程求解斐波拉契数列的一般公式.

【推荐关注】微信公众号:许兴华数学(xuxinghua688)

(读者交流Q群：552532631，回答“数学花园”即可)返回搜狐，查看更多