Fibonacci数

概述

Fibonacci数 是经典的递归定义序列，$F_n=F_{n-1}+F_{n-2}$，其增长速率由黄金比例 $\phi$ 决定。

定义

Fibonacci数

$F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}(n\ge 2)$

核心性质

• 黄金比例：$\phi =\frac{1+\sqrt{5}}{2}\approx 1.61803$，$\hat{\phi }=\frac{1-\sqrt{5}}{2}\approx -0.61803$
• Binet 公式（闭合形式）：$F_n=\frac{{\phi }^n-{\hat{\phi }}^n}{\sqrt{5}}=\lfloor \frac{{\phi }^n}{\sqrt{5}}+\frac{1}{2}\rfloor$
• 渐近行为：$F_n=\Theta ({\phi }^n)$，即 $F_n$ 以指数速率增长。
• Fibonacci 数在算法分析中频繁出现，如朴素递归计算 $F_n$ 的时间复杂度为 $\Omega ({\phi }^n)$。
• 恒等式：$F_0+F_1+\cdots +F_n=F_{n+2}-1$；$F_n^2+F_{n+1}^2=F_{2n+1}$

章节扩展

第3章：运行时间刻画

• 3.3 标准记号与常见函数 给出 Fibonacci 数的定义与 Binet 公式的推导。

参见

• 阶乘
• 对数函数