Tuyển tập Dãy số - Giới hạn116 bài

Bài toán (Poland Finals 2002)

Cho $k$ là một số nguyên dương cố định. Xét dãy $(a_n)$ thỏa mãn :

$$\{\begin{array}{c}{a}_1=k+1\\ a_{n+1}=a_n^2-k{a}_n+k,\forall n\ge 1\end{array}$$

Chứng minh rằng với mọi số nguyên dương $m$ khác $n$ thì $a_m,a_n$ nguyên tố cùng nhau.

Lời giải :

Ta có :

$$a_{n+1}-k=a_n(a_n-k)=a_n{a}_{n-1}(a_{n-1}-k)=...=a_n{a}_{n-1}{a}_{n-2}...a_1(a_1-k)=a_n{a}_{n-1}...a_1$$

Không giảm tổng quát, ta giả sử $m>n$. Khi đó gọi $p$ là một ước nguyên tố chung của $\gcd (a_m,a_n)$. Ta có :

$$a_m-k=a_{m-1}{a}_{m-2}...a_n..a_1⋮p\Rightarrow p\mid k$$

Suy ra :

$p\mid a_n-k$$=a_{n-1}(a_{n-1}-k)$$=a_{n-1}^2-k{a}_{n-1}$$\Rightarrow p\mid a_{n-1}^2$$\Rightarrow p\mid a_{n-1}$

Và lại suy ra :

$$p\mid a_{n-1}-k=a_{n-2}^2-k{a}_{n-2}\Rightarrow p\mid a_{n-2}^2\Rightarrow p\mid a_{n-2}$$

Cứ tiếp tục quá trình này ta suy ra $p\mid a_1=k+1$, suy ra $p\mid 1$. Mâu thuẫn.

Như vậy $\gcd (a_m,a_n)$ không có một ước nguyên tố nào, tức là $\gcd (a_m,a_n)=1$. Điều phải chứng minh.

Bài toán : Xét dãy số $(a_n)$ thỏa mãn :

$$\{\begin{array}{c}{a}_0=0,a_1=1,a_2=2,a_3=6\\ a_{n+4}=2a_{n+3}+a_{n+2}-2a_{n+1}-a_n\end{array}$$

a) Chứng minh rằng với mọi số nguyên dương $n$ thì $n\mid a_n$.

b) Chứng minh rằng với $k$ là số nguyên dương bất kỳ thì dãy $\frac{a_1}{1},\frac{a_2}{2},\frac{a_3}{3},...,\frac{a_n}{n}$ chứa vô hạn các số hạng chia hết cho $k$.

Lời giải :

a) Ta thấy $\frac{a_1}{1}=1=F_1,\frac{a_2}{2}=1=F_2,\frac{a_3}{3}=2=F_3,\frac{a_4}{4}=3=F_4,\frac{a_5}{5}=5=F_5,...$

Vậy ta có dự đoán :

$$a_n=n.F_n$$

Và chứng minh dự đoán này bằng quy nạp, giả sử điều đó đúng đến $n+3$. Xét với $n+4$ :

$a_{n+4}$$=2a_{n+3}+a_{n+2}-2a_{n+1}-a_n$$=2(n+3)F_{n+3}+(n+2)F_{n+2}-2(n+1)F_{n+1}-n{F}_n$$=2(n+3)F_{n+3}+(n+2)F_{n+2}-2(n+1)F_{n+1}-n(F_{n+2}-F_{n+1})$$=2(n+3)F_{n+3}+2F_{n+2}-(n+2)F_{n+1}$$=2(n+3)F_{n+3}+2F_{n+2}-(n+2)(F_{n+3}-F_{n+2})$$=(n+4)(F_{n+3}+F_{n+2})$$=(n+4)F_{n+4}$

Theo nguyên lí quy nạp ta có $a_n=n.F_n$ với mọi $n$ nguyên dương, suy ra $n\mid a_n$ với mọi $n$ nguyên dương.

Điều phải chứng minh.

b) Nhận thấy dãy nói ở đề bài chính là dãy Fibonacci.

