Có bao nhiêu dãy gồm 5 phần tử a1, a2, a3, a4, a5, trong đó mỗi phần tử lấy giá trị từ {0,1,2} đồng thời không chứa 2 số 0 đứng liền nhau và cũng không chứa 2 số 1 đứng liền nhau?

Let $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$