[Bài bạn Hoàng Minh Tuấn hỏi] Dãy các số dư của dãy tuyến tính cấp hai


Bài toán. Cho dãy Fibonacci xác định bởi F_1=F_2=1F_{n+2}=F_{n+1}+F_n\forall n\geq 1. Chứng minh rằng trong 100.000.000  số hạng đầu của dãy này có ít nhất một số hạng tận cùng là 4 chữ số 0.

Lời giải. Với mỗi số nguyên dương n, gọi r_n là số dư  của F_n khi chia cho 10^4, như thế ta có 0\leq r_n<10^4\forall n\geq 1. Xét 10^8+1 cặp (r_n,r_{n+1}),n=1,2,\cdots, 10^8+1. Trong các cặp này chắc chắn sẽ có hai cặp bằng nhau, gọi chúng là các cặp ứng với n=xn=y, với x<y. Chú ý là trong dãy r_1,r_2,\cdots cứ khi biết hai số ta sẽ biết được số sau và số trước. Như vậy cặp (1,1) chắc chắn bị lặp. Bài toán được giải.

Các bài toán sau đây được giải với cùng kỹ thuật như trên.

1. Cho dãy (x_n) xác định bởi x_1=43,x_2=142x_{n+1}=3x_{n+1}+x_n\forall n\geq 1. Chứng minh rằng (x_n,x_{n+1})=1\forall n\geq 1 và với mỗi số nguyên dương m tồn tại vô hạn số nguyên dương n sao cho x_n-1x_{n+1}-1 chia hết cho m.

2. Let x_0, x_1, x_2, \cdots be the sequence defined by x_i = 2^i if 0 \leq i \leq 2003, x_i = \sum_{j = 1}^{2004} x_{i - j} if i \geq 2004. Find the greatest k for which the sequence contains k consecutive terms divisible by 2004.

3. Cho dãy số (u_n) xác định bởi u_1=20,u_2=100u_{n+1}=4u_n+5u_{n-1}-1976\forall n\geq 2. Chứng minh rằng có ít nhất một số hạng của dãy chia hết cho 1996.

4. Cho dãy (u_n) xác định bởi u_1=39,u_2=45u_{n+2}=u_{n+1}^2-u_n\forall n\geq 1. Chứng minh rằng có vô hạn số hạng của dãy chia hết cho 1986.