Bài toán: 
Từ các chữ số $1, 3, 5, 9$ có thể lập được bao nhiêu số tự nhiên 2014 chữ số và chia hết cho 3.

Hướng dẫn giải.

Cách 1:
Gọi $a_n$ là số các số tự nhiên chia hết cho 3 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$; $b_n$ là số các số tự nhiên chia 3 dư 1 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$ và $c_n$ là số các số tự nhiên chia 3 dư 2 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$. Dễ thấy $a_1=2;\,b_1=c_1=1$.

Một số tự nhiên chia hết cho 3 và có $n+1$ chữ số lập ra từ các chữ số $1, 3, 5, 9$, chỉ có 3 cách tạo như sau:

1. Thêm chữ số 3 hoặc 9 vào cuối số tự nhiên chia hết cho 3 và có $n$ chữ số lập ra từ các chữ số $1, 3, 5, 9$. Trường hợp này có $2a_n$ khả năng.
2. Thêm chữ số 5 vào cuối số tự nhiên chia 3 dư 1 và có $n$ chữ số lập ra từ các chữ số $1, 3, 5, 9$. Trường hợp này có  $b_n$ khả năng.
3. Thêm chữ số 1 vào cuối số tự nhiên chia 3 dư 2 và có $n$ chữ số lập ra từ các chữ số $1, 3, 5, 9$. Trường hợp này có $c_n$ khả năng.

Ta được công thức truy hồi $$a_{n+1}=2a_n+b_n+c_n.$$
Mặt khác, $a_n+b_n+c_n=4^n$ vì đó là số cách tạo nên một số có $n$ chữ số từ $1, 3, 5, 9$, do đó $${a_1} = 2;\,\,{a_{n + 1}} = {a_n} + {4^n} = {a_1} + 4 + 4^2 + \ldots + {4^n} = \frac{{{4^{n + 1}} + 2}}{3}.$$

Từ đó ta suy ra kết quả cần tìm là $\frac{4^{2014}+2}{3}$.

Cách 2: 
Một số tự nhiên chia hết cho 3 khi và chỉ khi tổng các chữ số của nó chia hết cho 3.
Xét đa thức
$ P(x) = (x + x^3 + x^5 + x^9)^{2014} =\sum x^{a_1+a_2+...+a_{2014}} $ trong đó $ a_i \in \{1, 3, 5, 9\}$. Số các số có 2014 chữ số lập từ các chữ số 1, 3, 5, 9 và chia hết cho 3, kí hiệu là $S_{2014}$, bằng tổng các hệ số của các số mũ chia hết cho 3 của P(x).

Đặt
$$\epsilon= \cos \frac{{2\pi }}{3} + i\sin \frac{{2\pi }}{3}.$$

Ta có $\epsilon^3 = 1$ và $\epsilon^2+\epsilon +1=0$ và $P(1)+P(\epsilon)+P(\epsilon)=3S$.

Từ $ P(1) = 4^{2014}, P(\epsilon) = 1, P(\epsilon^2) = 1$ kết quả cần tìm là $ S= \frac{4^{2014}+2}{3}$.

Một số bài tập tương tự

1. Có bao nhiêu số tự nhiên khác nhau nhỏ hơn 2.10^8, chia hết cho 3, có thể được viết bởi các chữ số 0, 1, 2.
2. (PTNK 2009) Có bao nhiêu số tự nhiên gồm n chữ số được lập từ các chữ số:3,4,5,6 và chia hết cho 3.
3. Có bao nhiêu số có 6 chữ số không chứa số 0 và chia hết cho 7.
4. Có bao nhiêu số có n chữ số được lập từ các chữ số 1, 3, 4, 6, 7, và 9 có tổng các chữ số chia hết cho 7.
5. (ĐH Huế 2000) Có bao nhiêu số có 3 chữ số khác nhau chia hết cho 9. Có bao nhiêu số có 5 chữ số khác nhau chia hết cho 9.
6. Có bao nhiêu số có 9 chữ số không chứa số 0 và chia hết cho 11.