Final Answer:
The recursion for the number g(n) of ternary strings of length n that do not contain 02 as a substring is:
g(1) = 2
g(2) = 5
g(n) = 2g(n-1) + g(n-2)
Step-by-step explanation:
The base cases are g(1) = 2 and g(2) = 5, which represent the number of strings of length 1 and 2, respectively, that do not contain 02.
The recursive step is g(n) = 2g(n-1) + g(n-2), which means that the number of strings of length n that do not contain 02 is equal to the number of strings of length n-1 that do not contain 02 plus the number of strings of length n-2 that do not contain 02. This is because there are two ways to form a string of length n that does not contain 02:
Append a 1 or 2 to a string of length n-1 that does not contain 02.
Append a 01 to a string of length n-2 that does not contain 02.
Therefore, the recursion g(n) = 2g(n-1) + g(n-2) captures the two ways to form a string of length n that does not contain 02.