The Fibonacci numbers F0, F1, ..., are defined by

F0 = 0, F1 = 1, Fn = Fn1 + Fn2

Use induction to prove that: (a) Fn = O(2n) (b) Fn = 2 n

2. The Fibonacci numbers Fo, Fi,., are defined by Use induction to prove that: (a) Fn= 0(2") (b) F (V2)