Từ đó theo định luật tuần hoàn của dãy số dư, ta có dãy số dư $(r_n)$ là dãy tuần hoàn. Trong đó $r_n$ là số dư khi chia $F_n$ cho $k$ với mỗi $n$. Hơn nữa $r_0=0$ vì $F_0=0$, điều này đồng nghĩa tồn tại vô hạn số hạng của dãy Fibonacci là bội của $k$. Điều phải chứng minh.

Bài toán : (International Mathematical Olympiad 1981)

Tìm giá trị lớn nhất của $m^2+n^2$ trong đó $m,n$ là các số nguyên thỏa mãn $1\le m,n\le 1981$ và

$$(n^2-mn-m^2{)}^2=1$$.

Lời giải :

Trước hết ta sẽ chứng minh rằng với cặp $(x,y)$ nguyên dương bất kỳ thỏa mãn $(x^2-xy-y^2{)}^2=1(1)$ thì đều tồn tại $n$ sao cho $x=F_n,y=F_{n+1}$ với $F_n$ là số hạng thứ $n$ của dãy Fibonacci :

$$\{\begin{array}{c}{F}_0=0,F_1=1\\ F_{n+1}=F_n+F_{n-1},n\ge 1\end{array}$$

Ta gọi $(u_1,u_0)$ là một cặp số nguyên dương bất kỳ thỏa $(1)$. Vì các cặp $(0,1),(1,0),(1,1)$ đều thỏa $(1)$ và dễ dàng thấy những giá trị này đều thuộc dãy Fibonacci nên ta chỉ xét với $u_1,u_0>1$.

Ta có :

$$u_0(u_0-u_1)=u_1^2\pm 1>0\Rightarrow u_0>u_1$$

Ta chọn $u_2=u_0-u_1$. Thế thì $u_2$ nguyên dương. Hơn nữa dễ kiểm tra được cặp $(u_1,u_2)$ cũng sẽ thỏa $(1)$. Để ý :

$$u_2+u_1=(u_0-u_1)+u_1=u_0<u_1+u_0$$

Chọn tiếp cặp $(u_2,u_3)=(u_2,u_1-u_2)$ thì $u_3$ nguyên dương và cặp $(u_2,u_3)$ cũng thỏa $(1)$ và cũng thu được $u_3+u_2<u_2+u_1$.

Cứ tiếp tục quá trình này :

$$...<u_{i+1}+u_i<...<u_3+u_2<u_2+u_1<u_1+u_0$$

Hơn nữa $u_1+u_0$ bị chặn dưới bởi $2$ nên phải tồn tại $k$ sao cho $u_{k+1}+u_k=2$, kéo theo $u_k=u_{k+1}=1$.

Điều này tức là :

$$u_k=F_2,u_{k+1}=F_1$$.

Suy ra :

$$u_{k-1}=u_k+u_{k+1}=F_2+F_1=F_3$$

$$u_{k-2}=u_{k-1}+u_k=F_3+F_2=F_4$$

…

$$u_1=u_2+u_3=F_k+F_{k-1}=F_{k+1}$$

$$u_0=u_1+u_2=F_{k+1}+F_k=F_{k+2}$$

Như vậy với cặp $(u_1,u_0)$ bất kỳ thỏa $(1)$ thì tồn tại $n=k+1$ để mà $u_1=F_{k+1},u_0=F_{k+2}$.

Điều này chứng tỏ mọi nghiệm của $(1)$ là $(F_n,F_{n+1})$.

Ta liệt kê các số hạng của dãy Fibonacci không vượt quá $1981$ :

$$0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597$$

Ta kết luận được $max(m^2+n^2)=987^2+1597^2$.

 

Bài toán : Xét phương trình $x^2+y^2+1=kxy$.

a) Tìm tất cả các số $k$ nguyên dương sao cho phương trình trên có nghiệm nguyên dương $(x,y)$.

b) Với các giá trị $k$ tìm được, hãy tìm tất cả các nghiệm nguyên dương của phương trình.

Lời giải :

a) Cố định $k$ và xét tập :

$S$$=\left\{(x,y)\in {\left({\mathbb{Z}}^{+}\right)}^2|k=\frac{x^2+y^2+1}{xy}\in {\mathbb{Z}}^{+}\right\}$

