Arithmetic Sequence

Bài toán : Cho dãy $(u_{n})$ thỏa mãn :

${u_{1} = 1, u_{2} = 2 u_{n + 2} = 3 u_{n + 1} + u_{n}, \forall n \geq 1$

Với mỗi số nguyên dương $n$ ta gọi $r_{n}$ là số dư khi chia $u_{n}$ cho $2013$ . Chứng minh rằng dãy $(r_{n})$ là dãy tuần hoàn.

Lời giải :

Dãy số $(r_{n})$ có công thức :

${r_{1} = 1, r_{2} = 2 r_{n + 2} \equiv 3 r_{n + 1} + r_{n} (m o d 2013)$

Xét dãy các bộ hai số :

$(r_{1}, r_{2}), (r_{2}, r_{3}), ...., (r_{n}, r_{n + 1}), (r_{n + 1}, r_{n + 2}), ...$

Dãy trên có vô số bộ nhưng do $r_{n} \in {1, 2, ..., 2012, 2013}$ với mọi $n$ nên chỉ có hữu hạn bộ đôi một khác nhau. Vì vậy theo nguyên lí Dirichlet sẽ tồn tại hai bộ trùng nhau. Nghĩa là tồn tại các số nguyên dương $m, k$ sao cho :

$(r_{m + 1}, r_{m + 2}) = (r_{m + k + 1}, r_{m + k + 2})$

Từ đó ta có :

$r_{m} \equiv - 3 r_{m + 1} + r_{m + 2} = - 3 r_{m + k + 1} + r_{m + k + 2} \equiv r_{m + k} (m o d 2013)$

$r_{m - 1} \equiv - 3 r_{m} + r_{m + 1} = - 3 r_{m + k} + r_{m + k + 1} \equiv r_{m + k - 1} (m o d 2013)$

$...$

$r_{1} \equiv - 3 r_{2} + r_{3} = - 3 r_{k + 2} + r_{k + 3} \equiv r_{k + 1} (m o d 2013)$

Như vậy ta có :

$(r_{1}, r_{2}) = (r_{k + 1}, r_{k + 2})$

Lại kết hợp với :

$r_{n + 2} = 3 r_{n + 1} + r_{n} (m o d 2013)$

Ta chứng minh được :

$r_{n} = r_{n + k}, \forall n \in Z^{+}$

Từ đó dãy $(r_{n})$ là dãy tuần hoàn.

Bài toán trên chỉ là một trường hợp cụ thể của “Định lí tuần hoàn của dãy số dư” có nội dung như sau :

Xét dãy số $(a_{n})$ :

${a_{1}, a_{2}, ..., a_{k} \in Z a_{n + k} = A_{1} a_{n + k - 1} + A_{2} a_{n + k - 2} + ... + A_{k} a_{n}$

Với $A_{i}$ là các số nguyên. Khi đó với số nguyên dương $X$ bất kì, dãy số dư của $(a_{n})$ theo modulo $X$ là dãy tuần hoàn.

Arithmetic Sequence

Đề bài

Mô tả