题目

令F0=1,F1=1,Fk=Fk-1+Fk-2,即Fk为斐波那契数列.试证明：Fi≤FjF(i-j)+F(j+1)F(i-j-1),这里i≥j+1∈Z+

提问时间：2021-01-29

答案

用数学归纳法.
证明j具有性质:对任意正整数i ≥ j+1都有Fi ≤ Fj·F(i-j)+F(j+1)·F(i-j-1).
若j = 0,Fi ≤ F0·Fi+F1·F(i-1) = Fi+F(i-1)显然对任意i ≥ j+1 = 1成立.
若j = 1,Fi ≤ F1·F(i-1)+F2·F(i-2) = F(i-1)+2F(i-2) = Fi+F(i-2)也对任意i ≥ j+1 = 2成立.
假设对j < k,Fi ≤ Fj·F(i-j)+F(j+1)·F(i-j-1)对任意i ≥ j+1成立.
则j = k时,对任意i ≥ j+1 = k+1,有i-1 ≥ k,i-2 ≥ k-1.由j = k-1,k-2时的归纳假设,有:
F(i-1) ≤ F(k-1)·F(i-k)+Fk·F(i-k-1),F(i-2) ≤ F(k-2)·F(i-k)+F(k-1)·F(i-k-1).
相加得Fi = F(i-1)+F(i-2) ≤ (F(k-1)+F(k-2))·F(i-k)+(Fk+F(k-1))·F(i-k-1) = Fk·F(i-k)+F(k+1)·F(i-k-1).
即j = k时,Fi ≤ Fj·F(i-j)+F(j+1)·F(i-j-1)也对任意正整数i ≥ j+1成立.
于是命题对任意自然数j成立,即对任意i ≥ j+1,有Fi ≤ Fj·F(i-j)+F(j+1)·F(i-j-1).