The Fibonacci numbers are recursively dened by F1 = 1; F2 = 1and for n > 1; F_(n+1) = F_n + F_(n-1): So the rst few FibonacciNumbers are: 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; : : : Thereare numerous properties of the Fibonacci numbers.
a) Use the principle of Strong Induction to show that allintegers n > 1 and m > 0
F_(n-1)F_(m )+ F_(n)F_(m+1) = F_(n+m):
Solution. (Hint: Use induction with respect to m. First verifythe formula the base case,for m = 1 case (here use again inductionon n) the assume that it is true for m = 1;m = 2; ;m = k then provethat it remains true if m = k + 1 (still with the use of inductionon n)
