算法导论第三章函数的增长问题研究2

算法导论3.2-7

斐波那契数列：0,1,1,2,3,5.... 
证明：对于i>=0,第(i+2)个斐波那契数满足F(i+2)>=φ^i
利用φ=(1+√5)/2 Φ=(1-√5)/2 =>F(i)=(φ^i-Φ^i)/√5
Φ是φ的共轭数。
F(i+2)=(φ^(i+2)-Φ^(i+2))/√5
φ^2=((√5+1)/2)^2=(3+√5)/2
Φ^2=((√5-1)/2)^2=(3-√5)/2
F(i+2)=(φ^i((3+√5)/2)-Φ^i(3-√5)/2)/√5
      =φ^i+((3√5-5)/10)(φ^i-Φ^i)
      =φ^i+((3-√5)/2√5)F(i)  //F(i)=(φ^i-Φ^i)/√5
      因为F(i)>0  (3-√5)/2√5>0 所以F(i+2)>φ^i