Assignment 2 Math2320 Dow

  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.


      Well Q_1 is just equal to 1*(2*1+1)/(2*1) = 3/2 Which is certainly less than 2*1+1.

      Now Assume that the statement is true for n, i.e. Q_n < 2n+1 and consider Q_(n+1). Think how to (recursively) get Q_(n+1) from Q_n. Well, Q_(n+1) = Q_n * (2(n+1)+1)/2(n+1). Since, by induction Q_n < 2n+1, we have that
      Q_(n+1) < (2n+1) * [ (2n+3)/(2n+2) ]. Therefore we need to check that (2n+1) * [ (2n+3)/(2n+2) ] <= (2(n+1) + 1)= 2n+3. Well just multiply both sides by (2n+2) and, if necessary, expand:
      (2n+1) * (2n+3) is the left hand side, while (2n+2)*(2n+3) the right hand side. Clearly the LHS is less than the right hands side.

    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.


      We know Q_1=3/2 and check that (1/2)H_1 = 1/2 * 1. So, for the induction proof, assume that n >= 1 and that Q_n> (1/2)H_n.
      Again Q_(n+1) = Q_n * (2n+3)/(2n+2), while H_(n+1) = H_n + (1/(n+1)).
      So (1/2) H_(n+1) = (1/2) H_n + 1/2(n+1) which, by induction is less than
      Q_n + 1/2(n+1). Now look more closely at that expression for Q_(n+1), and see that it equals
      Q_n * (2n+2) + 1 ) / 2n+2 = Q_n * (1 + (1/(2n+2)) ) = Q_n + Q_n / (2n+2), we are done so long as we know that Q_n is at least 1.

      I guess that should have been part 1 of the question. You can easily prove this by induction, Q_1 is bigger than 1, and then each time we multiply it by a number bigger than 1. Alternatively we can notice that Q_n is equal to

      (3/2)*(5/4) * ... * (2n+1/2n) -- i.e. a product of numbers each of which is bigger than 1.

      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.


    First just generate a few iterations of S:
    S= {5,7} union {10,12,14} union {15,17,19,20,21} union {22,24,25,26,27,29,30,31,33,34,...} union ...

    P(n) is the statement that n is in S and we want to prove P(n) for all n> 23.

    Base step: 24 is in S (inspection)

    Inductive: assume that n>23 and that P(k) is true for all k between 24 and n. We must prove that P(n+1) holds.

    Well if P( (n+1) - 5) holds, then 5, (n+1)-5 are both in S and we can then say that (n+1) - 5 + 5 = (n+1) is in S. This is valid so long as k=(n+1) -5 is bigger than 23. I.e. this is valid so long as n+1< 29. In other words we have to check P(k) for k< 29 directly. Luckily we already did most of them above. We only missed 28, so 28 = 7+7+7+7 is in S.

  3. From the text: page 216:

    10: a recursive algorithm for a^(2^n)

    11. How does the number of multiplications used compare to the number used by power(a,0):= 1 and power(a,k+1):= a*power(a,k)?


For question 10:

	Procedure pwr(a,n)
	if n=0 then pwr(a,0):=1
		   pwr(a,n):= k*k

Number of multiplications in pwr(a,n) is about n+1, while the number in power(a,2^n) is of course about 2^n.