2. (10 points) Recall the problem from Homework #1, where Dorothy is trying to
walk from Munchkin Country to the Emerald City in OZ. Assume that Munchkin
Country is still located at the point (0,0) in the usual coordinate plane, but now OZ
is located at the point (n, n) in the first quadrant of the plane, where n is a positive
integer. Since Dorothy is in a hurry she intends to only take East-bound steps or
North-bound steps. An East-bound step takes you from (x, y) to (x + 1, y) and a
North-bound step takes you from (x, y) to (x, y + 1). Dorothy has learned that the
Wicked Witch of the West is waiting for her somewhere above the line y = x in
the first quadrant. If Dorothy never goes above the line y = x, how many different
paths can she take from Munchkin Country to the Emerald City? I want you to
come up with a recurrence relation for these paths and explain how this recurrence
relation is the same as one you saw in this section. This will allow you to say that
these paths have the same enumeration as an object we saw in this section.