Trong $S$ chọn ra cặp $(X,Y)$ thỏa mãn $X+Y$ nhỏ nhất, giả sử $X\ge Y$.

Xét phương trình :

$$t^2-ktY+Y^2+1=0$$

Dễ thấy phương trình này có nghiệm $t_1=X$, gọi nghiệm còn lại là $t_0$. Theo định lí Viete :

$$\{\begin{array}{c}{t}_0+X=kY\\ t_{0}X=Y^2+1\end{array}$$

Từ đây dễ thấy $t_0$ cũng nguyên dương, vì tính nhỏ nhất của $X+Y$ nên $t_0\ge X$.

Suy ra :

$$kY=t_0+X\ge 2X\Rightarrow \frac{X}{Y}\le \frac{k}{2}$$

Vì $X,Y$ nguyên dương nên $X,Y\ge 1$. Như vậy :

$$k=\frac{X}{Y}+\frac{Y}{X}+\frac{1}{XY}\le \frac{k}{2}+1+1\iff k\le 4$$

Và dấu bằng chỉ xảy ra khi $X=Y,2X=kY,X=Y=1$. Mâu thuẫn. Như vậy $k\le 3$. Hơn nữa theo AM-GM ta dễ thấy $k\ge 3$.

Ta được $k=3$. Thử lại với $k=3$ thì $(x,y)=(1,1)$ là một nghiệm của phương trình.

b) Ta tìm tất cả các nghiệm của phương trình :

$$x^2+y^2+1=3xy(1)$$

Xét dãy số $(u_n)$ xác định như sau :

