Tuyển tập Quy nạp toán học30 bài

Bài toán : (IMO Shortlist 2014) 

Tìm tất cả các hàm số $f:\mathbb{Z}\to \mathbb{Z}$ và thoả mãn :

$$f(f(m)+n)+f(m)=f(3m)+f(n)+2014,\forall m,n\in \mathbb{Z}(1)$$

Lời giải :

Trước tiên, ta sẽ chứng minh rằng $f(0)=1007$. Đặt $f(0)=a$.

Trong $(1)$ cho $m=0$ :

$$f(n+a)=f(n)+2014,\forall n\in \mathbb{Z}$$

Từ đây ta chứng minh được bằng quy nạp :

$$f(na)=a+2014n,\forall n\in \mathbb{Z}(2)$$

Trong $(1)$ thay $m$ bởi $ma$ và sử dụng $(2)$ :

$f(f(ma)+n)+f(m)$$=f(3m)+f(n)+2014,\forall m,n\in \mathbb{Z}$$\iff f(a+2014m+n)+(a+2014m)$$=(a+3.2014m)+f(n)+2014,\forall m,n\in \mathbb{Z}$

Hay :

$$f(a+2014m+n)=f(n)+4028m+2014,\forall m,n\in \mathbb{Z}(3)$$

Trong $(3)$ thay $n=-a,m=a$ thì :

$$f(2014a)=f(-a)+4028a+2014,\forall m\in \mathbb{Z}(4)$$

Trong $(2)$ cho $n=2014$ thì :

$$f(2014a)=a+2014^2(5)$$

Từ $(4)(5)$ ta suy ra rằng :

$$f(-a)=-4027a+2014^2-2014(6)$$

Trong $(2)$ ta lại cho $n=-1$ thì được :

$$f(-a)=a-2014(7)$$

Và kết hợp $(6)(7)$ ta được :

$$a-2014=-4027a+2014^2-2014\iff a=1007$$

Như vậy ta đã chứng minh được rằng $a=f(0)=1007$.

Từ $(2)$ ta được :

$f(1007n)$$=1007+2014n,\forall n\in \mathbb{Z}$$\Rightarrow f(n)$$=a+2n,\forall n\in \mathbb{Z},a\mid n$

Trong $(1)$ ta thay $n=-f(m)$ thì được  :

$$f(m)=f(3m)+f(-f(m))+1007,\forall m\in \mathbb{Z}(8)$$

Trong $(8)$ ta tiếp tục thay $m$ bởi $am$ :

$f(am)$$=f(3am)+f(-f(am))+1007,\forall m\in \mathbb{Z}$$\iff (a+2m)$$=(a+6m)+f(-a-2m)+1007,\forall m\in \mathbb{Z}$

Thu gọn thành :

$f(-a-2m)$$=-4m-a,\forall m\in \mathbb{Z}$$\iff f(2m-1007)$$=4m-1007,\forall m\in \mathbb{Z}$

Thay $m$ bởi $m+503$ thì có :

$$f(2m-1)=4m+1005=2(2m-1)+1007,\forall m\in \mathbb{Z}$$

Tức là :

$$f(n)=2n+1007,\forall n\in \mathbb{Z},2\nmid n$$

Tuy nhiên ta cũng có :

$$f(n+1007)=f(n)+2014,\forall n\in \mathbb{Z}$$

Từ đó ta sẽ dễ dàng suy ra được rằng :

$$\boxed{f(n)=2n+1007,\forall n\in \mathbb{Z}}$$

Đây là đáp số duy nhất của bài toán.

Bài toán : Có tồn tại hay không một dãy số thực vô hạn $(a_n)$ sao cho các đa thức :

$$P_n(x)=a_0+a_{1}x+...+a_n{x}^n$$

có $n$ nghiệm thực phân biệt với mọi $n\ge 1$ ?

Lời giải :

Câu trả lời là có. Ta xây dựng dãy $(a_n)$ bằng quy nạp.

Với $n=1$ thì hiển nhiên là tồn tại đa thức $P_1(x)=a_0+a_{1}x$ có đúng một nghiệm thực.

Gỉa sử nhận định trên đúng với $n$, tức là tồn tại một dãy $(a_n)$ vô hạn mà đa thức :

$$P_n(x)=a_0+a_{1}x+...+a_n{x}^n$$

