Question 1: [5'0 marks] In this question, remember to carefully word what it is you are trying to show at each step, and then whether or not you actually showed it. (a) Use mathematical induction (and proof by division into cases) to show that any postage of at least 12 can be obtained using 33 and 7 stamps. (b) Use mathematical induction to prove that: 37101 + 1) 3+6+9+...+3n= 2 Question 2: [15 marks] Consider a Double Tower of Hanoi. In this variation of the Tower of Hanoi there are three poles in a row and 291. disks, two of each of 71. different sizes, where n is any positive integer. Assume one of the poles initially contains all of the disks placed on top of each other in pairs of decreasing size. Disks are transferred one by one from one pole to another, but at no time may a larger disk be placed on top of a smaller disk. However, a disk may be placed on top of one of the same size. Let an be the minimum number of moves needed to transfer a tower of 2n disks from one pole to another. (a) Find a1, a2, and 0.3. (b) Derive a recurrence relation for the sequence (11, (12, G3,... Drawing a diagram, as shown in the textbook for the Tower of Hanoi, may help here. Check that the results in (a) satisfy your recurrence relation. (c) Show that the formula on = 2\"+1 2 for the nth term in the sequence satises the recurrence relation you derived in (b). Question 3: [25 marks] (a) Consider a sequence that obeys the recurrence relation: (11171 = 1+a'n71) an with 0.0 = 1. Use the method of iteration to guess an explicit formula for this sequence. (b) Use mathematical induction to verify the correctness of the formula you found in (a). Question 4: [20 marks] (a) Each person has two parents, four grandparents, eight great-grandparents, and so on. By summing a geometric sequence, nd the total number of ancestors a person has going back (1) ve generations, (2) 10 generations. (b) The normal growth pattern for Children aged 3-11 follows an arithmetic sequence. Given a child measures 98.2 Cm at age 3, and 109.8 cm at age 5, what is the common difference of the arithmetic sequence? What would the child's height at age 8 be? Question 5: (History Question) [10 marks] (a) Briefly outline the history and founders of logic. (b) Briefly outline the history of the first uses of mathematical induction