1. A proposition about the Fibonacci numbers and a proof (by induction) is presented below. Complete all of the missing spaces with appropriate terms or phrases. Note that for this problem we are defining the Fibonacci sequence starting at n = 1, i.e. F1 = F2 = 1 and Fn = Fn-1 + Fn-2. Proposition. For every natural number n 2 1, if 3 then Fn is even. Proof (by induction). Base Case. We will show the proposition is true when n = The recurrence equation that defines the Fibonacci numbers has F3 = F2 + F1 = 1+ 1 =2, and this is an even number. Inductive Step. Suppose the proposition is true when n = 3k. (We wts that the proposition is true when n = .) The recurrence equation that defines the Fibonacci numbers implies Fak+3 = F3k+2 + F3k+1 (1) = F3k+1 + F3k + F3k+1 (2) = 2F3k+1 + F3k (3) where in line (2) we applied the recurrence equation a second time to the Fibonacci number F3k+2. Since 2F3k+1 is even, and since our tells us F3k is even it follows that Fak+3 is even.2. Recall (from our notes) the definition of a "path graph with n vertices," PG(n). Use induction to prove the fol- lowing proposition: Proposition. The graph PG(n) has n - 1 edges. Proof (By Induction). Base Case. Inductive Step.3. Let r E R be some fixed real number. Use induction to prove the following proposition. 1 - rn+1 'N P UA . uo!!sodold p' = i=0 1 -r Proof (by induction) Base Case Inductive Step4. Consider the recursivelydened sequence and initial condition an=anl+an2+"'+al+a0 (10:1 Write an inducion proof of the following proposition (and consider the hint that you may need to use the Proposition from problem 3 as part of your work): Proposition. Vn Z 1, an = 2"1 Proof (by induction) Base Case Inductive Step 5. Use induction to prove the "extended De Morgan's law" For all n 2 1, Ain An . .. n An = AlUA U . . . UAn Here each A; is some set, and there is some arbitrary universal set, U, that contains them all as subsets. Proof (by induction) Base Case Inductive Step