Discrete Structures

HW #10

 Last Update: 3 April 2009 Note: or material is highlighted

Reminder: Each HW problem solution should consist of:

• a restatement of the entire problem (you may copy it word for word),
• followed by a complete solution with all intermediate steps shown.

Exercises are from §4.1, pp. 279-282 (mathematical induction).

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

pp. 279-280: 4a-f

• This problem leads you through the steps of an inductive proof.

2. (12 points)

p. 280: 6

• This asks you to do an inductive proof, but doesn't lead you through it.
But you should follow the general strategy of the previous problem and as suggested in the grading scheme below:

• statement of base case: 3 points
proof of base case: 3 points
statement of inductive case: 3 points
proof of inductive case: 3 points

3. (18 points)

p. 280: 10a-b

• Part (a) asks you to find a formula for a summation.

Do this as follows:

• Make a 2-column table with one column for n and one column for the value of the summation.
• Fill it out for n ∈ {1, …, 5}.
• Then look for a pattern that will give you the desired formula.

• (3 points for the table; 3 points for the formula)

• Part (b) asks you to use mathematical induction to prove that your formula is correct.

• 3 points for statement of base case; 3 points for its proof;
3 points for statement of inductive case; 3 points for its proof

4. (12 points)

p. 280: 16

• Another inductive proof.
• 3 points for statement of base case; 3 points for its proof;
3 points for statement of inductive case; 3 points for its proof

5. (12 points)

p. 282: 56

• This asks you to give an inductive proof for a theorem in propositional logic.

• 3 points for statement of base case; 3 points for its proof;
3 points for statement of inductive case; 3 points for its proof

Total points = 72

```A       69 - 72
A-      65 - 68
B+      61 - 64
B       57 - 60
B-      53 - 56
C+      49 - 52
C       41 - 48
C-      33 - 40
D+      25 - 32
D       13 - 24
F        0 - 12
```

 DUE: AT THE BEGINNING OF LECTURE, FRIDAY, APRIL 10

 REMINDER:NAME, DATE, RECITATION SECTION AT TOP RIGHT OF EACH PAGE;         STAPLE MULTIPLE PAGES