# Homework #8

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

1. 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$$.]
2. 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.