用數(shù)學(xué)歸納法.
證明j具有性質(zhì):對任意正整數(shù)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成立.
假設(shè)對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時的歸納假設(shè),有:
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)也對任意正整數(shù)i ≥ j+1成立.
于是命題對任意自然數(shù)j成立,即對任意i ≥ j+1,有Fi ≤ Fj·F(i-j)+F(j+1)·F(i-j-1).