COS 341, October 15, 1997Handout Number 10
Homework Set 5
Reading Assignments Read Chapter 11.
Written Assignments Do exercises 1, 7 and 11 in Section 7.8.
Special Problem 1 (to be counted as 1 exercise) Let n be any positive integer. Evaluate
Your answer should be a closed-form expression of n.
Special Problem 2 (to be counted as
1 exercise) Let n>1 be any integer. The road map of a
certain town forms a
grid
(two East-West streets of length (n-1) each, and
n North-South streets of length 1 each).
All the roads are two-way. If you want to go
from the south-west corner point Q to
the north-east corner point W, how many different routes can
you take without traversing the same segment twice? Give
your answer as a closed-form expression of n.
Remarks Let g(n) be this number. Then g(2)=2, g(3)=4.
Special Problem 3 (counted as 1 exercise)
Solve the following
recurrence relation: 
, and for n>1,
