Homework #2 Solution

Description

 

Section 5.1

 

 

Compute  65 and  74.  Assume the  values of the  variables  are restricted so that the expressions  are defined.

 

 

Problem 65

 

 

      n!          (n−k+1)

Let, n! = n · (n − 1) · (n − 2) · … · 3 · 2 · 1

Therefore,

✭✭

= n(n−1)…(n−k+2)(n−k+1)(n−k)…3·2·1 (n−k+1)(n−k)(n−k−1)…3·2·1

✭✭✭ ✭

−k)…

= n(n−1)…(n−k+2)(n−✭k+✭1)✭(n             3·2·1

(n−k+1)(n−k)(n−k−1)…3·2·1

= n(n − 1)(n − 2)…(n − k + 2)

 

 

Problem 74

 

r

Prove that if p is a prime number and r is an integer with 0 < r < p, then  p

is divisible by p. Let,  p  =       p!                        

r       r!(p−r)!

=       p(p−1)!

r(r−1)!(p−r)!

This implies,  p  = ( p )                 (p−1)!

 

 

p   = ( p

r

p−1

r   (r−1)!((p−1)−(r−1))!

 

r          r )

r−1

 

∴ r p  = p p−1

r          r−1

Both   p   and   p−1  are integers  and  p can divide  p  p−1 , which states  that p

 

r            r−1

rtyrjstrsyjrt

r

can also divide r  p  .

r

However, p is a prime number  and is 0 < r < p.  So, p cannot  divide r, but since it’s a prime number,  p divides   p  .

 

 

 

Section 5.2

 

 

Problem 17

 

 

Prove  the statement by mathematical induction.

 

 

n

Y(     1    

 

    1  

 

       1      

 

 

i=0

2i + 1 · 2i + 2 ) = (2n + 2)!       for all integers  n ≥ 0

 

 

(i) Let, n = 0

Q0                                   

i=0 (   1             1                       1

2i+1 · 2i+2 ) = (2(0)+2)!

Q0                                   

i=0 (   1             1                       1                      1

2i+1 · 2i+2 ) = (2(0)+1) · (2(0)+2)

= 1       1          1

1  · 2  = 2! , so this is proven  for n = 0

(ii) Let, n = k

Qk                                    

i=0 (   1             1                      1

2i+1 · 2i+2 ) = (2k+2)!

(iii) Let, n = k+1

Qk+1                               

i=0 (   1             1                          1

2i+1 · 2i+2 ) = (2(k+1)+2)!

 

Qk+1                               

k                                   

 

2i+1 · 2i+2 ) = Qi=0 ( 2i+1 · 2i+2 ) · 2(k+1)+1  · 2(k+1)+2 , by (ii)

 

