0.3. The Fibonacci numbers Fo, F1, F2, ..., are defined by the rule Fo= 0, F...

 

Transcribed Image Text:

0.3. The Fibonacci numbers Fo, F1, F2, ..., are defined by the rule Fo= 0, F = 1, Fn = Fn-1 + Fn-2. In this problem we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth. (a) Use induction to prove that F 20.5n for n 6. (b) Find a constant c < 1 such that Fn 2ch for all n 0. Show that your answer is correct. (c) What is the largest c you can find for which F = (2c)? 0.3. The Fibonacci numbers Fo, F1, F2, ..., are defined by the rule Fo= 0, F = 1, Fn = Fn-1 + Fn-2. In this problem we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth. (a) Use induction to prove that F 20.5n for n 6. (b) Find a constant c < 1 such that Fn 2ch for all n 0. Show that your answer is correct. (c) What is the largest c you can find for which F = (2c)?