[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.

2 thoughts on “[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”

  1. Bài 1 em thấy nếu bổ sung F_o=0 thì kết quả sẽ rõ ràng hơn. Hình như còn có một chặn trên khá tốt, nhỏ hơn 10^8, chứng minh bằng cách xét theo mũ 5 của F_{5n} và F_n.

  2. Bài 1 này dùng một vòng For trong Pascal sẽ ra kết quả chính xác luôn.😛 Anh đi ngủ đây. Bb

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s