Đáp án đúng: DLet $u_n$ be the number of sequences of length $n$ satisfying the given conditions. We consider the last element $a_n$.
If $a_n = 0$, then $a_{n-1}$ must be different from 0. The number of choices for the first $n-1$ elements is $u_{n-1} - $(number of sequences ending in 0). That is $u_{n-1} - u_{n-2}$.
If $a_n = 1$, then $a_{n-1}$ must be different from 1. The number of choices for the first $n-1$ elements is $u_{n-1} - u_{n-2}$.
If $a_n = 2$, then the number of choices for the first $n-1$ elements is $u_{n-1}$.
$u_n(i)$ is the number of sequences of length $n$ that ends with $i$, $i \in \{0,1,2\}$.
$u_n = u_n(0) + u_n(1) + u_n(2)$
$u_n(0) = u_{n-1}(1) + u_{n-1}(2)$
$u_n(1) = u_{n-1}(0) + u_{n-1}(2)$
$u_n(2) = u_{n-1}(0) + u_{n-1}(1) + u_{n-1}(2)$
Therefore, $u_n = 2(u_{n-1}(1) + u_{n-1}(0) + u_{n-1}(2)) - u_{n-1}(2) = 2u_{n-1} - u_{n-1}(2) = 2u_{n-1} - u_{n-2}$.
$u_1 = 3$, $u_2 = 7$, $u_3 = 2u_2 - u_1 = 2(7) - 3 = 11$
$u_1 = 3$ (0, 1, 2)
$u_2 = 7$ (02, 10, 12, 20, 21, 22, 01)
$u_3 = 17$ (020, 021, 022, 101, 102, 120, 121, 122, 201, 202, 210, 212, 220, 221, 222, 012, 120)
$u_1 = 3$
$u_2 = 7$
$u_3 = 17$
$u_4 = 41$
$u_5 = 99$
$u_{n+1} = 2u_n - u_{n-1}$.
So $u_3 = 2u_2 - u_1 = 2*7 - 3 = 11$, and $u_n = 2u_{n-1} + u_{n-2}$.
Incorrect equation here
$u_1=3, u_2 = 7, u_3 = 17, u_4=41, u_5 =99$