$$\{\begin{array}{c}{u}_0=1,u_1=1\\ u_{n+1}=3u_n-u_{n-1},\forall n\ge 1\end{array}$$

Ta chứng minh nếu $(x,y)$ là cặp số nguyên dương bất kỳ thỏa $(1)$ khi và chỉ khi $n$ để $x=x_n,y=x_{n+1}$.

Thực vậy, dễ kiểm tra được $(x_n,x_{n+1})$ thỏa $(1)$ với mọi $n$. Gọi $(w_0,w_1)$ là một cặp số nguyên dương bất kỳ thỏa $(1)$. Nếu $w_0=1$ thì $w_1=1$, tức tồn tại $n=0$ để $w_0=u_0,w_1=w_1$. Do đó ta chỉ cần xét $w_0,w_1>1$, giả sử luôn $w_0>w_1$.

Khi đó ta chọn $w_2=3w_1-w_0$. Dễ thấy $w_2$ nguyên dương và cặp $(w_1,w_2)=(w_1,3w_1-w_0)$ lúc này cũng thỏa $(1)$.

Để ý ta có :

$$w_2=3w_1-w_0=\frac{w_1^2+1}{w_0}<w_0$$

Suy ra $w_2+w_1<w_1+w_0$.

Hoàn toàn tương tự ta chọn được cặp $(w_2,w_3)=(w_2,3w_2-w_1)$ cũng thỏa $w_3$ nguyên dương và $w_3+w_2<w_2+w_1$.

Cứ tiếp tục quá trình này, ta được :

$$...<w_{i+1}+w_i<...<w_2+w_1<w_1+w_0$$

Nhưng $w_1+w_0$ bị chặn dưới bởi $2$ nên phải tồn tại $k$ sao cho :

$$w_k+w_{k+1}=1\Rightarrow w_k=u_1=1,w_{k+1}=u_0=1$$

Từ đó :

$$w_{k-1}=3w_k-w_{k+1}=3u_1-u_0=u_2$$

$$w_{k-2}=3w_{k-1}-w_k=3u_2-u_1=u_3$$

…

$$w_1=3w_2-w_3=3u_{k-1}-u_{k-2}=u_k$$

$$w_0=3w_1-w_2=3u_k-3u_{k-1}=u_{k+1}$$.

Như vậy với cặp $(w_0,w_1)$ bất kỳ thì tồn tại $n=k$ để $(w_1,w_0)=(u_k,u_{k+1})$.

Từ đó tất cả các nghiệm của phương trình là $(x,y)=(u_n,u_{n+1})$ với dãy $(u_n)$ xác định như trên.

 

Lưu ý : Kỹ thuật xét dãy như trên :

Xét dãy truy hồi tuyến tính cấp hai : 

$$\{\begin{array}{c}{u}_0=\alpha ,u_1=\beta \\ u_{n+1}=a{u}_n-u_{n-1}+b\end{array}(\ast )$$

Để ý thì thấy :

$\frac{u_{n+1}+u_{n-1}-b}{u_n}$$=a$$=\frac{u_{n+2}+u_n-b}{u_{n+1}}$$\iff u_{n+1}^2+u_{n+1}{u}_{n-1}-b{u}_{n+1}$$=u_{n+2}{u}_n+u_n^2-b{u}_n$$\iff u_{n+1}^2-(a{u}_{n+1}-u_n+b)u_n-b{u}_{n+1}$$=u_n^2-(a{u}_n-u_{n-1}+b)u_{n-1}-b{u}_n$$\iff u_{n+1}^2+u_n^2-a{u}_{n+1}{u}_n-b(u_{n+1}+u_n)$$=u_n^2+u_{n-1}^2-a{u}_n{u}_{n-1}-b(u_n+u_{n-1})$

Như vậy :

$$u_n^2+u_{n-1}^2-a{u}_n{u}_{n-1}-b(u_n+u_{n-1})={\alpha }^2+{\beta }^2-a\alpha \beta -b(\alpha +\beta )$$

Do đó nếu gặp phương trình có dạng :

$$x^2+y^2-axy-b(x+y)={\alpha }^2+{\beta }^2-a\alpha \beta -b(\alpha +\beta )$$

Thì ta sẽ xét dãy $(\ast )$. 

 

Bài toán (China 1991) 

Cho dãy số $(u_n)$ nguyên thỏa mãn $u_{n+2}=u_{n+1}^2-u_n$ với mọi $n$ tự nhiên. Gỉa sử $u_0=39,u_1=45$. Chứng minh có vô hạn số hạng của dãy $(u_n)$ chia hết cho $1986$.

Lời giải :

Gọi $r_n$ là số dư của $u_n$ khi chia cho $1986$ ứng với mỗi $n$. Ta chứng minh dãy $(r_n)$ tuần hoàn.

Xét dãy gồm các bộ số dư :

$$(r_1,r_2),(r_2,r_3),...,(r_m,r_{m+1}),...$$

Dãy trên có vô số số hạng mà số bộ khác nhau là hữu hạn vì $r_i\in \left\{0,1,2,...,1985\right\}$. Như vậy theo nguyên lí Dirichlet, sẽ tồn tại hai bộ trùng nhau. Tức là tồn tại $k,m$ nguyên dương :

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

Từ đó :

$$r_m=r_{m+1}^2-r_{m+2}=r_{m+k+1}^2-r_{m+k+2}=r_{m+k}$$

$$r_{m-1}=r_m^2-r_{m+1}=r_{m+k}^2-r_{m+k+1}=r_{m+k-1}$$

…

$$r_1=r_2^2-r_3=r_{k+2}^2-r_{k+3}=r_{k+1}$$

Tức là ta đã được :

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

Từ đó dựa vào công thức xác định dãy, ta thu được :

$$r_n=r_{n+k},\forall n=0,1,\mathrm{2...}$$

Hơn nữa ta có $u_2=45^2-39=1986$ nên sẽ tồn tại vô hạn số hạng của dãy $(u_n)$ chia hết cho $1986$.

Bài toán : Cho dãy số $(a_n)$ xác định bởi :

$$a_1=0,a_{n+1}=\frac{n^3(4n+2)}{(n+1{)}^4}{a}_n+\frac{3n+1}{(n+1{)}^4},\forall n\in {\mathbb{N}}^{\ast }$$

a) Chứng minh rằng $a_n=\frac{C_{2n}^n-2}{2n^3}$.

b) (Chọn đội tuyển HSG THPT Chuyên Khoa học Tự Nhiên, ĐHQG Hà Nội 2010)

Chứng minh rằng dãy trên chứa vô hạn các số hạng nguyên dương.

Lời giải :

a) Ta chứng minh bằng quy nạp, dễ thấy với $n=0,1$ thì đúng. Gỉa sử có điều đó với $n$. Xét với $n+1$ :

