1: Refinancing a loan. Suppose someone takes out a home improvement loan for $30,000. The annual interest on the loan is 6% and is compounded monthly. The monthly payment is $600. Let an denote the amount owed at the end of the nth month. The payments start in the first month and are due the last day of every month. (a) Give a recurrence relation for an. Don't forget the base case. (b) Suppose that the borrower would like a lower monthly payment. How large does the monthly payment need to be to ensure that the amount owed decreases every month? Q2: A variation on Fibonacci's rabbits. Give a recurrence relation for the population of Fibonacci's rabbits if the rabbits must be at least two months old to reproduce. The colony starts with one pair of newborn rabbits. Every pair of reproducing rabbits gives birth to a new pair of rabbits, one male and one female over the course of a month. Let gn denote the number of pairs of rabbits at the end of month n. Assume that the first pair of rabbits obtained for the colony are born at the end of month 1. Q3: Proving identities by induction. Prove each of the following statements using mathematical induction. Q4: Proving inequalities by induction. Prove each of the following statements using mathematical induction. Q5: Proof by the wellordering principle. Prove that any amount of postage worth 8 cents or more can be made from 3-cent or 5-cent stamps. Q6: Properly nested parentheses and curly braces. Give a recursive definition for strings of properly nested parentheses and curly braces. For example, ({}){}() is properly nested but ({)} is not properly nested. The empty string should not be included in your definition. Q7: Characterizing the strings in a recursively defined set. The recursive definition given below defines a set S of strings over the alphabet {a, b}: Base case: S and a S Recursive rule: if x S then, o xb S (Rule 1) o xba S (Rule 2) (a) Use structural induction to prove that if a string x S, then x does not have two or more consecutive a's. (b) Use strong induction on the length of a string x to show that if x does not have two or more consecutive a's, then x S. Specifically, prove the following statement parameterized by n: For any n 0, let x be a string of length n over the alphabet {a, b} that does not have two or more consecutive a's, then x S. Q8: Recursively computing the product of two integers. Give a recursive algorithm that takes as input two non-negative integers x and y and returns the product of x and y. The only arithmetic operations your algorithm can perform are addition or subtraction. Your algorithm should have no loops. Q9: Solving linear homogeneous recurrence relations. Solve the following recurrence equations with the given initial values. bn = 3bn1 + 4bn2. Initial values: b0 = 4, b1 = 1. Q10: Let A, B be square matrices such that AB - BA. Show that for any integer n, ABn=BnA