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 

(3 points each; total = 18 points)
pp. 279–280: 4 a–f
 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: 10 a–b
 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, FRI., DEC. 3 
Text copyright © 2010 by William J. Rapaport
(rapaport@buffalo.edu)
Cartoon links and screencaptures appear here for your enjoyment.
They are not meant to infringe on any copyrights held by the creators.
For more information on any cartoon, click on it, or contact me.
http://www.cse.buffalo.edu/~rapaport/191/F10/hw11.html20101114