MATH 1365 Introduction to Mathematical Reasoning Fall 2021 Homework 6 1. (35 pts) Consider the sequence of integers a1, a2, a3, dened recursively as (11 = 1, a2 = 1, and an\" = an + an_1 for all integers n 2 2. Use induction to prove that am is even for all integers n 2 1. Hint #1: Determine a3. Hint #2: Observe that a3n+3 = a3n+2 + a3n+1 and a3n+2 = a3n+1 + am for all integers n 2 1. 2. (35 pts) Consider the sequence a1, a2, a3, dened recursively as a1 = 0, a2 = 4, and an\" = 6a\" 5an_1 for all integers n 2 2. Use strong induction to prove that an = 5""1 1 for all integers n 2 1. 3. (30 pts) Use the method of smallest counterexamples to prove that 6 I (7" 1) for all integers n 2 1