CSE 321 Assignment #6
Autumn 1998
Due: Friday, November 20, 1998.
Reading assignment: Read the text, Discrete Mathematics and Its Applications,
Sections 4.1-4.5.
The following problems are from the Third Edition of the text.
Problems:
- Suppose that a function T is defined by T(1)=1 and
for n greater than or equal to 1, T(n+1) is
equal to T(n) if n+1 is not divisible by 4 and
is equal to T((n+1)/4) + T((n+1)/2) + n if n+1 is divisible by 4.
Prove that for all n greater than or equal to 1, T(n) is less than or equal to 4n.
- Define a set S of strings by
- Basis: The empty string is in S.
- Constructor: If x and y are in S then 0x11x0 and xy are also in S.
- Nothing is in S other than the strings that can be derived by starting
with the basis and applying the constructor.
Prove that every string in S has an equal number of 1's and 0's.
- Page 241, Problems 8, 16
- Page 242, Problems 32, 34, 38
- Page 249, Problems 18, 26
- Page 258, Problem 18
- Page 259, Problems 24 (c)(d), 26, 28, 40
- Page 260, Problem 48
- (Bonus) Page 261, Problem 60