1

Given Fibonacci is F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for all n >= 2

Prove that for any a, b such that 1 ≤ a < φ < b we have that F(n) ∈ O(b^n ) and that F(n) ∈ Ω(a^n ).

I'm looking for help on how to start this question

s878
  • 11
  • 1
    What have you tried? What do you already know about the Fibonacci numbers? In particular, do you know an explicit formula for computing $F(n)$ without computing $F(0), F(1), \ldots, F(n-1)$? – Michael Lugo Sep 26 '17 at 16:01

0 Answers0