Solutions for selected homework problems:

Week #10

7.2

 2> Let x belong to A. R is reflexive => (x,x) belongs to R.
      (x,x) belongs to R, (x,x) belongs to R => (x,x) belongs to RoR = R^2.

 9> Here, there are 2 choices for each a(ii), 1 <= i < 6. For each
      pair a(ij), a(ji), 1<= i < j <= 6,
      there are 2 choices, and there are (36-6)/2=15 such pairs => 
      there are (2^6) (2^15) = 2^21 such matrices.

7.4

 8> a>   -For all a belonging to A, a-a=3*0 so R is reflexive.
         -For a,b in A, a-b = 3c, for some c belonging to Z => 
          b-a = 3(-c) for -c belonging to Z, so aRb => bRa
          and R is symmetric.
         -If a,b,c belong to A, and aRb, bRc, then a-b=3m, b-c=3n,
          for some m,n in Z
          => (a-b) + (b-c)=3m+3n => a-c=3(m+n), so aRc; R is 
          transitive.
    b>  [1]=[4]=[7]={1,4,7}
        [2]=[5]={2,5}
        [3]=[6]={3,6}
        A={1,4,7} U {2,5} U {3,6}

Week #11

9.2

 10>
	a>The coefficient of x^12 in (1-x)^(-4) is C(-4,12)(-1)^12=C(15,12)
	b>The coefficient of x^12 in [(1-x)^7/(1-x)]^4 is 
          (-4)C(-4,5)(-1)^5+C(-4,12)(-1)^12 = 4(-1)^5C(8,5)+C(15,12)=
	     C(15,12)-4C(8,5)

 18>	The coefficient of x^n is C(-1/2,n)(-4)^n
	= {[(-1/2)-n+1][(-1/2)-n+2].....[(-1/2)-1](-1/2)}(-4)^n/(n!)
        = [(1+2n-2)(1+2n-4)...(1+2)(1)](2^n)/(n!)
        = [(2n-1)(2n-3)...(5)(3)(1)](2^n)(n!)/(n!n!)
        = (2n)!/(n!n!) = C(2n,n)

9.3

  4> a>  (1/(1-t^2))(1/(1-t^3))(1/(1-t^5))(1/(1-t^7))
     b>   t^67(1/(1-t^2))(1/(1-t^3))(1/(1-t^5))(1/(1-t^7))

Week #12

4.1>

 20> b>  Hint on Inductive Step: a_k+1 = a_k + a_k-1 
         < (7/4)^k + (7/4)^(k-1) < (7/4)^(k+1)
	Proved by the Alternative Form of the Principle of Mathematical
        Induction

10.1

 8> a>      Suppose that for  i = k, where 1<= k <= n-2
	    no interchanges result (for the first time) in the execution of the
            inner FOR loop.
	    Up to this point, the number of executions that have been made is 
            (n-1)+(n-2)+...+(n-k) > (1/2)(n-k-1)(n-k) unnecessary comparisons.

    b>      Use a flag variable to indicate if the list is sorted.
	    In the WHILE loop set initially flag = true; if the statements
            inside the IF statement are executed then flag is set to false.
	    As long as flag is false, then the WHILE loop continues; if flag is
            true, then the WHILE loop stops, not causing unnecessary comparisons.

   c>       worse case: O(n^2)
	    best case: O(n)