Gọi $a_n$ là số các số có $n$ chữ số lấy từ tập $X$ mà chia hết cho 3. $b_n$ là số các số có $n$ chữ số lấy từ tập $X$ mà chia cho 3 dư 1.
$c_n$ là số các số có $n$ chữ số lấy từ tập $X$ mà chia cho 3 dư 2.
Ta có: $a_1=2,b_1=1,c_1=1$
Có $4^n$ số có $n$ chữ số lấy từ tập $X$ nên suy ra: $a_n+b_n+c_n=4^n$
Từ 1 số có $n$ chữ số lấy từ $X$ mà chia hết cho 3 ta có thể thêm vào bên phải số đó chữ số $3$ hoặc $9$ để được 1 số có $n+1$ chữ số lấy từ $X$ mà chia hết cho 3.
Từ 1 số có $n$ chữ số lấy từ $X$ mà chia cho 3 dư 1 ta có thể thêm vào bên phải số đó chữ số $5$ để được 1 số có $n+1$ chữ số lấy từ $X$ mà chia hết cho 3.
Từ 1 số có $n$ chữ số lấy từ $X$ mà chia cho 3 dư 2 ta có thể thêm vào bên phải số đó chữ số $7$ để được 1 số có $n+1$ chữ số lấy từ $X$ mà chia hết cho 3.
Suy ra: $a_{n+1}=2a_n+b_n+c_n=a_n+4^n$.
Từ đó ta có:
$\displaystyle a_n=\sum_{i=1}^{n-1}(a_{i+1}-a_i)+a_1=\sum_{i=1}^{n-1}4^i+2=\dfrac{4^n+2}{3}$