5. For each of the following, find a recurrence relation and initial conditions

that defines the given sequence.

(a) an, n >= 0, the number of n digit numbers, without leading zeros,

that do not contain 00.

(b) bn, n >= 0, the number of n digit numbers, without leading zeros,

that contain 00.

(c) cn, n >=1, the number of ways it is possible to climb a staircase of n

stairs if, on each stride, you go up 1, 2, or 3 steps.