Lý thuyết phương pháp quy nạp toán học

Bài toán

Gọi $P\left( n \right)$ là một mệnh đề chứa biến $n\left( {n \in {N^*}} \right)$. Chứng minh $P\left( n \right)$ đúng với mọi số tự nhiên $n \in {N^*}$.

Phương pháp quy nạp toán học

- Bước 1: Chứng minh $P\left( n \right)$ đúng với $n = 1$.

- Bước 2: Với $k$ là một số nguyên dương tùy ý, giả sử $P\left( n \right)$ đúng với $n = k \ge 1$, chứng minh $P\left( n \right)$ cũng đúng khi $n = k + 1$.

Chú ý:

Đối với bài toán chứng minh $P\left( n \right)$ đúng với mọi $n \ge p$ với $p$ là số tự nhiên cho trước thì:

- Bước 1: Chứng minh $P\left( n \right)$ đúng với $n = p$.

- Bước 2: Với $k \ge p$ là một số nguyên dương tùy ý, giả sử $P\left( n \right)$ đúng với $n = k$, chứng minh $P\left( n \right)$ cũng đúng khi $n = k + 1$.

Ví dụ: Chứng minh ${n^7} - n$ chia hết cho $7$ với mọi $n \in {N^*}$.

Giải:

Đặt $P\left( n \right) = {n^7} - n$.

- Với $n = 1$ thì $P\left( 1 \right) = {1^7} - 1 = 0 \vdots 7$ nên $P\left( 1 \right)$ đúng.

- Giả sử mệnh đề đúng với $n = k \in {N^*}$, tức là $P\left( k \right) = \left( {{k^7} - k} \right) \vdots 7$.

Ta phải chứng minh mệnh đề đúng với $n = k + 1$, tức là: $P\left( {k + 1} \right) = {\left( {k + 1} \right)^7} - \left( {k + 1} \right) \vdots 7$

Ta có: ${\left( {k + 1} \right)^7} - \left( {k + 1} \right)$ $= C_7^0.{k^7} + C_7^1.{k^6} + C_7^2.{k^5} + C_7^3.{k^4}$ $+ C_7^4.{k^3} + C_7^5.{k^2} + C_7^6.k + C_7^7 - \left( {k + 1} \right)$

$= {k^7} + 7{k^6} + 21{k^5} + 35{k^4} + 35{k^3}$ $+ 21{k^2} + 7k + 1 - k - 1$ $= \left( {{k^7} - k} \right) + 7\left( {{k^6} + 3{k^5} + 5{k^4} + 5{k^3} + 3{k^2} + k} \right)$

Do $({k^7} - k) \vdots 7$ và $7\left( {{k^6} + 3{k^5} + 5{k^4} + 5{k^3} + 3{k^2} + k} \right) \vdots 7$ nên $P\left( {k + 1} \right) = {\left( {k + 1} \right)^7} - \left( {k + 1} \right) \vdots 7$.

Vậy mệnh đề đã cho đúng.