反证法,证斐波那契数F0=1,F1=1,F2=2,F3=3,F4=4,...,Fi=Fi-1+Fi-2,对i>=1,满足Fi

Question

反证法,证斐波那契数
F0=1,F1=1,F2=2,F3=3,F4=4,...,Fi = Fi-1 + Fi-2,对 i >= 1,满足Fi < (5/3)^i
假设 i = 1,2,...,k成立；为了证明定理,需要证明 Fk+1 < (5/3)^(k+1).
根据定理我们有 Fk+1 = Fk + Fk-1
Fk+1 < (5/3)^k + (5/3)^(k-1)
< (3/5)(5/3)^(k+1) + (3/5)^2 * (5/3)^(k+1)
< (3/5)(5/3)^(k+1) + (9/25)*(5/3)^(k+1)
化简后为
Fk+1 < （3/5 ＋ 9/25）* (5/3)^(k+1)
< (24/25)* (5/3)^(k+1)
< (5/3)^(k+1)
怎么到最后一步 (5/3)^(k+1)

Answer 1

因为24/25<1
同乘(5/3)^(k+1)
所以
(24/25)* (5/3)^(k+1)< (5/3)^(k+1)