### Assignment 2 Math2320

Turn in by Thursday, October 24, to have it marked and returned before Quiz 2 on October 30.

1. I am interested in the following sequence of numbers. For each positive integer n, we take the product of the first n+1 odd numbers (i.e. 1,3,5,...,(2n+1)) and we divide it by the product of the first n even numbers (i.e. 2,4,6,...,(2n)). Call the resulting number Q_n.
1. Prove, by induction, that Q_n is less than 2n+1.
2. But does Q_n grow to infinity as n gets large? Since Q_(n+1) is obtained from Q_n (for large n) by multiplying by a number very nearly 1, i.e. (2n+1)/(2n), it is a little hard to guess.

We'll prove (approximately) that log(n) is big-O of Q_n as follows.

For each n , let H_n be the n-th Harmonic number,
i.e. the sum of 1/k for k from 1 to n.

Now prove by induction that Q_n is bigger than (1/2) * H_n.

Deduce that Q_n goes to infinity.

2. Suppose that the set S is recursively defined by the following two simple rules:

1. 5 and 7 are in S;
2. x+y is in S whenever x and y are in S.
Prove by induction, that S contains all integers greater than 23.

Then explain where your proof would break down if you tried to prove that S contained all integers greater than 20.

3. From the text
page 216: 10, 11