Discrete Math                                                  

Review Chapter 4 Solutions

 

 

1.      Compute the first 4 terms of the following sequences:

a.       , for all n > 1               3/2,   6/5,   9/10,   12/17

 

 

b.  , for all m > 0           2,   3,   3,   4

 

2.      Find an explicit formula for the following sequence:

 

                     

 

 

3.      Compute the summation or product as indicated:

a.                                     31/16 or 1 15/16

 

b.                          8640

 

 

4.      Rewrite the following using summation notation:

 

1 + r + r2 + r3 + r4 + r5                   

 

5.      Prove each of the following using mathematical induction:

 

a.       2 + 4 + 6 + … + 2n = n2 + n for all integers n >1.

 

Step 1:  P(1) = 2(1) = 2          12 + 1 = 2        2=2

Step 2: Suppose P(k) is true:  That is, suppose that 2+4+6+…+2k = k2+k

Step 3:  We want to show P(k+1) is true:  That is, 2+4+6+…+2(k+1) = (k+1)2+(k+1)

            2+4+6+…+2(k+1)= [2+4+6+…+2k]+2(k+1)

                                           = [k2+k]+2(k+1)

                                           =  k2+3k+2

                                           = (k2+2k+1)+(k+1)

                                           = (k+1)2 + (k+1)  Q.E.D.

 

 

 

b.      23n – 1 is divisible by 7, for all integers n > 1.

Step 1:  P(1) = 23(1)–1 = 8-1 = 7,  and 7=7(1), so 7 is divisible by 7.

Step 2:  Suppose P(k) is true:  23k-1 is divisible by 7.

Step 3: We want to show P(k+1) is true:  23(k+1)-1 is divisible by 7.

            23(k+1)–1 = 23k+3–1 = (23k)(23)–1 = (23k)8–(8–7) = 8 (23k)–8+7 = 8(23k–1)+7

We know from our supposition that 23k–1 is divisible by 7, and 7 is divisible by 7, so the sum 8(23k–1) + 7 is also divisible by 7.  Q.E.D.

 

c.       n! > n2, for all integers n > 4

Step 1: P(4) –>  4! = 24 and 42 = 16, so 4! > 42

Step 2:  Suppose P(k) is true:  Suppose k! > k2

Step 3:  We want to show (k+1)! > (k+1)2

From our hypothesis, k! > k2.  Multiply both sides by (k+1) and you have k!(k+1) > k2(k+1)

(k+1)! > k3 + k2  But how does k3 + k2 compare to (k+1)2?

If we can show k3 + k2 > (k+1)2 for k > 4, we have what we need by the transitive property.  We can simplify a little first:  k3 + k2 > k2 + 2k + 1, so

k3 > 2k + 1 is all we need to show.

            Sub-Proof:  Step 1:  P(4):  43 = 64,  2(4)+1 = 9, 64>9. It works for 4.

                        Step 2:  Suppose P(a) is true where 4<a<k: a3 > 2a + 1

                        Step 3:  Show P(a+1) is true:  (a+1)3 > 2(a+1) + 1 {or 2a+3}

                                    (a+1)3 = a3 + 3a2 + 3a + 1

                                                >(2a+1) + 3a2 + 3a + 1 from the hypothesis

                                                > (2a+1+2) + 3a2 + 3a + 1 – 2

                                                > (2a+3) + 3a2 + 3a – 1

Since a > 4, 3a2 + 3a – 1 > 0, and since (a+1)3 is greater than (2a+3) + some positive number, the inequality holds, k3 > 2k+1

and now we can say (k+1)! > (k+1)2 Q.E.D.

** No, you will not have one this complicated on the test.  No sub-proofs required.  J

 

6.      Use strong mathematical induction to prove the following:

 

Suppose that E0 = 1, E1 = 2, E3 = 3, Ek = Ek–1 + Ek–2 + Ek–3 for all integers k > 3.

Prove that En < 3n for all integers n >0.

 

            Step 1:  E0 = 1, 1 < 30

                        E1 = 2, 2 < 31

                        E2 = 3, 3 < 32

            Step 2:  Let k be an integer > 3 and suppose Ei < 3i for 0 < I < k.

 [We want to show that Ek < 3k].

Ek = Ek-1+Ek-2+Ek-3 from the definition of the sequence. 

By the hypothesis, Ek-1 < 3k-1, Ek-2< 3k-2, and Ek-3 < 3k-3. so, adding these three inequalities together, we get

Ek-1+Ek-2+Ek-3 < 3k-1 + 3k-2 + 3k-3.  Since 3k-3 and 3k-2 are both < 3k-1, we can say

                 Ek    < 3k-1 + 3k-1 + 3k-1

            Or Ek < 3(3k-1)

            So Ek­ < 3k.  Q.E.D.

I hope there are no typos.  J