经典的走楼梯问题

兔子问题

假设某种兔子在出生的第1个月不能生育,但2个月之后每月生一对(一雌一雄)兔子. 开始时, 假设有一对新生的兔子, 且不考虑兔子的死亡. 问: 在第7个月月初共有多少对兔子?

这个问题可以用递推的思想来求解. 令表示第个月月初兔子的总数. 根据已知的信息,第1个月月初兔子总对数为

在第2月月初, 因为兔子没有生育, 所以

这些是初始条件. 到第3个月月初, 生育了子女, 子女记作. 现在共有兔子 2对, 即

到第4个月月初, 生育了子女, 然而尚不能生 育,所以

到第5个月月初, 和都生小兔, 所以

到第6个月月初, 在第4个月存活的3对兔子都生育小兔, 所以

到第7个月月初,在第5个月存活的5对兔子都生育小兔, 所以

递推关系

一般地, 注意到下个月月初增加的兔子对数等于上个月存活的兔子对数. 这就是,

第 个月月初兔子对的总数 = 第个月月初对的总数 + 第 个月月初兔子对的总数

这样生成了下列递推关系

的递推关系定义为:

现在可以计算 的任意一项. 初始条件是:

由 的递推关系, 可得

数列叫做斐波那契数列. 它的项称为斐波那契数.