How to do question 1?

Part l: Strong Induction (50 pt.) (40 pt., 20/10 pt. each) Prove each of the following statements using strong induction. For each statement, answer the following questions a. (4/2 pt.) Complete the basis step of the proof by showing that the base cases are true. b. (4/2 pt.) What is the inductive hypothesis? c. (4/2 pt.) What do you need to show in the inductive step of the proof? d. (8/4 pt.) Complete the inductive step of the proof. (20 pt.) Let al, a2,a3, 1. be the sequence defined by the following recurrence relation: A1-3, a,-5 ??3.ai-1-2.ai-2 for 12 3 Prove that an-2 +1 for any positive integer n. 2. (20 pt.) Let bo.bi, b2. be the sequence defined by the following recurrence relation: bo-5, b 16 b-7 bi-1 -10 b-2 for 22 Prove that bn 3 2" + 2 5" for any nonnegative integer n