Asmall combination lock on a suitcase has 55 wheels, each labeled with the 10 digits 0 to 9. how many 55 digit combinations are possible if successive digits must be different?

Suppose is the number of possible combinations for a suitcase with a lock consisting of wheels. If you added one more wheel onto the lock, there would only be 9 allowed possible digits you can use for the new wheel. This means the number of possible combinations for wheels, or is given recursively by the formula



starting with (because you can start the combination with any one of the ten available digits 0 through 9).

For example, if the combination for a 3-wheel lock is 282, then a 4-wheel lock can be any one of 2820, 2821, 2823, ..., 2829 (nine possibilities depending on the second-to-last digit).

By substitution, you have



This means a lock with 55 wheels will have



possible combinations (a number with 53 digits).