Math 221 Week 2 Assignment

Week 2 Assignment

September 13, 2013

Week 2 Assignment

Chapter 4

Exercise 4.1

2. Establish each of the following for all n ≥ 1 by the Principle of Mathematical Induction.

a) i=1n2i-1=i=0n-12i= 2n-1

b) i=1ni2i=2+n-12n+1

c) i=1nii!=n+1!-1

Answer:

A) Basis step: n=1 ,then 20=21-1, so 1=1 and we know the basis step is true.

Inductive: n=k , then

i=0k-12i=2k-1

i=0k2i= i=0k-12i+2k=2k-1+sk=2k+1-1

True for inductive

B) Basis Step: n=1, then 1*21=2+1-121+1, so 2=2 and we know the basis step is true.

Inductive : n=k, then

i=1k+1i2i=2+k+1-12k+1+1

i=1k+1i2i= i=1ki2i+k+12k-1=2+k-12k+1+k+12k+1=2+2k+1 k-1+k+1=2+2k+12k=2+k*2k+2=True

C) Basis Step: n=1, then 1*1!=(1+1)!-1, so 1=1 and we know basis is true.

Inductive : n=k then;

i=1k+1ii!= k+1+1!-1

i=1k+1ii!= i=1kii!+k+1k+1!=k+1!-1+k+1k+1!=k+1!*1+k+1-1=k+1!*k+2-1=k+2!-1=True

18. Consider the following four equations:

1) 1 = 1

2) 2 + 3 + 4 =1 + 8

3) 5 + 6 + 7 + 8 + 9 = 8 + 27

4) 10 + 11 + 12 + 13 + 14 + 15 + 16 =27 + 64

Conjecture the general formula suggested by these four equations, and prove your conjecture.

Answer: The left hand side of the equation is the sum of positive integers from

n-12+1 to n2 and the right side is n-13+n3if this stays the same then the conjecture of the equation is

k=n-12+1n2k= n-13+n3

Using Induction to prove:

k=n-12+1n2k= k=1n2k- k=1n-12k=12n2 n2+1-n-12n-12+1=2n3-3n2+3n-1=n3-3n2+3n-1+n3=n-13+n3=True

Exercise 4.2

5.

a) Give a recursive definition for the intersection of the sets A1, A2, . . . , An, An+1 ⊆ μ, n ≥ 1.

b) Use the result in part (a) to show that for all n, r ∈Z+ with n ≥ 3 and 1 ≤ r < n,

(A1 ∩ A2 ∩ ・ ・ ・ ∩ Ar ) ∩ (Ar+1 ∩ ・ ・ ・ ∩ An)

= A1 ∩ A2 ∩ ・ ・ ・ ∩ Ar ∩ Ar+1∩ ・ ・ ・ ∩ An.

Answer:

a) Intersection of A1 , A2 is A1 ∩ A2. The intersection of the two sets is A1 , A2… An , An+1is (A1 ∩ A2∩… ∩An) ∩ An+1

b) If r=k and for 1 ≤ r < k , the equation is:

A1 ∩ A2∩… ∩Ar∩ (Ar+1 ∩ A2∩… ∩Ak ∩ Ak+1)...