$a_{n+1}$$=\frac{n^3(4n+2)}{(n+1{)}^4}.\frac{C_{2n}^n-2}{2n^3}+\frac{3n+1}{(n+1{)}^4}$$=\frac{(2n+1)}{(n+1{)}^4}.\left(\frac{2n(2n-1)(2n-2)...(n+1)}{n!}-2\right)+\frac{3n+1}{(n+1{)}^4}$$=\frac{1}{(n+1{)}^4}\left(\frac{(2n+2)(2n+1)(2n)...(n+2)(n+1)}{2(n+1)!}-2(2n+1)\right)+\frac{3n+1}{(n+1{)}^4}$$=\frac{1}{(n+1{)}^4}.\left(\frac{C_{2n+2}^{n+1}.(n+1)}{2}-2(2n+1)\right)+\frac{3n+1}{(n+1{)}^4}$$=\frac{C_{2n+2}^{n+1}}{2(n+1{)}^3}+\frac{3n+1}{(n+1{)}^4}-\frac{2(2n+1)}{(n+1{)}^4}$$=\frac{C_{2n+2}^{n+1}-2}{2(n+1{)}^3}$

Theo nguyên lí quy nạp, ta có điều phải chứng minh.

b) Ta chứng minh với mọi số nguyên tố $p>3$ thì $a_p$ nguyên dương, khi đó bài toán hoàn toàn được giải quyết.

Tức là ta đi chứng minh nếu $p$ nguyên tố và lớn hơn $3$ thì :

$$2p^3\mid C_{2p}^p-2$$

Ta chứng tỏ $2\mid C_{2p}^p$. Thực vậy ta có :

$C_{2p}^p$$=\frac{2p(2p-1)(2p-2)...(p+1)}{p!}$$=\frac{(2p)!}{(p!{)}^2}$$\Rightarrow v_2(C_{2p}^p)$$=v_2((2p)!)-2v_2((p!))$

Sử dụng định lý Legendre :

$v_2((2p)!)$$=\lfloor p\rfloor +\lfloor \frac{p}{2}\rfloor +\lfloor \frac{p}{2^2}\rfloor +..$

$2v_2(p!)$$=2\lfloor \frac{p}{2}\rfloor +2\lfloor \frac{p}{2^2}\rfloor +2\lfloor \frac{p}{2^3}\rfloor +...$

Ta chứng minh nhận xét sau :

$$2\lfloor \frac{p}{2^{n+1}}\rfloor \le \lfloor \frac{p}{2^n}\rfloor$$

Thực vậy, ta đặt $p=2^{n+1}.k+t$ với $t\in \left\{1,3,5,...,2^{n+1}-1\right\}$. Khi ấy :

$2\lfloor \frac{p}{2^{n+1}}\rfloor$$=2\lfloor \frac{2^{n+1}.k+t}{2^{n+1}}\rfloor$$=2\lfloor k+\frac{t}{2^{n+1}}\rfloor ,\lfloor \frac{p}{2^n}\rfloor$$=\lfloor 2k+\frac{t}{2^n}\rfloor$

Rõ ràng nhận xét sẽ đúng nếu mà $t<2^n<2^{n+1}$. Do vậy chỉ xét $2^n<t<2^{n+1}$. Khi ấy cần chứng minh :

$2\lfloor \frac{p}{2^{n+1}}\rfloor$$=2k$$<2k+1$$=\lfloor 2k+\frac{t}{2^n}\rfloor$$=\lfloor \frac{p}{2^n}\rfloor$

Vậy nhận xét được chứng minh, sử dụng nhận xét này ta dễ dàng suy ra :

$$v_2\left((2p)!\right)>2v_2(p!)\Rightarrow 2\mid C_{2p}^p-2$$

Và vì $\gcd (p,2)=1$ nên nhiệm vụ còn lại là chứng minh :

$$C_{2p}^p\equiv 2(\mathrm{mod}{p}^3)$$

Ta lại có :

$$C_{2p}^p=\frac{2p(2p-1)(2p-2)..(p+1)}{p!}=2\frac{(2p-1)(2p-2)...}{(p-1)!}=C_{2p-1}^{p-1}$$

Nên chỉ cần chứng tỏ :

