Problem 2. (10 points) The Fibonacci numbers F(n) for n EN are defined as follows: n=0 n=1 n>1 0, F(n)-1, F(n - 1) + F(n -2), Using strong induction1, prove that th and q = where p= 2 Hint: p and q are the two roots of the equation x2-x-1 0. In strong Induction the inductive hypothesis is Vi,0 S i S k P(i). In other words, in the inductive step you can 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