Call a positive integer one-full if it satisfies the following criteria:

(a) Every digit is either 0, 1, or 2.

(b) Out of every two consecutive digits, at least one of them is a 1.

For $n \geq 2$, calculate the number of $n$-digit one-full numbers. (Numbers beginning with the digit 0 are not allowed.)
The answer is $2^{n}$. It is clear that there are four 2-digit one-full numbers: 10, 11, 12, and 21 . To prove that the required number is $2^{n}$ for all $n \geq 3$, it is enough to show that there are twice as many $n$-digit one-full numbers as $(n-1)$-digit one-full numbers for every $n$. Given an ( $n-1$ )-digit one-full number, we construct two different $n$-digit one-full numbers via the following rules:

- If the first digit is 1 , we replace it with 11 and then with 21.
- If the first digit is 2 , we replace it with 12 and then with 10 .

Since 2's and 0's have the same function in the middle of a number, the two numbers that we get using this process are both one-full. Moreover, since any $n$-digit one-full number must begin with one of the four 2 -digit one-full numbers, we can get all $n$-digit one-full numbers in this way. Thus there are twice as many $n$-digit one-full numbers as $(n-1)$-digit ones.