Discrete Structures

# HW #10 — §§2.3–2.4: Functions, Sequences, & Summations

 Last Update: 13 November 2010 Note: or material is highlighted

All exercises come from, or are based on exercises from, the Rosen text.

Each HW problem's solution should consist of:

All solutions must be handwritten.

 PUT YOUR NAME, DATE, RECITATION SECTION, & "HW #10" AT TOP RIGHT OF EACH PAGE; STAPLE MULTIPLE PAGES

1. (3 points each; total = 9 points)

p. 146: 12 a–c

• You are given some functions and asked to determine which are 1–1.

2. (3 points each; total = 9 points)

pp. 146–147: 14 a, c, e

• You are given some functions and asked to determine which are onto.

3. (3 points each; total = 6 points)

p. 147: 32

• You are given 2 functions and asked to compute both ways of composing them with each other.
• For full credit, you must show all your work.

4. (6 points)

p. 148: 68.

• You are asked to prove that a certain kind of function is 1–1 iff it is onto.
• Hint: Use the definitions of "1–1" and of "onto" together with the fact that:
if |A| = |B|, then:
if a function from one of these to the other is not 1–1 or not onto, then |A| ≠ |B|.

5. (3 points)

p. 149: 74a

• Be sure to read the section on partial functions on p. 149, column 1, starting immediately after problem 72 and ending at the end of the column.

• You should probably try to do problems 73a,c–e and check your answers before attempting problem 72.

• You are asked to prove that a partial function (i.e., a function that is not defined on some elements of its domain) can be "extended" to a total function by assigning an arbitrary image to each element for which it is not defined.
• Hint: All you have to do is show that f* satisfies the definition of a function.

6. (3 points each; total = 9 points)

p. 161: 4 a–b, d

• For 3 sequences, you are asked to compute the first 4 terms.

7. (3 points)

List the first 10 terms of the sequence {an} whose first two terms are a0 = –3 and a1 = 2, and which is such that each succeeding term is the sum of the two previous terms.

• I.e., an+2 = an + an+1

8. (3 points)

p. 161: 16a

• You are asked to compute the value of a summation (a.k.a., a "series"), i.e., to compute the sum of the terms of a sequence.
• Hint: Compute the terms of the sequence, and then add them up!

Total points = 48

```A       46-48
A-      44-45
B+      41-43
B       38-40
B-      36-37
C+      33-35
C       28-32
C-      22-27
D+      17-21
D        9-16
F        0- 8
```

 DUE: AT THE BEGINNING OF LECTURE, FRI., NOV. 19