大斐波那契数

斐波那契数列是按如下方式递归定义的数列: $$F_n=F_{n-1}+F_{n-1}, \quad F_1=F_2=1.$$ 它的前12项分别是 1,1,2,3,5,8,13,21,34,55,89,144 因此该数列首次出现3位数字是在第12项，那么首次出现1000位数字是在第几项？

本题难度:

解答

斐波那契数列的通项公式是： $$F_n=\frac{1}{\sqrt5}\cdot\left(\frac{\sqrt 5+1}{2}\right)^n-\frac{1}{\sqrt5}\cdot\left(\frac{1-\sqrt 5}{2}\right)^n.$$ 显然等式右侧的第二项在n很大时接近于0, 因此$F_n$的大小主要由等式右侧的第一项决定。取对数得 $$\frac{1000}{\lg{\frac{\sqrt 5+1}{2}}}\approx 4784.$$ 利用WolframAlpha的Fibonacci(n)函数，在$n=4784$附近简单尝试即得结果。答案是$4782$。 本题无需编程。 附：通项公式的求法。 考虑常微分方程 $$y''-y'-y=0, \quad y(0)=y'(0)=1.$$ 将$F_n$视作$y^{(n-1)}(0)$即可。该方程的解法是我国《高等数学》课程的标准内容之一，此处不再复述。