Question

1a. Consider the sequence {?? }n≥0 which starts 1,2,7,20,61,122,..., defined by the recurrence relation ?? = 2??−1 + 3??−2 and initial conditions ?0 = 1, ?1 = 2. Solve the recurrence relation. That is, find a closed formula for ??. Show your work.

The abandoned field behind your house is home to a large prairie dog colony. Each week the size of the colony triples. However, sadly 4 prairie dogs die each week as well (after the tripling occurs). Consider the sequence ?0, ?1, ,a2,..., where ?? is the number of prairie dogs in the colony after n weeks.

(b) Write down a recurrence relation to describe an and briefly explain.

(c) Explain why if ?? is even, then ??+1 must also be even.

(d) Suppose you wanted to prove by mathematical induction that an was always even. What would the base case be and why is it needed? 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 not understand the logic behind induction. Explain why induction in this case proves that there will be an even number of prairie dogs in week 3 specifically

Please with clear legible hand writing, and number your work.

Answer 1