1. **Problem statement:** We have an alphabet $\Omega = \{X, Y, Z, T, 0, 1, 2, 3, 4, 5, 6, 7\}$ with 12 characters: 4 letters ($X,Y,Z,T$) and 8 digits ($0$ to $7$). A Q-key of length $n$ is a string of $n$ characters from $\Omega$ with no two consecutive digits. We want to find $a_n$, the number of Q-keys of length $n$. Given $a_0=1$ (empty string) and $a_1=12$, we need to: 2. **Calculate $a_2$ using combinatorial argument:** - For length 2, each character can be a letter or digit but no two digits consecutively. - Total pairs: $12 \times 12 = 144$. - Invalid pairs: both characters digits. Number of digit-digit pairs = $8 \times 8 = 64$. - Valid pairs = $144 - 64 = 80$. So, $$a_2 = 80.$$ 3. **Recurrence relation:** - Let $a_n$ be number of Q-keys of length $n$. - Consider Q-keys of length $n-1$ ending with a letter or digit. - Number of letters = 4, digits = 8. - If $k$ ends with a letter, next character can be any of 12 characters. - If $k$ ends with a digit, next character must be a letter (4 options) to avoid consecutive digits. Define: - $L_{n-1}$ = number of Q-keys length $n-1$ ending with a letter. - $D_{n-1}$ = number of Q-keys length $n-1$ ending with a digit. Then: $$a_{n-1} = L_{n-1} + D_{n-1}.$$ Next: - $L_n = 4a_{n-1}$ (append letter to any Q-key of length $n-1$) - $D_n = 8L_{n-1}$ (append digit only to Q-keys ending with letter) So: $$a_n = L_n + D_n = 4a_{n-1} + 8L_{n-1}.$$ But $L_{n-1} = a_{n-2} \times 4$ because to end with letter at $n-1$, the previous step can be any Q-key of length $n-2$ appended by a letter. Hence: $$a_n = 4a_{n-1} + 8 \times 4 a_{n-2} = 4a_{n-1} + 32a_{n-2}.$$ 4. **Solve the recurrence:** Characteristic equation: $$r^2 - 4r - 32 = 0.$$ Solve: $$r = \frac{4 \pm \sqrt{16 + 128}}{2} = \frac{4 \pm 12}{2}.$$ Roots: $$r_1 = 8, \quad r_2 = -4.$$ General solution: $$a_n = A \cdot 8^n + B \cdot (-4)^n.$$ Use initial conditions: - $a_0 = 1 = A + B$ - $a_1 = 12 = 8A - 4B$ From $a_0$: $$B = 1 - A.$$ Substitute into $a_1$: $$12 = 8A - 4(1 - A) = 8A - 4 + 4A = 12A - 4.$$ So: $$12 + 4 = 12A \Rightarrow 16 = 12A \Rightarrow A = \frac{4}{3}.$$ Then: $$B = 1 - \frac{4}{3} = -\frac{1}{3}.$$ Final formula: $$a_n = \frac{4}{3} \cdot 8^n - \frac{1}{3} \cdot (-4)^n.$$ 5. **Verify for $n=2$:** $$a_2 = \frac{4}{3} \cdot 8^2 - \frac{1}{3} \cdot (-4)^2 = \frac{4}{3} \cdot 64 - \frac{1}{3} \cdot 16 = \frac{256}{3} - \frac{16}{3} = \frac{240}{3} = 80,$$ which matches the combinatorial result. **Answer:** $$a_n = \frac{4}{3} \cdot 8^n - \frac{1}{3} \cdot (-4)^n.$$