Let a[n] be the number of strings of length n on the alphabet {0,1,2} that do not contain the substring 00 (in other words, do not contrain to consecutive 0s).

1- Use a tree to enumerate all strings on {0,1,2} of length 0, 1, 2 and 3 that do not contain 00. What are the values of a0, a1, a2, and a3?

2- Develop a recurrence relation expresing a[n] as a linear combination of a[n-1] and a[n-2] for n >= 2. Write also the initial conditions. (Hint: For a string of length n >= 2, consider two cases: the last character is 0, or not.)

3- Solve the recurrence relation in #2

4- expand the expression found in #3 and manipulate it for eliminating any fraction or square-root, so that nly integers remain.