Final answer:
To find a recursion for the number of n-digit ternary sequences avoiding '012', consider the last two digits and apply restrictions accordingly, leading to T(n) = 2T(n-1) - T(n-3) with base cases T(1)=3, T(2)=9, and T(3)=26.
Step-by-step explanation:
The student is asking to find a recursion for the number of n-digit ternary sequences that avoid the specific pattern '012'. A ternary sequence is one where each digit can be a 0, 1, or 2. To create a recursion, we need to consider how we can construct such sequences without ending in '012'. We'll define the number of valid sequences of length n as T(n).
Let's start by defining the base cases. For n=1 and n=2, it is clear that there are no restrictions as the sequence is too short to contain '012', therefore T(1) = 3 and T(2) = 9. For n>2, we have to consider the last two digits:
-
- If the last digit is '2', the previous one can't be '1', making two choices for the second to last digit and T(n-1) choices for the rest.
-
- If the last digit is '1', any digit can precede it, giving us T(n-1) choices for the rest.
-
- If the last digit is '0', again any digit can precede it, giving us T(n-1) choices for the rest.
However, in the first and third cases, we cannot have the sequence ending in '10' or '00' as it would allow a '012' to be formed if the next digit is '2' or '1' respectively. Taking all this into account, a recursive formula can be expressed as T(n) = 2T(n-1) - T(n-3), with the initial conditions of T(1) = 3, T(2) = 9, and T(3) = 26 (since '012' is the only invalid 3-digit sequence out of the 27 possible).