1. Assume that a bus driver pays all tolls, using only nickels and dimes, by throwing one coin at a time into a mechanical toll collector and a toll is a positive multiple of 5 [cent]. Show how you construct a recurrence system for the number an of different ways the bus driver can pay an exact toll of 5n cents (n 0), where the order in which coins are used matters.

2. Let = {0,1,2} be an alphabet. Show how you derive a recurrence system for the number of ternary strings x that contain two consecutive 0's.