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