Assignment 6: Cardinality; Induction
Due 04.Mar.16 (Tue) 17:00
The
general hw policies
include instructions for proofs-by-induction!
Reading: Rosen 3.2 (summations and cardinality), 3.3 (induction).
- (4pts)
Rosen 3.2, #16.
(4ed: ?? -- let me know)
Summations; see Rosen 3.2 and/or
some summation hints
(ps,
pdf).
- (4pts)
Rosen 3.2, #18.
(4ed: ?? -- let me know)
Double
summations; see Rosen 3.2 and/or
some summation hints
(ps,
pdf).
You should be able do this and the previous problem
w/o brute force
(I.e., you wouldn't be phased
if the indices were 200,300 rather than 2,3.)
- (4pts)
Rosen 3.2, #26.
(4ed: ?? -- let me know)
(Sum of cube roots.)
You may assume that m is a perfect cube.
Hints:
- As always, work out some examples by hand, first.
- Don't get too hung up on Rosen's hint? (It wasn't helpful to me.)
- (1pt extra credit)
Extend the previous problem to when m is not
necessarily a perfect cube.
- (4pts)
Rosen 3.2, #32 a,c,d.
(4ed p.79, #32a,c,d)
(Specific sets countable?)
When countable, be sure to show a correspondence and be sure
it really is one-to-one and onto!
- (5pts)
Rosen 3.2, #36.
(4ed p.80, #36)
(Union of countable sets.)
Give a constructive proof -- an explicit mapping
between sets, and show why it is one-to-one and onto.
2pts max if you don't show one-to-one.
Be careful!
- (4pts)
Rosen 3.3: #10.
(4ed 3.2, #10)
(∑ k*k! = (n+1)!-1.)
- (4pts)
Rosen 3.3, #18.
(4ed 3.2, #18)
(∑k-2 < 2-1/n.)
- (1pt )
Rosen 3.3, #50.
(4ed: ?? -- let me know)
(False proof: sum i = (n+0.5)2/2.
- (2pts)
Rosen 3.3, #52.
(4ed: ?? -- let me know)
(False proof: max(x,y)=n ⇒ x=y)
- (4pts)
Rosen 3.4, #18.
(4ed: ?? -- let me know)
(powers of [1 1 / 1 0].)
See labbies or TAs, or read Rosen, for
matrix multiplication (p.198)
and
the Fibonacci numbers fi (p.259).
- (4pts)
Rosen Chpt 3 Supplementary exercise (p.294), #44.
(4ed: ?? -- let me know) (jigsaw)
Note: strong induction really is relevant here;
if you didn't use it, think about some jigsaw-solving moves that
don't actually correspond to your non-strong apporach.