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. 279282 (mathematical induction).

(3 points each; total = 18 points)
pp. 279280: 4af
 This problem leads you through the steps of an inductive proof.
 (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
 (18 points)
p. 280: 10ab
 Part (a) asks you to find a formula for a summation.
Do this as follows:
 Make a 2column 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
 (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
 (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
Tentative grading scheme:
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

Copyright © 2009 by
William J. Rapaport
(rapaport@cse.buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/191/S09/hw10.html20090330