có đủ $n$ nghiệm thực phân biệt. Ta sẽ chỉ ra tồn tại số hạng $a_{n+1}$ tiếp theo của dãy số thoả mãn đa thức :

 $$P_{n+1}(x)=a_0+a_{1}x+...+a_n{x}^n+a_{n+1}{x}^{n+1}$$

có $n+1$ nghiệm thực phân biệt.

Thật vậy,

Ta chọn ra $n+2$ giá trị tuỳ ý $b_0<b_1<b_2<...<b_n<b_{n+1}$.

Lúc này ta sẽ chọn hệ số $a_{n+1}$ thoả mãn :

$\left|a_{n+1}\right|$$\le \underset{0\le i\le n+1}{\min }\left|\frac{P_n(b_i)}{b_i^{n+1}}\right|$

Thì đa thức $P_{n+1}$ sẽ có $n+1$ nghiệm phân biệt.

Thực như vậy, với cách chọn $a_{n+1}$ như vậy thì :

$\min \left\{\frac{-P_n(b_0)}{b_0^{n+1}},\frac{-P_n(b_1)}{b_1^{n+1}}\right\}$$\le a_{n+1}$$\le \max \left\{\frac{-P_n(b_0)}{b_0^{n+1}},\frac{-P_n(b_1)}{b_1^{n+1}}\right\}$

Suy ra rằng :

$\left(P_n(b_0)+a_{n+1}{b}_0^{n+1}\right)\left(P_n(b_1)+a_{n+1}{b}_1^{n+1}\right)$$\le 0$$\iff P_{n+1}(b_0)P_{n+1}(b_1)$$\le 0$

Hoàn toàn tương tự :

$$P_{n+1}(b_1)P_{n+1}(b_2)\le 0$$

$$...$$

$$P_{n+1}(b_n)P_{n+1}(b_{n+1})\le 0$$

Tức là trên $n+1$ khoảng $(b_0,b_1),(b_1,b_2),...,(b_n,b_{n+1})$ , đa thức $P_{n+1}(x)$ sẽ có $n+1$ nghiệm phân biệt.

Quy nạp hoàn tất.

Và câu trả lời cho bài toán là “có”.

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 : 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 (Kiểm tra trường Đông toán học miền Nam 2013-2014)

Cho dãy số $(a_n)$ thỏa $a_1=\frac{1}{3},a_2=\frac{2}{7}$ và :

$$a_{n+1}=\frac{1}{2}+\frac{a_n}{3}+\frac{a_{n-1}^2}{6}$$

Chứng minh dãy trên có giới hạn hữu hạn và tính giới hạn này.

Lời giải :

Ta chứng minh từ số hạng thứ hai trở đi, dãy $(a_n)$ là dãy tăng. Thật vậy, dễ kiểm tra được $a_3>a_2$. Gỉa sử $a_{k+1}>a_k,\forall k=\overline{2,n}$. Từ đó :

$$a_{n+2}-a_{n+1}=\frac{a_{n+1}-a_n}{3}+\frac{a_n-a_{n-1}}{6}.(a_n+a_{n-1})$$

Cũng dễ thấy $a_n>0$ nên $a_{n+2}>a_{n+1}$. Theo nguyên lí quy nạp ta được dãy $(a_n)$ tăng.

Dễ dàng chứng minh được bằng quy nạp $a_n\le 1,\forall n$. Từ đó ta được dãy $(a_n)$ hội tụ về giới hạn $L$. Chuyển qua giới hạn :

$L$$=\frac{1}{2}+\frac{L}{3}+\frac{L^2}{6}$$\iff L\in \left\{1,3\right\}$$\Rightarrow L$$=1$

Vậy dãy $(a_n)$ hội tụ và $\underset{n\to +\infty }{\lim }{a}_n=1$

Bài toán : Cho $a$ là số thực thỏa mãn điều kiện $sin(a)\ne 0$. Chứng minh rằng với mọi giá trị nguyên $n\ge 2$, đa thức 

$$P_n(x)=x^{n}sin(a)-x.sin(na)+sin(n-1)a$$ 

chia hết cho đa thức $Q(x)=x^2-2x.cos(a)+1$.

Lời giải :

Với $n=2$, ta có :

$$P_2(x)=x^{2}sin(a)-x.sin(2a)+sin(a)=sin(a)\left[x^2-2cos(a).x+1\right]=sin(a).Q(x)⋮Q(x)$$