$$C_{2p-1}^{p-1}\equiv 1(\mathrm{mod}{p}^3)$$

Và đây chính là nội dung của định lý Wolstenholme.

Bài toán được chứng minh.

 

 

Một chút về định lý Wolstenholme :

Định lý có bốn cách phát biểu khác nhau :

Phát biểu 1 : Với mọi số nguyên tố $p$ lớn hơn $3$ và :

$1+\frac{1}{2^2}+\frac{1}{3^2}+...+\frac{1}{(p-1{)}^2}$$=\frac{m}{n}\left(m,n\in \mathbb{Z},\gcd (m,n)=1\right)$

Thì $p\mid m$.

Phát biểu 2 :Với mọi số nguyên tố $p$ lớn hơn $3$ và :

$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{(p-1)}$$=\frac{m}{n}\left(m,n\in \mathbb{Z},\gcd (m,n)=1\right)$

Thì $p^2\mid m$.

Phát biểu 3 : Với mọi số nguyên tố $p$ lớn hơn $3$ thì :

$$C_{2p-1}^{p-1}=\left(\genfrac{}{}{0ex}{}{2p-1}{p-1}\right)\equiv 1(\mathrm{mod}{p}^3)$$

Phát biểu 4 : Với mọi số nguyên tố $p$  lớn hơn $3$ thì :

$$C_{ap}^{bp}=\left(\genfrac{}{}{0ex}{}{ap}{bp}\right)\equiv \left(\genfrac{}{}{0ex}{}{a}{b}\right)=C_a^b(\mathrm{mod}{p}^3)$$

Xem chứng minh cụ thể tại đây.

Bài toán : Cho dãy số xác định bởi $P_0=3,P_1=0,P_2=2$ và :

$$P_n=P_{n-2}+P_{n-3},n\ge 3$$.

Chứng minh rằng nếu $p$ là số nguyên tố thì $p\mid x_p$.

(Dãy số xác định như trên được gọi là Dãy Perrin)

Lời giải :

Phương trình đặc trưng của dãy là :

$$t^3-t-1=0$$

Gọi $t_1,t_2,t_3$ là ba nghiệm của phương trình này thì $x_n$ luôn được biểu diễn dưới dạng :

$$x_n=A{t}_1^n+B{t}_2^n+C{t}_3^n$$

Ta có :

