Quy nạp toán học là một kĩ thuật được sử dụng trong việc chứng minh các mệnh đề. Ý tưởng của nguyên lí quy nạp tương tự như việc làm đổ các thanh domino được xếp liên tiếp nhau. Để đảm bảo rằng các thanh domino đều đổ, ta cần đảm bảo rằng thanh đầu tiên sẽ đổ và các thanh được đặt đủ gần nhau sao cho nếu thanh đứng trước đổ thì thanh đứng sau cũng đổ theo. Tương tự, để chứng minh một mện đề $P(n)$ đúng với mọi $n$, ta cần chứng minh hai bước sau Chứng minh $P(1)$ đúng. Chứng minh nếu $P(n)$ đúng thì $P(n+1)$ đúng với mọi $n.$ $\boxed{\text{Ví dụ 1}}$ Cho $k$ và $n$ là các số nguyên không âm với $n\ge k.$ Chứng minh rằng $$C^{k+1}_{n+1}=C_k^k+C^k_{k+1}+\ldots+C_n^k.$$ GiảiXét mệnh đề $P(n)$ là $C^{k+1}_{n+1}=C_k^k+C^k_{k+1}+\ldots+C_n^k.$ Đầu tiên ta chứng minh mệnh đề đúng với $n=k$. Điều này là hiển nhiên vì $$C^{k+1}_{k+1}=C_k^k=1.$$ Giả sử $P(n)$ đúng, ta cần chứng minh $P(n+1)$ đúng, tức $$C^{k+1}_{n+2}=C_k^k+C^k_{k+1}+\ldots+C^k_{n+1}.$$ Chú ý rằng $$C_{k}^k+C^k_{k+1}+\ldots+C^k_{n+1}=\left[C_{k}^k+C^k_{k+1}+\ldots+C^k_{n}\right]+C^k_{n+1}$$ nên ta chỉ cần chứng minh $$C^{k+1}_{n+2}=C_{n+1}^{k+1}+C^k_{n+1}.$$ Điều này đúng theo công thức Pascal (có thể chứng minh bằng biến đổi tương đương). Ta đến với một số bài toán cùng dạng này. $\boxed{\text{Bài toán 1}}$ Chứng minh rằng $$1^2+2^2+\ldots+n^2=\dfrac{n(n+1)(2n+1)}{6}$$ với mọi số nguyên dương $n$. $\boxed{\text{Bài toán 2}}$ Chứng minh rằng nếu $q$ là số thực khác $1$ và $n$ là số nguyên dương thì $$1+q+q^2+\ldots+q^n=\dfrac{q^{n+1}-1}{q-1}.$$ $\boxed{\text{Bài toán 3}}$ Chứng minh rằng $\dfrac{1}{\sqrt{1}}+\dfrac{1}{\sqrt{2}}+\ldots+\dfrac{1}{\sqrt{n}}\ge \sqrt{n}$ với mọi $n$ nguyên dương.
$\boxed{\text{Ví dụ 2}}$ (IMO 2002) Cho $n$ là một số nguyên dương và $S$ là tập hợp các điểm $(x,y)$ trên mặt phẳng với $x,y$ không âm và $x+y< n$. Các điểm trong $S$ được tô màu đỏ hoặc xanh theo qui luật, nếu $(x,y)$ là màu đỏ thì $(x',y')$ được tô màu đỏ với $x\leq x'$ và $y\leq y'$. Đặt $A$ là số cách chọn $n$ điểm xanh mà hoành độ $x$ của nó khác nhau và đặt $B$ là số cách chọn $n$ điểm xanh mà tung độ $y$ của chúng khác nhau. Chứng minh rằng $A=B$ Spoiler: Lời giải Gọi $a_0,..,a_{n-1}$ là số điểm xanh có hoành độ bằng $0,1,..,n-1$. Gọi $b_0,..,b_{n-1}$ là số điểm xanh có tung độ bằng $0,1,..,n-1$. Khi đó, ta có $A=a_0...a_{n-1},B=b_0...b_{n-1}$. Ta cần chứng minh $A=B$ hay nói cách khác $a_0..a_{n-1}=b_0..b_{n-1}$. Ta nhận thấy rằng nếu trên đường chéo $x+y=n-1$ có một điểm màu đỏ thì $A=B=0$. Do đó ta chỉ nhìn trên trường hợp mà tất cả các điểm trên đường chéo đều màu xanh. Tuy nhiên, khi trong trường hợp này, ta lại đưa bài toán về việc đếm bài toán ban đầu với $n-1$, đáp án sẽ có được bằng cách cộng thêm vào mỗi $a'_i,b'_i$ với 1 (Với $a'_i$ là số điểm xanh có hoành độ bằng i trong hình $(x,y),x+y< n-1$ va $b_i$ cũng như vậy). Phân tích này dẫn đến việc chúng ta phải giải bài toán này bằng qui nạp. Ta sẽ tìm cách tính $A,B$ với $n$ từ việc tính $A,B$ với $n-1$. Quan sát thêm một chút, việc tô màu như đề cho sẽ cho chúng ta các hình tam giác vuông cân, từ đó nảy ra ý tưởng rằng $a_0,..,a_n$ là các hoán vị của $b_0,..,b_n$ (*). Ta sẽ chứng minh kết quả này bằng qui nạp. Với $n=1$ thì hình chỉ còn một điểm, khi đó $a_0=b_0=0$ hoặc $a_0=b_0=1$ nên (*) đúng với $n=1$ Giả sử (*) đúng với $n=k$, tức $a_0,..,a_{k-1}$ là hoán vị của $b_0,..,b_{k-1}$. Ta chứng minh (*) đúng với $n=k+1$. Gọi $c_k$ là số điểm xanh có hoành độ $k$ trong trường hợp $k+1$, $d_k$ là số điểm xanh có tung độ bằng $k$.Ta xét hai trường hợp Nếu tất cả các điểm trên đường $x+y=k$ đều là màu xanh thì ta có $c_i=a_i+1,d_i=b_i+1,i=0..k; c_k=d_k=1$ nên ta có đpcm Nếu tồn tại một điểm $(m,k-m)$ màu đỏ thì phần $(x,y):x\leq m,y\leq m$ đều màu đỏ, đặc biệt $c_m=d_{n-m}$. Xét hai phần $P=\left\{(x,y):x<m,y>k-m\right\}$ và $Q=\left\{(x,y):x>m,y<k-m\right\}$ thì ta có $a_i,a_{i+1},..,a_m$ là hoán vị của $b_0,b_1,..,b_{k-m}$ tương tự ta suy ra được đpcm.
$\boxed{\text{Ví dụ 3}}$ Có $n$ số nguyên dương có tổng bằng $2n-1$. Chứng minh rằng mọi số nguyên dương $S<2n$ đều có thể biểu diễn được dưới dạng tổng của một số số trong $n$ số trên.
$\boxed{\text{Ví dụ 4}}$ Chứng minh rằng trong $7$ đoạn thẳng độ dài tùy ý $d$ với $1\leq d\leq 13$ có thể chọn ra ba đoạn để làm ba cạnh của một tam giác.
$\boxed{\text{Ví dụ 5}}$ Cho $a_1,a_2,..,a_n$ là các số nguyên dương phân biệt và $M$ là tập $n-1$ số nguyên dương mà không chứa số $S=a_1+a_2+..+a_n$. Một con châu chấu chuẩn bị nhảy dọc theo trục số thực. Nó bắt đầu tại điểm $0$ và bắt đầu nhảy các bước nhảy có độ dài $a_1,..,a_n$ theo một thứ tự nào đó. Chứng minh rằng con châu chấu này có thể tìm được cách nhảy mà các lần nhảy của nó không có lần nào rơi vào các điểm thuộc tập $M$. Spoiler: Lời giải Ta chứng minh bằng nguyên lí quy nạp mạnh. Ta giả sử các bước nhảy là $a_1<a_2<\ldots<a_n$ và các phần tử của $M$ là $b_1<b_2<\ldots<b_{n-1}$. Đặt $s'=a_1+a_2+\ldots+a_{n-1}$. Nếu ta lấy $a_n$ và $b_{n-1}$, sẽ có hai trường hợp xảy ra $s'$ không nằm trong $n-2$ phần tử đầu tiên của $M$. Trong trường hợp này, theo nguyên lí quy nạp, ta có thể sắp xếp $n-1$ bước nhảy đầu tiên cho đến khi con châu chấu tới $s'$. Nếu tại một thời điểm nào đó con châu chấu nhảy vào $b_{n-1},$ ta thay đổi bước nhảy cuối cùng thành $a_n$ thì khi đó ta sẽ đến được $s$. Theo nguyên lí quy nạp, ta biết rằng châu chấu sẽ không bao giờ nhảy vào các điểm $b_1,b_2,\ldots,b_{n-2}.$ Thêm nữa, vì không có phần tử nào của $M$ sau $b_{n-1}$ nên việc châu chấu nhảy vào $b_k$ là không thể. $s'$ là một phần tử trong số $n-2$ phần tử đầu tiên của $M$. Vì $s'=s-a_n$ nằm trong $M$ nên trong số $2(n-1)$ phần tử có dạng $s-a_i,s-a_i-a_n$ với $1\le i\le n-1$, tồn tại ít nhất hai phần tử thuộc $M.$ Nếu ta nhìn vào các cặp phần tử $(s-a_i,s-a_i-a_n)$, vì ta có $n-1$ cặp như vậy và chúng chứa nhiều nhất $n-2$ phần tử của $M$ nên tồn tại $a_i$ thỏa mãn $s-a_i$ hoặc $s-a_i-a_n$ thuộc $M$. Chú ý rằng sau $s-a_i-a_n$, ta có $s'$ và $b_{n-1}$, là những phần tử của $M$. Do đó, có nhiều nhất $n-2$ phần tử của $M$ trước $s-a_i-a_n$. Theo nguyên lí quy nạp, ta có thể sử dụng $n-2$ bước nhảy để đến $s-a_i-a_n$ và nhảy tiếp $a_i$,$a_n$ để đến $s$ mà không chạm vào điểm nào của $M.$
