Cho dãy số $\begin{Bmatrix} a_{n} \end{Bmatrix}$ thỏa $a_{1}=30;a_{2}=45;...;a_{n+2}=a_{n+1}^{2}-a_{n}$
Chứng minh tồn tại vô số chỉ số n để $a_{n}\vdots 1995$
Bài viết đã được chỉnh sửa nội dung bởi dark templar: 05-06-2013 - 16:48
Cho dãy số $\begin{Bmatrix} a_{n} \end{Bmatrix}$ thỏa $a_{1}=30;a_{2}=45;...;a_{n+2}=a_{n+1}^{2}-a_{n}$
Chứng minh tồn tại vô số chỉ số n để $a_{n}\vdots 1995$
Bài viết đã được chỉnh sửa nội dung bởi dark templar: 05-06-2013 - 16:48
Cho dãy số $\begin{Bmatrix} a_{n} \end{Bmatrix}$ thỏa $a_{1}=30;a_{2}=45;...;a_{n+2}=a_{n+1}^{2}-a_{n}$
Chứng minh tồn tại vô số chỉ số n để $a_{n}\vdots 1995$
- Xét dãy $b_n$ là dãy được xác định theo quy tắc: $b_n\equiv a_n\ (mod\ k)\ \ ;0\le b_n<k$ với modul $k$ bất kì. Từ công thức của dãy $a_n$ ta có:
$$b_{n+2}\equiv b_{n+1}^2-b_{n}\ (mod\ k)$$
- Ta sẽ chứng minh $b_{n}$ là dãy tuần hoàn với mọi modul $k$. Thật vậy, ta chỉ cần chứng minh tồn tại hai chỉ số $i,j,i<j$ sao cho $b_i=b_j;b_{i+1}=b_{j+1}$ vì khi đó sẽ có $b_{j+2}\equiv b_{j+1}^2-b_{j}\equiv b_{i+1}^2-b_{i}\equiv b_{i+2}\ (mod\ k)$. Tương tự: $b_{j+3}\equiv b_{i+3};b_{j+4}\equiv b_{i+4};...;b_{2j-i-1}\equiv b_{j-1}\ (mod\ k)$, suy ra $b_n$ là dãy tuần hoàn.
- Do chỉ có tối đa $k^2$ cặp giá trị $(b_i;b_{i+1})$ nên nếu ta chọn $k^2+1$ cặp như thế thì theo nguyên lí Đi dép lê sẽ tồn tại hai cặp $(b_i;b_{i+1});(b_j;b_{j+1}): b_i=b_j;b_{i+1}=b_{j+1}$. Tóm lại với mọi modul $k$ thì dãy số dư của $a_n$ theo modul $k$ sẽ tuần hoàn.
Công việc còn lại là cần chỉ ra tồn tại $a_m\vdots 1995$. Rất đơn giản vì $a_3=45^2-30=1995$ luôn rồi $\square$
---------
Hình như bài toán này giải chưa đầy đủ vì chưa biết dãy $a_n$ tuần hoàn từ số hạng thứ mấy thì phải???
Uk nhỉ. Vậy t nghĩ có thể làm lùi như thế này:
---
- Ta đã chọn được các chỉ số $i,j$ sao cho $b_i=b_j;b_{i+1}=b_{j+1}$. Bây giờ ta sẽ chứng minh: $b_{j-1}=b_{i-1}$. Thật vậy:
$$b_{j-1}-b_{i-1}\equiv (b_j^2-b_i^2)-(b_{j+1}-b_{i+1})\equiv 0\ (mod\ k)\\ \Rightarrow b_{j-1}=b_{i-1}$$
Tương tự: $b_{j-2}=b_{i-2};... ;b_2=b_{2+(j-i)};b_1=b_{1+(j-i)}$
Vậy dãy đã cho tuần hoàn ngay từ $b_1$ với chu kỳ (chưa chắc đã là cơ sở) $j-i$
Bài viết đã được chỉnh sửa nội dung bởi minhtuyb: 14-06-2013 - 12:33
- Xét dãy $b_n$ là dãy được xác định theo quy tắc: $b_n\equiv a_n\ (mod\ k)\ \ ;0\le b_n<k$ với modul $k$ bất kì.
Làm sao nghĩ ra được dãy này thế
Làm sao nghĩ ra được dãy này thế
Em dựa vào ý tưởng chứng minh dãy số dư của một dãy số cho bởi công thức tuyến tính modul bất kỳ đều tuần hoàn ạ.
Em dựa vào ý tưởng chứng minh dãy số dư của một dãy số cho bởi công thức tuyến tính modul bất kỳ đều tuần hoàn ạ.
Cái này là 1 định lý hay là phương pháp vậy em ? Anh dở Số học....
Cái này là 1 định lý hay là phương pháp vậy em ? Anh dở Số học....
Em nghĩ gọi nó là bổ đề . Em tổng quát cái này từ phần b bài dãy số trong TST 2004 .
Giả sử ta có dãy $(a_n):a_0;a_1;...;a_m;a_{n+m}=\alpha_1 a_{m+n-1} +\alpha_2 a_{m+n-2}+...+\alpha_m a_{n}\ \forall n$ với $\alpha_i$ là các hằng số nguyên và $b_n$ là dãy số dư của $a_n$ theo modul $k$ bất kỳ thì $b_n$ sẽ tuần hoàn.
Cốt lõi của phép chứng minh chỉ là chỉ ra có hữu hạn bộ $(b_1;b_2;b_3;...;b_m)$ rồi dùng Đi dép lê để chứng minh có hai bộ trùng nhau, suy ra dãy tuần hoàn.
P/s: Ta có thể mở rộng thêm bằng cách cho thêm số mũ vào nữa .
Bài viết đã được chỉnh sửa nội dung bởi minhtuyb: 13-06-2013 - 23:24
- Xét dãy $b_n$ là dãy được xác định theo quy tắc: $b_n\equiv a_n\ (mod\ k)\ \ ;0\le b_n<k$ với modul $k$ bất kì. Từ công thức của dãy $a_n$ ta có:
$$b_{n+2}\equiv b_{n+1}^2-b_{n}\ (mod\ k)$$
- Ta sẽ chứng minh $b_{n}$ là dãy tuần hoàn với mọi modul $k$. Thật vậy, ta chỉ cần chứng minh tồn tại hai chỉ số $i,j,i<j$ sao cho $b_i=b_j;b_{i+1}=b_{j+1}$ vì khi đó sẽ có $b_{j+2}\equiv b_{j+1}^2-b_{j}\equiv b_{i+1}^2-b_{i}\equiv b_{i+2}\ (mod\ k)$. Tương tự: $b_{j+3}\equiv b_{i+3};b_{j+4}\equiv b_{i+4};...;b_{2j-i-1}\equiv b_{j-1}\ (mod\ k)$, suy ra $b_n$ là dãy tuần hoàn.
- Do chỉ có tối đa $k^2$ cặp giá trị $(b_i;b_{i+1})$ nên nếu ta chọn $k^2+1$ cặp như thế thì theo nguyên lí Đi dép lê sẽ tồn tại hai cặp $(b_i;b_{i+1});(b_j;b_{j+1}): b_i=b_j;b_{i+1}=b_{j+1}$. Tóm lại với mọi modul $k$ thì dãy số dư của $a_n$ theo modul $k$ sẽ tuần hoàn.
Công việc còn lại là cần chỉ ra tồn tại $a_m\vdots 1995$. Rất đơn giản vì $a_3=45^2-30=1995$ luôn rồi $\square$
Hình như bài toán này giải chưa đầy đủ vì chưa biết dãy $a_n$ tuần hoàn từ số hạng thứ mấy thì phải???
Cái này là 1 định lý hay là phương pháp vậy em ? Anh dở Số học....
Định luật tuần hoàn dãy số dư! Một định lý đơn giản nhưng ứng dụng rất nhiều đối với dãy số (tổng hữu hạn, hàm phần nguyên, v.v...)
Định luật chỉ ra rằng:
$a_n= P(n)\mod m$ là dãy tuần hoàn
với $P(n)$ là đa thức nguyên hay hàm mũ nguyên biến $n$
$m$ là số nguyên dương bất kỳ.
Từ đó, mọi dãy (nguyên) tuyến tính cấp 1, 2, ... đều thỏa mãn định lý này. (Nguồn: không nhớ )
Định luật tuần hoàn dãy số dư! Một định lý đơn giản nhưng ứng dụng rất nhiều đối với dãy số (tổng hữu hạn, hàm phần nguyên, v.v...)
Định luật chỉ ra rằng:
$a_n= P(n)\mod m$ là dãy tuần hoàn
với $P(n)$ là đa thức nguyên hay hàm mũ nguyên biến $n$
$m$ là số nguyên dương bất kỳ.
Từ đó, mọi dãy (nguyên) tuyến tính cấp 1, 2, ... đều thỏa mãn định lý này. (Nguồn: không nhớ )
Thầy ơi thầy có tài liệu nào chuyên viết về mấy cái này không ạ?
Bài tương tự sử dụng tính tuần hoàn của dãy số dư.
Cho dãy số $(x_n)$ thỏa mãn
$$\left\{\begin{matrix}
x_1=1990;x_2=1989; x_3=2000;\\
x_{n+3}=19x_{n+2}+9x_{n+1}+x_n+1991\;\;\; \forall n\ge 1
\end{matrix}\right.$$
a) Với mọi $n\in \mathbb{N^*}$, gọi $r_n$ là số dư trong phép chia $x_n$ cho 1992. Chứng minh rằng dãy số $(x_n)$ tuần hoàn .
b) Chứng minh rằng tồn tại vô số số $n\in \mathbb{N^*}$ sao cho
$$5x_n^{1992}+5x_n^{1954}+4x_n^{1975}+8x_n^{1945}+2x_n^{1930}+11x_n^2+49 \vdots 1992$$
Bài viết đã được chỉnh sửa nội dung bởi Ispectorgadget: 14-06-2013 - 17:21
►|| The aim of life is self-development. To realize one's nature perfectly - that is what each of us is here for. ™ ♫
0 thành viên, 1 khách, 0 thành viên ẩn danh