1a. Consider the sequence {?? }n?0 which starts1,2,7,20,61,122,..., defined by the recurrence relation ?? = 2???1+ 3???2 and initial conditions ?0 = 1, ?1 = 2. Solve the recurrencerelation. That is, find a closed formula for ??. Show yourwork.
The abandoned field behind your house is home to a large prairiedog colony. Each week the size of the colony triples. However,sadly 4 prairie dogs die each week as well (after the triplingoccurs). Consider the sequence ?0, ?1, ,a2,..., where ?? is thenumber of prairie dogs in the colony after n weeks.
(b) Write down a recurrence relation to describe an and brieflyexplain.
(c) Explain why if ?? is even, then ??+1 must also be even.
(d) Suppose you wanted to prove by mathematical induction thatan was always even. What would the base case be and why is itneeded? Your answer should be specific to this context.
(e) Your friend believes what you have written in parts (b) and(c), but still does not see why ?3 must be even because he does notunderstand the logic behind induction. Explain why induction inthis case proves that there will be an even number of prairie dogsin week 3 specifically
Please with clear legible hand writing, and number yourwork.
