Homework #2 Solution

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.

a. A ∧ B

b. B ∨ C

c. Ac

d. A - (B ∨ C)

e. (A ∨ B)c

f. 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







c. (everything except entire circle A)

U A B S




S

S




S




S S S S C










d.

U A B




S S













C







e. (everything except circles A and B)

U A B S




S













C

S S S S S




f. (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

a. S Vi = [−1, 1]

i=1

4

b. T Vi = [− 1 , 1 ]

i i i
4 4

i=1

c. 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

d. S Vi = [−1, 1]

i=1

n

e. T Vi = [− 1 , 1 ]

n n i=1

S∞
f.

i=1

Vi = [−1, 1]
T V = [ 1 1

∞

g. 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.