Recall the Fibonacci numbers. as dened by: f1= 1 f2 =1 fa = fnl + fnz, for n L: 3. Recall the Sharp numbers from P86, as dened by: 31:2 32:4 311 = 3nl + 3.12, for Tl- E' 3+ Claim. For all n. 2 3, 3,, = 4'f'nl + 2 fn2- Fill in the blanks helonr with a proof by strong induction of the claim. This is a variation on the Tstep process from lecture and the induction proof handout for (not strong} mathematical induction, with appropriate modications in the base case, induction hypothesis and inductive step to take strong induction into account. You may use chatGPT at your own risk. but you must take that solution and t it appropriately into the form below. I'd rather you not use it, so that you get the host engagement with induction. Step 0. For all n. .3 , we want to shoe.r that Step 1. For any n. 2 . let P(n) be the preperty that We want to show that P{n) is true for all n. 33 Step 2. As baSe castes, consider when n = . We will Show that PI: ) is true: that is, that Fortunately, {add as many base cases as you need.) Step 3. Let k 2 . For the induction hypothesis, suppose that P( 2|, . . . , PUB] are true, or equivalently, that fer 3.11 S k' 5 : PUc'). That is, suppose that Step 4. Now we prove that PH 1) is true, using our induction assumptions that PI: 31,. . . ,Pc) are two. That is. we prove that Step 5. The proof that PU: +1} is true {given that Pf }. . . .,P[k:l are true} is % follows: left-hand side of Plfk + 1) = column format, use 1H applied 2 to some 36' in the range of the 1H. = righthand. side of PU: + 1). Step 8. The steps above have shown that for any #- 2 _. if Pl: ),7...P{k} are true. then PUc + I) is also true. Combined with the base cases: which show that P": L are true, we have shown that for all n. I: . PM) is true, as desired