发现一个Fibonacci数列递推式

xiaoee posted @ 2009年12月12日 02:36 in Mathematics with tags Fibonacci 数列公式 , 4190 阅读

今天翻看以前的日记，看到几个月前发现的一个斐波那契数列的递推公式： $F(2n)={F^2(n)}+{F^2(n-1)}$ (公式二）

在这里Fibonacci数列为从0开始的这样一个序列：1，1，2，3，5，8，13，21 . . .，满足 $$F(n+1)=F(n)+F(n-1)$$ ，n>0;

记得当时是在晚上睡觉的时候在想怎么把递归程序转换成非递归程序的时候，想到Fibonacci数列，然后就想到上面那个公式的。

看到这个公式，还真不知道当时是怎么想出来的，于是把以前的草稿纸都翻了一下，才终于找到怎么推导出来的（看来有了想法一定要记录下来才行啊），如下：
$F(n)=F(n-1)+F(n-2)$
$=F(1)F(n-1)+F(0)F(n-2)

$=F(1)[F(n-2)+F(n-3)]+F(0)F(n-2)

$=F(2)F(n-2)+F(1)F(n-3)

$. . .$

$=F(i)F(n-i)+F(i-1)F(n-i-1) , n>0 (公式一）

这样就推出来了，只要把n用2n，i用n替换就得到 $F(2n)={F^2(n)}+{F^2(n-1)}$ 。

我们还可以得到 $F(2n+1)=F(n)F(n+1)+F(n-1)F(n)

=F(n)[F(n+1)+F(n-1)]

=F(n)[F(n)+2F(n-1)] (公式三）

Module77:Yes,it is.