Gỉa sử có $P_n(x)=x^n.sin(a)-x.sin(na)+sin(n-1)a⋮Q(x)$. Xét với $n+1$ :

Ta có :

$$P_{n+1}(x)=x^{n+1}sin(a)-x.sin(n+1)a+sin(na)$$

$$=x\left[x^n.sin(a)-x.sin(na)+sin(n-1)a\right]+x^2.sin(na)-x.sin(n-1)a-x.sin(n+1)a+sin(na)$$

$$=x.P_n(x)+sin(na).\left[x^2-2x.cos(a)+1\right]+2sin(na).cos(a).x-x.sin(n-1)a-x.sin(n+1)a$$

$$=x.P_n(x)+sin(na).Q(x)+x\left[2sin(na).cos(a)-sin(n-1)a-sin(n+1)a\right]$$

$=x.P_n(x)+sin(na).Q(x)+x\left[2sin(na).cosa-2sin(na).cos(a)\right]$$=x.P_n+sin(na).Q(x)⋮Q(x)$

Theo nguyên lí quy nạp, bài toán được chứng minh.

Bài toán (Japan Mathematical Olympiad Finals 2009)

Tìm tất cả các số nguyên dương $n$ sao cho $8^n+n$ chia hết cho $2^n+n$.

Lời giải :

Ta có $2^n+n\mid 8^n+n^3$, lại theo đề bài thì $2^n+n\mid 8^n+n$. Dẫn đến :

$$2^n+n\mid n^3-n$$

Ta chứng minh bằng quy nạp rằng nếu $n\ge 10$ thì :

$$2^n>n^3(\ast )$$

Gỉa sử có $(\ast )$. Ta cần chứng minh $2^{n+1}>(n+1{)}^3$. Do có $(\ast )$ nên ta chỉ cần chứng minh :

$$2n^3>(n+1{)}^3\iff n^3>3n^2+3n+1\iff n^2(n-9)+n(n^2-9)+(n^3-3)>0$$

Và vì $n\ge 10$ nên điều này luôn đúng. Theo nguyên lí quy nạp ta có :

$$2^n>n^3,\forall n\in \mathbb{N},n\ge 10$$

Kéo theo $2^n+n>n^3-n$. Thế nhưng lại có $2^n+n\mid n^3-n\Rightarrow n^3-n\ge 2^n+n$. Hai điều này mâu thuẫn nhau.

Từ đó ta có $n\le 9$. Thử trực tiếp ta được đáp số của bài toán là :

$$n\in \left\{1,2,4,6\right\}$$

Bài toán (VMO 2014)

Cho hai dãy số dương $(x_n),(y_n)$ thỏa $x_1=1,y_1=\sqrt{3}$ và :

$$\{\begin{array}{c}{x}_n{y}_{n+1}-x_n=0\\ x_{n+1}^2+y_n=2\end{array}$$

Chứng minh rằng hai dãy $(x_n),(y_n)$ có giới hạn hữu hạn. Tính các giới hạn đó.

Lời giải :

Ta tính được :

$x_2$$=\sqrt{2-\sqrt{3}}$$=\sqrt{2\left(1-\frac{\sqrt{3}}{2}\right)}$$=\sqrt{2\left(1-cos\frac{\pi }{6}\right)}$$=2sin\frac{\pi }{12}$

$y_2$$=\frac{x_1}{x_2}$$=\frac{1}{\sqrt{2-\sqrt{3}}}$$=\sqrt{2+\sqrt{3}}$$=\sqrt{2\left(1+cos\frac{\pi }{6}\right)}$$=2cos\frac{\pi }{12}$

Ta chứng minh được bằng quy nạp :

$$\{\begin{array}{c}{x}_n=2sin\frac{\pi }{3.2^n}\\ y_n=2cos\frac{\pi }{3.2^n}\end{array}$$

Từ đó suy ra ngay :

$\underset{n\to +\infty }{\lim }{x}_n$$=\underset{n\to +\infty }{\lim }\left(2.sin\frac{\pi }{3.2^n}\right)$$=0$

$\underset{n\to +\infty }{\lim }{y}_n$$=\underset{n\to +\infty }{\lim }\left(2.cos\frac{\pi }{3.2^n}\right)$$=1$