VMO

Denote by $S=\{2,0,1,5\}$ and $$A(n,i)=\{\overline{x_n{x}_{n-1}\dots x_1}:x_j\in S\text{ and }{x}_1+\cdots +x_n\equiv i(\mathrm{mod}3)\}.$$ Let $a_n,b_n$ and $c_n$ be the cardinal number of $A(n,0)$, $A(n,1)$ and $A(n,2)$ respectively. Since a natural number is divisible by $3$ if and only if the sum of its digits is a multiple of $3$, we only need to count the number of elements in the set $A(k,0)$. Let $\overline{x_1\dots x_{n+1}}$ be an element of $A(n+1,0)$, we have

If $x_{n+1}=0$ then $(x_1,x_2,\dots ,x_n)\in A(n,0)$. If $x_{n+1}=2$ or $5$ then $(x_1,x_2,\dots ,x_n)\in A(n,1)$. If $x_{n+1}=1$ then $(x_1,x_2,\dots ,x_n)\in A(n,2)$.

Hence, $a_{n+1}=a_n+2b_n+c_n$ (1). Similarly, we get $$b_{n+1}=a_n+b_n+2c_n,(2)$$ $$c_{n+1}=2a_n+b_n+c_n.(3)$$ From those equations, we have $a_2=5$, $b_2=6$, $c_2=5$, $a_3=22$, $b_3=21$, $c_3=21$. Moreover, $$a_{n+1}-b_{n+1}=a_n+2b_n+c_n-a_n-b_n-2c_n=b_n-c_n,$$ $$b_{n+1}-c_{n+1}=a_n+b_n+2c_n-2a_n-b_n-c_n=c_n-a_n,$$ $$c_{n+1}-a_{n+1}=c_{n+1}-b_{n+1}+b_{n+1}-a_{n+1}=a_n-b_n.$$ This leads to $$a_{n+3}-b_{n+3}=b_{n+2}-c_{n+2}=c_{n+1}-a_{n+1}=a_n-b_n.$$ Similarly, $$b_{n+3}-c_{n+3}=b_n-c_n,c_{n+3}-a_{n+3}=c_n-a_n.$$ Hence, it is easy to see that If $k\equiv 0(\mathrm{mod}3)$ then $b_k=c_k=a_k-1$. If $k\equiv 1(\mathrm{mod}3)$ then $a_k=b_k=c_k-1$. If $k\equiv 2(\mathrm{mod}3)$ then $a_k=c_k=b_k-1$.

On the other hand, $a_k+b_k+c_k$ is equal to the cardinal number of $A(k)=\{\overline{a_k{a}_{k-1}\dots a_1}:a_j\in S\}$ so that $$a_k+b_k+c_k=4^k.$$ In conclusion, the value of $a_k$ is $a_k=\frac{4^k-1}{3}$ if $k$ is not a multiple of $3$; $a_k=\frac{4^k+2}{3}$ if $k$ is a multiple of $3$.