i=0 (   1             1

1             1                     1                        1

 

=      1                    1

     1      

 

(2k+2)!  · (2k+3)  · (2k+4)

=

      1       

(2k+4)!

∴ Qn                                     

i=0 (   1             1                      1

2i+1 · 2i+2 ) = (2n+2)! , for all integer  values n ≥ 0.

 

 

Problem 29

 

 

Use the  formula  for the  sum of the  first n integers  and/or the  formula  for the sum of a geometric  sequence to evaluate  the sum or to write in closed form.

 

1 − 2 + 22 − 23  + . . . + (−1)n 2n , where n is a positive  integer.

 

i=0

Goal is to find the  geometric  series indicated  by Pn

n+1 

i       r         1

r =      −  , where r is

r−1

 

any real number  except  1 and integer  n ≥ 1.

Let, r = −2.

 

 

n+1

 

−         −                  −

Hence, the sum of 1    2 + 22       23  + . . . + (   1)n 2n = (−2)     −1 (−2)−1

n+1

= (−2)     −1

−3

 

3

∴ Sum

√n

Section 5.3

 

 

Prove  each statement in 21 and 22 by mathematical induction.

 

 

Problem 21

 

 

√

+

√2

√n <   1

1

 1    + . . . +   1    , for all integers  n ≥ 2.

 

Let, n = 2.

√2 < 1 +   1  , since 2 < 1 + √2 + 1 , (√2 > 1)

√2                                                         2

Assume an integer  n > 2 and the result  holds for n − 1,

 

that means √n − 1 < 1 +   1

+ .  .  .  +      1          

 

        √2                 

√n−1

 

√2

So, √n = √n − 1 + √n − √n − 1 < 1 +   1

+ . . . +     1       + √n − √n − 1

 

√   √

Therefore,  this  is enough to prove that √n − √n − 1 <   1     ⇔ 1 <   n+  n−1 ,

√n−1

√n                   √n

since n − 1 = 0. The proof is proven  by induction.

 

 

Problem 22

 

1 + nx ≤ (1 + x)n , for all real numbers  x > −1 and integers  n ≥ 2. (i) n = 2

(1 + x)2   = x2  + 2x + 1 ≥ 2x+1,  since x2  ≥ 0

(ii) n = k

1 + kx ≤ (1 + x)k

(iii) n = k + 1

1 + (k + 1)x ≤ (1 + x)k+1

(1 + x)k+1 = (1 + x)k (1 + x) ≥ (1 + kx)(1 + x)

= kx2  + kx + x + 1 = kx2  + (k + 1)x + 1 ≥ (k + 1)x + 1, since x2  ≥ 0

∴ By the principle  of induction, 1 + nx ≤ (1 + x)n , x > −1, x ∈ R, n ≥ 2, n ∈ N

 

 

 

Section 5.5

 

 

Problem 12

 

n

n!

Let s0 , s1 , s2 , .  .  .  be defined by the  formula  sn = (−1)   (1) for all integers  n

k

≥ 0. Show that this sequence satisfies the recurrence  relation  sk   = −sk−1 .

Let, k ≥ 1 and substitute n = k − 1 into eq(1)

(−1)k−1

 

sk−1 =

(k−1)!   (2)

 

Substitute n = k into eq(1)

 

 

 

k

sk  =  (    1)

−

k!

=  (−1)(−1)

k−1

 

m

n

k(k−1)!      , by using n! = n(n − 1)! and a    · a

k−1

= am+n

 

= −1

(−1)        

 

k    · ( (k−1)!  )

= −1

∴ sk  = −sk−1

k    · sk−1 , from eq(2)

k      , for all integer  values k ≥ 1.

 

 

Problem 28

 

 

In 28 F0 , F1 , F2 , . . . is the Fibonacci  sequence.

 

Prove  that F 2

− F 2 − F 2

= 2Fk Fk

1 , for all integers  k ≥ 1.

 

2

F 2                 2

k+1

2

k       2  k−1    2                −

 

2

k+1 − Fk   − Fk−1  = (Fk+1 − Fk−1 ) − Fk

−        k+1       k−1         k

= (Fk+1 + Fk    1 )(F       − F      ) − F 2 , by using a2  − b

2

= (a + b)(a − b).

 

= (Fk+1 + Fk−1 )(Fk ) − Fk , using Fk  = Fk+1 − Fk−1 , for k ≥ 1.

= Fk [Fk+1  + Fk−1  − Fk ]

= Fk [(Fk+1 − Fk ) + Fk−1 ]

= Fk [Fk−1  + Fk−1 ], by using Fk−1  = Fk+1 − Fk , for k ≥ 1.

= Fk (2Fk−1 )

= 2Fk Fk−1

 

∴ F 2

− F 2 − F 2

= 2Fk Fk

1 , for all integer  values k ≥ 1.

 

k+1         k

k−1                  −

 

 

 

Section 5.6

 

 

Problem 15

 

 

Question  15 is a sequence defined recursively.  Use iteration to guess an explicit formula  for the  sequence.   Use the  formulas  from Section  5.2 to  simplify your answers whenever  possible.

2

yk  = yk−1  + k , for all integers  k ≥ 2,

y1  = 1.

Plug in k = 2, 3, 4… into equation  to get terms  in the sequence

y2  = y1  + 22

= 1 + 22  , by using y1  = 1

= 12 + 22

y3  = y2  + 32

= 12 + 22 + 32 , by using y2  = 12 + 22

y4  = y3  + 42

= 12 + 22 + 32 + 42 , by using y3  = 12 + 22 + 32

y5  = y4  + 52

= 12 + 22 + 32 + 42 + 52 , by using y4  = 12 + 22 + 32 + 42

y6  = y5  + 62

 

 

 

 

 

 

= 12 + 22 + 32 + 42 + 52 + 62 , by using y5  = 12 + 22 + 32 + 42 + 52

and so on…

6

Sum of the squares  of integer  numbers  is 12 + 22 + 32 + … + n2  = n(n+1)(2n+1) .

Now, the nth term  will be:

6

yn = 12 + 22 + 32 + 42 + … + n2  = n(n+1)(2n+1)

6

Hence, the explicit formula for the sequence is: yn = n(n+1)(2n+1) , for all n ≥ 1.

 

 

Problem 46

 

 

Question  46 is a  sequence  defined  recursively.    (a)  Use iteration to  guess an explicit  formula  for the  sequence.   (b)  Use strong  mathematical induction to verify that the formula  of part  (a) is correct.

sk   = 2sk−2 , for all integers  k ≥ 2,

s0  = 1, s1  = 2.

Let, k = 2 in the recurrence  relation

s2  = 2S0  = 2 · 1, since s0  = 1

s2  = 2.

Let, k = 3

s3  = 2S1  = 2 · 2, since s1  = 2

s3  = 4.

Let, k = 4

s4  = 2S2  = 2 · 2, since s2  = 2

s4  = 4.

Let, k = 5

s5  = 2S3  = 2 · 4, since s3  = 4

s5  = 8.

Let, k = 6

s6  = 2S4  = 2 · 4, since s4  = 4

s6  = 8.

Let, k = 7

s7  = 2S5  = 2 · 8, since s5  = 8

n

s7  = 16.

Therefore,  we can assume that (1) sn = 2( 2 )

Must  prove formula  above is true  for n = 1

LHS of (1) = s1  = 2, by looking above

 

2 )

2

2

