斐波那契

问题

在数学上, 斐波那契数是以递归的方法来定义：

也就是斐波那契数列由0和1开始, 之后的斐波那契数就是由之前的两数相加而得出.

若将令斐波那契数列的每一项平方得到新的数列.

那么能否推导出其线性递归关系式呢?

方法一

已知

将两个方程平方后相加得

因此

方法二

斐波那契数列的特征多项式的根是

因此, 斐波那契数列的通项公式可写为

其中和是常数.

则斐波那契数列通项公式的平方为

由于, 的多项式的特征根是和. 因此其特征多项式是

为了进一步简化, 我们引入卢卡斯数, 它满足与斐波那契数相同的递归关系, 但其初始值为

因此, 卢卡斯数为

则

因此, 我们的特征多项式简化为

因此