LVIII OM - I - Problem 4

For each natural number $ n\ge 3 $, determine the number of sequences $ (c_1,c_2,\ldots,c_n) $, where $ {c_i\in\{0,1,\ldots,9\}} $, with the following property:\break in every triple of consecutive terms, there are at least two terms that are equal.
Let $ z_n $ be the number of $ n $-term sequences having the desired properties (we will further call them {\it good} sequences). Let $ x_n $ be the number of good sequences $ (c_1,c_2,\ldots,c_n) $, whose last two terms $ c_{n-1} $ and $ c_n $ are equal, and let $ y_n $ denote the number of good sequences $ (c_1,c_2,\ldots,c_n) $, in which $ c_{n-1}\ne c_n $. Of course, the equation $ z_n=x_n+y_n $ is satisfied. 
Every good $ (n+1) $-term sequence $ (c_1,c_2,\ldots,c_{n+1}) $, in which the last two terms $ c_n $ and $ c_{n+1} $ are equal, arises from exactly one good sequence $ (c_1,c_2,\ldots,c_n) $ by adding the condition $ c_{n+1}=c_n $. Therefore, the following relationship holds:






On the other hand, a good $ (n+1) $-term sequence $ (c_1,c_2,\ldots,c_{n+1}) $, in which the last two terms $ c_n $ and $ c_{n+1} $ are different, can be obtained in two ways. In the first way, we take a good $ n $-term sequence $ (c_1,c_2,\ldots,c_n) $, in which $ c_{n-1}=c_n $, and take $ c_{n+1} $ to be any number from the set $ \{0,1,\ldots,9\} $ different from $ c_n $. This way we will obtain $ 9x_n $ different good $ (n+1) $-term sequences. In the second way, we choose a good $ n $-term sequence $ (c_1,c_2, \ldots,c_n) $, in which $ c_{n-1}\ne c_n $ and set $ c_{n+1}=c_{n-1} $. This time we will obtain $ y_n $ different sequences. Moreover, no sequence can be obtained in both ways. It follows that the following equation holds:






From equations (1) and (2) we get






for $ n=4,5,6,\ldots $. We will now apply the method of solving linear recurrences (see  L Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego, Warszawa 2000, Appendix A, p. 103). The characteristic equation of recurrence (3) is $ t^2=2t+8 $, which has two distinct real roots: $ t=4 $ and $ t=-2 $. Therefore, there exist real numbers $ a $, $ b $, such that the following equation holds:






To complete the solution, it remains to determine the values of $ a $, $ b $. For this purpose, we will calculate the numbers $ z_3 $, $ z_4 $. From equations (1) and (2) it follows that






The number of good sequences $ (c_1,c_2,c_3) $, in which $ c_2=c_3 $, is $ 10^2=100 $, since the values of $ c_1 $, $ c_2 $ can be chosen arbitrarily, while the number of good sequences $ (c_1,c_2,c_3) $, in which $ c_2\ne c_3 $, is $ 2\cdot 10\cdot 9=180 $, because the pair of different numbers $ (c_2,c_3) $ can be chosen arbitrarily and $ c_1 $ must be equal to $ c_2 $ or $ c_3 $. Therefore,






Combining the values calculated above with condition (4) we obtain the system of equations






whose solution are the numbers $ a=b=5 $.
Answer: The sought number of sequences is $ 5\cdot(4^n+(-2)^n) $.
Note: After obtaining dependencies (1) and (2), the solution of the problem can be completed without using the method of solving linear recurrences (although this requires guessing the correct coefficients). Namely, from dependencies (1) and (2) we get






Assuming now the notation






we have therefore






We also calculate that $ x_3=100 $, $ y_3=180 $, so $ u_3=480 $, $ v_3=120 $; therefore, from dependency (5) by induction we obtain the formulas






Hence, ultimately,

















The final answer is: The sought number of sequences is $ 5\cdot(4^n+(-2)^n) $.