klbcooldude
Nov 3, 2009, 02:03 PM
Hey I'm looking for some help on these questions, I don't know where to begin.
Base Case: F(0) = 0; F(1) = 1.
Recursive Step: F(n) = F(n-1) + F(n-2) for all n ≥ 2.
(a) Prove by induction that F(n)≤((1+√5)/2)^(n-1)
(b) Prove by induction that F(n)≥(1.5)^(n-1)
thanks
Base Case: F(0) = 0; F(1) = 1.
Recursive Step: F(n) = F(n-1) + F(n-2) for all n ≥ 2.
(a) Prove by induction that F(n)≤((1+√5)/2)^(n-1)
(b) Prove by induction that F(n)≥(1.5)^(n-1)
thanks