Problem 2. (10 points) The Fibonacci numbers F(n) forn E N are defined as follows: 0, n=0 F(n 1)F(n -2), n>1 Using strong induction1, prove that and q = 1-25 1+V5 p= Hint: p and q are the two roots of the equation x2-x-1 = 0. 1 In strong Induction the inductive hypothesis is Vi, 0 s i s k P(i). In other words, in the inductive step you carn show that P(k + 1) follows from P(0) P(1) P(k). It is called strong induction because the inductive hypothesis seems stronger. Although induction and strong induction are equivalent, some proofs are simpler using strong induction