$$\{\begin{array}{c}{x}_0=A+B+C=3\\ x_1=A{t}_1+B{t}_2+C{t}_3=0\\ x_2=A{t}_1^2+B{t}_2^2+C{t}_3^2=2\end{array}$$

Hơn nữa theo định lí Viete ta có :

$$t_1+t_2+t_3=0,t_1{t}_2+t_2{t}_3+t_3{t}_1=-1,t_1{t}_2{t}_3=1$$.

Ta được :

$$\{\begin{array}{c}A+B+C=3\\ A{t}_1+B{t}_2+C{t}_3=t_1+t_2+t_3\\ A{t}_1^2+B{t}_2^2+C{t}_3^2=t_1^2+t_2^2+t_3^2\end{array}\Rightarrow A=B=C=1$$

Như vậy thì :

$$x_n=t_1^n+t_2^n+t_3^n$$.

Ta sẽ chứng minh nhận xét sau :

$$(w_1+w_2+...+w_n{)}^p\equiv w_1^p+w_2^p+...+w_n^p(\mathrm{mod}p)$$

với mọi số nguyên tố $p$ và $w_1,w_2,...,w_n$ là các số thỏa $w_1+w_2+...w_n$ nguyên và $w_1^p+w_2^p+...+w_n^p$ nguyên.

Với $n=2$ thì bằng khai triển nhị thức Newton và chú ý $C_p^k\equiv 0(\mathrm{mod}p),\forall k=\overline{0,p-1}$, điều cần chứng minh là đúng.

Gỉa sử điều này đúng đến $n$, xét với $n+1$.

Ta đặt $w_1+w_2+...+w_n=U$ và $w_1^p+w_2^p+....+w_n^p=V$ thì theo giả thiết quy nạp $U^p\equiv V(\mathrm{mod}p)$

Ta có :

$(w_1+...w_n+w_{n+1}{)}^p$$=(U+w_{n+1}{)}^p$$\equiv U^p+w_{n+1}^p$$\equiv V+w_{n+1}^p$$\equiv w_1^p+w_2^p+....+w_{n+1}^p(\mathrm{mod}p)$

Ta quy nạp hoàn tất. Trở lại với bài toán, theo nhận xét :

$$t_1^p+t_2^p+t_3^p\equiv (t_1+t_2+t_3{)}^p=0(\mathrm{mod}p)$$

Tức là $p\mid x_p$. Bài toán hoàn tất.

 

Bài toán (Bulgarian Mathematical Olympiad 2001)

Xét dãy số $(a_n)$ thỏa mãn $a_0=4,a_1=22$ và :

$$a_n-6a_{n-1}+a_{n-2}=0$$ với mọi $$n\ge 2$$.

Chứng minh rằng với mọi số tự nhiên $n$, luôn tồn tại hai dãy $(x_n),(y_n)$ sao cho :

$$a_n=\frac{y_n^2+7}{x_n-y_n}$$

Gợi ý giải :

Ta xây dựng dãy mới $(c_n)$ như sau :

$$\{\begin{array}{c}{c}_0=a,c_1=b\\ c_n=p{c}_{n-1}+q{c}_{n-2},\forall n\ge 2\end{array}$$

Ta có một tính chất đặc biệt sau của dãy tuyến tính bậc hai :

$c_{n+2}{c}_n-c_{n+1}^2$$=(-q{)}^n.(c_0{c}_2-c_1^2)$$\iff c_{n+2}$$=\frac{c_{n+1}^2+(-q{)}^n.(c_0{c}_2-c_1^2)}{c_n}$

Rõ ràng ta phải chọn $q=1$ và $c_0{c}_2-c_1^2=7$.

Hay là :

$$q=1$$ và $$a(pb+a)-b^2=7$$

Khi đó ta có :

$$c_{n+2}=\frac{c_{n+1}^2+7.(-1{)}^n}{c_n}\Rightarrow c_{2n+2}=\frac{c_{2n+1}^2+7}{c_{2n}}$$

Như vậy ta phải chọn dãy $(c_n)$ để mà $a_n=c_{2n+2},\forall n\in \mathbb{N}$.

Cho $n=0$ thì $c_2=a_0=4$ tức $pb+a=4$. Chọn $n=1$ thì $22=a_1=c_4=p{c}_3+c_2=p(p{c}_2+c_1)+c_2=4p^2+pb+4$.

Ta có hệ sau :

$$\{\begin{array}{c}a(pb+a)-b^2=7\\ pb+a=4\\ 4p^2+pb+4=22\end{array}\iff p=2,a=2,b=1$$

Lời giải :

Ta xét dãy $(c_n)$ :

$$\{\begin{array}{c}{c}_0=2,c_1=1\\ c_n=2c_{n-1}+c_{n-2},\forall n\ge 2\end{array}$$

Ta sẽ chứng minh bằng quy nạp rằng $c_{2n+2}=a_n$ với mọi $n$.

Với $n=0,1$ hiển nhiên. Gỉa sử điều đó đúng với $n=k-2$ và $n=k-1$. Ta có :

$c_{2k+2}$$=2c_{2k+1}+c_{2k}$$=2(2c_{2k}+c_{2k-1})+c_{2k}$$=5c_{2k}+(c_{2k}-c_{2k-2})$$=6c_{2k}-c_{2k-2}$$=6a_k-a_{k-1}$$=a_{k+1}$

Theo nguyên lí quy nạp thì $c_{2n+2}=a_n$ với mọi số tự nhiên $n$.

Hơn nữa ta dễ dàng thấy được :

$$c_{n+2}{c}_n-c_{n+1}^2=7.(-1{)}^n\Rightarrow a_n=c_{2n+2}=\frac{c_{2n+1}^2+7}{c_{2n}}$$

Và công việc còn lại của ta chỉ cần chọn hai dãy $(x_n)$ và $(y_n)$ sao cho :

$$y_n=c_{2n+1},x_n=c_{2n}+y_n$$

Hiển nhiên chọn được. Bài toán hoàn tất.