Đến nội dung

Hình ảnh

$a_1=30;a_2=45;a_{n+2}=a_{n+1}^{2}-a_{n}$.CMR tồn tại vô số $n$ để $a_{n}\vdots 1995$.

- - - - -

  • Please log in to reply
Chủ đề này có 9 trả lời

#1
diepviennhi

diepviennhi

    Sĩ quan

  • Thành viên
  • 318 Bài viết

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


#2
minhtuyb

minhtuyb

    Giả ngu chuyên nghiệp

  • Thành viên
  • 470 Bài viết

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 :P $\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

Phấn đấu vì tương lai con em chúng ta!

#3
dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết

- 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ế  :icon13:


"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#4
minhtuyb

minhtuyb

    Giả ngu chuyên nghiệp

  • Thành viên
  • 470 Bài viết

Làm sao nghĩ ra được dãy này thế  :icon13:

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


Phấn đấu vì tương lai con em chúng ta!

#5
dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết

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.... :P


"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#6
minhtuyb

minhtuyb

    Giả ngu chuyên nghiệp

  • Thành viên
  • 470 Bài viết

Cái này là 1 định lý hay là phương pháp vậy em ? Anh dở Số học.... :P

Em nghĩ gọi nó là bổ đề :P. Em tổng quát cái này từ phần b bài dãy số trong TST 2004 :P.

 

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 :P.


Bài viết đã được chỉnh sửa nội dung bởi minhtuyb: 13-06-2013 - 23:24

Phấn đấu vì tương lai con em chúng ta!

#7
nguyenthehoan

nguyenthehoan

    Sĩ quan

  • Thành viên
  • 392 Bài viết

- 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 :P $\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???



#8
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3916 Bài viết

Cái này là 1 định lý hay là phương pháp vậy em ? Anh dở Số học.... :P

Đị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ớ :luoi:)



#9
minhtuyb

minhtuyb

    Giả ngu chuyên nghiệp

  • Thành viên
  • 470 Bài viết

Đị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ớ :luoi:)

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 ạ?


Phấn đấu vì tương lai con em chúng ta!

#10
Ispectorgadget

Ispectorgadget

    Nothing

  • Quản lý Toán Phổ thông
  • 2946 Bài viết

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. ™ ♫





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh