Due in lecture, Thursday May 9 (with homework #7). Please do the homework in a workbook.

In all cases, you can leave your answer in terms of factorials or \(C(n,r)\). No need to calculate: just simplify as much as you can with algebra.

# From the Text

Complete the following questions from the text:

- Section 5.3: 12, 26
- Section 5.4: 28
- Section 5.5: 8, 14, 42, 46
- Section 7.1: 4, 10, 28
- Question 4: The question is asking you to find initial conditions that make this true, and prove. For the proof, just do the induction steps. [No need to waste paper on the base case, which is just going to be “I chose the initial conditions so it works, so it works.”]
- Question 10: Certainly the realities of investment are different in China than in Canada, but remember the power of compound interest. Read The Wealthy Barber some time you have a chance.

- Section 7.2: 8

# Questions

- How many strictly increasing sequences of positive integers are there that have 1 as the first term and \(n\) as the last term? [For example, for \(n=4\) there are four possible sequences: \(1,4; 1,2,4;1,3,4;1,2,3,4\).]
- If we analyze selection sort, we would come up with a recurrence \(a_n=a_{n-1}+(n-1)\) for the number of comparisons used to sort \(n\) elements, with \(a_0=0\). Solve this recurrence using the method discussed in lecture. Hint: guess that there is a quadratic particular solution.