首页 > 试题广场 >

（斐波那契数）本题考虑斐波那契数的性质。我们将使用生成函数技

[问答题]

（斐波那契数）本题考虑斐波那契数的性质。我们将使用生成函数技术求解斐波拉契递归式。生成函数（又称为形式幂级数）F定义为

$F(z)=\sum_{i=0}^{\infty}{F_{i}z^{i}}=0+z+z^{2}+2z^{3}+3z^{4}+5x^{5}+8z^{6}+13z^{7}+21z^{8}+...$

其中F_i为第i个斐波那契数。

a.证明：F(z)=z+zF(z)+z²F(z)。

b.证明：

$F(z)=\frac{z}{1-z-z^{2}}=\frac{z}{(1-\phi z)(1-\tilde{\phi}z)}=\frac{1}{\sqrt{5}}(\frac{1}{1-\phi z}-\frac{1}{1-\tilde{\phi}z})$

其中

$\phi=\frac{1+\sqrt{5}}{2}=1.61803....$

$\tilde{\phi}=\frac{1-\sqrt{5}}{2}=-0.61803...$

c.证明：

$F(z)=\sum_{i=0}^{\infty}{\frac{1}{\sqrt{5}}(\phi^{i}-\tilde{\phi}^{i})z^{i}}$

d.利用（c）的结果证明：对i>0， $F_{i}=\phi^{i}/\sqrt{5}$ ，结果舍入到最接近的整数。（提示：观察到 $\left| \tilde{\phi} \right|<1$ ）

查看答案及解析

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小

难度：

0条回答 0收藏 250浏览

扫一扫，把题目装进口袋