5. For each of the following, fi nd 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.