Discrete Structures

# HW #11 — §4.1: Mathematical Induction

 Last Update: 19 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 #11" AT TOP RIGHT OF EACH PAGE; STAPLE MULTIPLE PAGES

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

pp. 279–280: 4 a–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: 10 a–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, FRI., DEC. 3