4. For the following two problems use induction to prove. Recall the standard definition of the...

   

Transcribed Image Text:

4. For the following two problems use induction to prove. Recall the standard definition of the Fibonacci numbers: Fo=0, F =1 and Fn = Fn-1+ Fn-2 for all n 2. a. Prove that Fi i=0 = Fn+2 1 for every non-negative integer n. [10 Points] b. The Fibonacci sequence can be extended backward to negative indices by rearranging the defining recurrence: Fn = Fn+2Fn+1. Here are the first several negative-index Fibonacci numbers: n Fn -10 -9 -55 -8 -7 -6 -5 -4 -3 -2 -1 34 -21 13 -8 5 -3 2 -1 1 Prove that Fn = (-1) +1 F for every non-negative integer n. [10 Points] 4. For the following two problems use induction to prove. Recall the standard definition of the Fibonacci numbers: Fo=0, F =1 and Fn = Fn-1+ Fn-2 for all n 2. a. Prove that Fi i=0 = Fn+2 1 for every non-negative integer n. [10 Points] b. The Fibonacci sequence can be extended backward to negative indices by rearranging the defining recurrence: Fn = Fn+2Fn+1. Here are the first several negative-index Fibonacci numbers: n Fn -10 -9 -55 -8 -7 -6 -5 -4 -3 -2 -1 34 -21 13 -8 5 -3 2 -1 1 Prove that Fn = (-1) +1 F for every non-negative integer n. [10 Points]