RHS of (1) = 2( 1

= 21

= 2, since (

1 ) = (1

− 1 ) = 1

 

Since, LHS = RHS for n = 1, the result  is valid for n = 1.

(2) Must  now prove equation  is true  for any integer  ”i”, and all integers  ”k”. Let, 0 ≤ i ≤ k and let equation  be true  for n = i

 

2 )

si = 2( i

, inductive  hypothesis

 

Prove  for n = k by using recurrence  relation  sk  = 2 · sk−2

k−2

 

k = 2 · 2(

2   ) , by using inductive  hypothesis  above

 

 

 

 

 

 

 

=

(2 · 2

 

−

k   2

2          from inductive  hypothesis

 

k

2 · 2 2 −1      if k is odd

 

=

k

(2

2       if k is even

k

2 2       if k is odd

 

k

∴ 2sn = 2( 2 ) , since the formula  is true  for k.

 

 

 

Section 6.1

 

 

Problem 17

 

 

Consider the Venn diagram  shown below. For each of (a)–(f ), copy the diagram and shade the region corresponding  to the indicated  set.

1. A ∧ B
2. B ∨ C
3. Ac
4. A – (B ∨ C)
5. (A ∨ B)c
6. Ac ∧ Bc

 

 

I will use the letter  ”S” in the region where there  is supposed  to be shading. a.

U           A          B

 

S

 

S

 

 

C

 

 

b.

 

 

 

 

 

 

U           A          B

 

S      S

 

S

S           S

 

S     S     C

 

 

1. (everything except entire circle A)

U           A          B           S

 

S

S

 

S

 

S S              S     S     C

 

 

 

d.

U           A          B

 

S  S

 

 

 

 

C

 

 

1. (everything except circles A and B)

U           A          B           S

 

S

 

 

 

 

C

S                      S     S           S S

 

1. (A ∨ B)c = Ac  ∧ Bc , by DeMorgan’s Laws

Therefore  parts  ”e” and ”f” are the equal.

 

 

 

 

 

 

U           A          B           S

 

S

 

 

 

 

C

S                      S     S           S S

 

 

 

 

Problem 23

 

Let Vi  = {x ∈ R | − 1  ≤ x ≤ 1 } = [− 1 , 1 ], for all positive  integers  i.

 

i

4

1. S Vi = [−1, 1]

i=1

4

1. T Vi = [− 1 , 1 ]

i             i   i

 

4    4

i=1

1. Are V1, V2, V3 , . . . mutually disjoint?  Explain.

No, they are not mutually disjoint since [− 1 , 1 ] is contained within  the interval

4    4

[−1, 1].

n

1. S Vi = [−1, 1]

i=1

n

1. T Vi = [− 1 ,  1 ]

n  n i=1

S∞

 

f.

i=1

Vi  = [−1, 1]

 

T V   = [     1      1

∞

1. i      −  ,    ] = 0

i=1            ∞  ∞

 

 

 

Section 6.2

 

 

Use an element  argument  to prove  the  statement in 14.  Assume  that all sets are subsets  of a universal  set U.

 

 

Problem 14

 

 

For all sets A, B, and C, if A ⊆ B then  A ∨ C ⊆ B ∨ C. Suppose A, B, and C are sets and A ⊆ B.

 

 

 

 

 

 

Let x ∈ A ∨ C , then  by the definition  of union:  x ∈ A or x ∈ C . In the case of x ∈ A:

Here x ∈ B as A ⊆ B.

Therefore,  it is true  that x ∈ B or x ∈ C .

Hence, by the definition  of the union:  x ∈ B ∨ C . In the case of x ∈ C :

For, x ∈ B, then  it is true  that x ∈ B or x ∈ C .

Hence, by the definition  of union:  x ∈ B ∨ C . Therefore,  in either  of the above cases, x ∈ B ∨ C .

∴ for A ⊆ B, A ∨ C ⊆ B ∨ C is valid.

 

 

 

Section 6.3

 

 

In  37 and  38,  construct an  algebraic  proof  for the  given  statement.   Cite  a property from Theorem  6.2.2 for every step.

 

 

Problem 37

 

For all sets A and B, (Bc  ∨ (Bc  − A))c   = B. Let A, B, and C be any set.

(Bc  ∨ (Bc  − A))c   = (Bc  ∨ (Bc  ∧ Ac ))c , by the Difference Law

= (Bc )c  ∧ (Bc  ∧ Ac )c , by DeMorgan’s Law

= (Bc )c  ∧ (Bc )c  ∨ (Ac )c , by DeMorgan’s Law

= B ∧ (B ∨ A), by Double Complement Law

= B, by Absorption Law

∴ (Bc  ∨ (Bc  − A))c   = B is valid.

 

 

Problem 38

 

For all sets A and B, A − (A ∧ B) = A − B. Let, A and B be any two sets

A − (A ∧ B) = A ∧ (A ∧ B)c , by Set Difference Law

= A ∧ (Ac  ∨ Bc ), by DeMorgan’s Law

= (A ∧ Ac ) ∨ (A ∧ Bc ), by the Distributive Law

= φ ∨ (A − B), by the Complement Law and Set Difference Law

= A − B, by the Identity Law

∴ A − (A ∧ B) = A − B, is valid.