Hôm nay chúng ta sẽ học về phép quy nạp toán học. Thông thường, chúng ta sẽ dùng quy nạp để chứng minh một phát biểu nào đó đúng với mọi số tự nhiên.
Để tiện cho việc diễn đạt, chúng ta sẽ gọi $P(n)$ là một phát biểu nào đó liên quan đến biến số tự nhiên $n$. Chứng minh bằng quy nạp sẽ gồm các bước sau.
Bước 1: gọi là bước khởi điểm. Chúng ta sẽ chứng minh $P(n)$ đúng cho trường hợp đầu tiên là $n=0$.
Bước 2: gọi là bước quy nạp. Bước này là bước quan trọng nhất. Ở bước này,
- chúng ta giả sử rằng $P(n)$ đúng cho các trường hợp $0 \leq n \leq k$,
- với giả thiết đó, chúng ta sẽ chứng minh $P(n)$ cũng đúng với trường hợp $n=k+1$.
Từ hai bước này, theo nguyên lý quy nạp toán học, chúng ta sẽ kết luận rằng $P(n)$ sẽ đúng với mọi số tự nhiên $n$.
Bây giờ chúng ta sẽ dùng quy nạp để giải bài toán đầu tiên.
Bài toán 1. Chứng minh rằng $$1 + 3 + 5 + 7 + \dots + (2n+1) = (n+1)^2.$$
Lời giải. Chúng ta sẽ chứng minh bằng quy nạp theo biến số $n$ công thức sau
$$1 + 3 + 5 + 7 + \dots + (2n+1) = (n+1)^2.$$
Bước 1. Với $n=0$, chúng ta có $$1 = (0+1)^2$$
Như vậy công thức ở trên đúng cho trường hợp $n=0$.
Bước 2. Giả sử công thức đúng cho các trường hợp $0 \leq n \leq k$. Chúng ta sẽ chứng minh rằng công thức trên cũng đúng cho trường hợp $n=k+1$, có nghĩa là chúng ta sẽ chứng minh $$1 + 3 + 5 + 7 + \dots + (2k+1) + (2k+3) = (k+2)^2.$$
Thực vậy, theo giả thiết quy nạp thì công thức đúng cho trường hợp $n=k$, cho nên $$1 + 3 + 5 + 7 + \dots + (2k+1) = (k+1)^2.$$
Do đó, $$1 + 3 + 5 + 7 + \dots + (2k+1) + (2k+3) = (k+1)^2 + (2k+3) = k^2 + 4k + 4 = (k+2)^2.$$
Như vậy chúng ta đã chứng minh rằng công thức đúng cho trường hợp $n=k+1$.
Theo nguyên lý quy nạp toán học thì công thức phải đúng với mọi số tự nhiên $n$. $\blacksquare$
Như vậy chúng ta đã biết cách chứng minh bằng quy nap.
Muốn chứng minh $P(n)$ đúng với mọi số tự nhiên $n$, chúng ta
- chứng minh $P(0)$ đúng
- chúng ta chứng minh rằng nếu $P(0), P(1), \dots, P(k)$ đúng thì $P(k+1)$ cũng đúng.
Bước chứng minh quy nạp (bước thứ 2) là bước quan trọng nhất bởi vì nhờ nó chúng ta có:
- vì $P(0)$ đúng nên $P(1)$ đúng
- vì $P(0), P(1)$ đúng nên $P(2)$ đúng
- vì $P(0), P(1), P(2)$ đúng nên $P(3)$ đúng
- vì $P(0), P(1), P(2), P(3)$ đúng nên $P(4)$ đúng
- v.v...
Bây giờ chúng ta tiếp tục giải tiếp một vài bài toán cho quen với phương pháp chứng minh quy nạp.
Bài toán 2. Chứng minh rằng với mọi số tự nhiên $n$, luôn tồn tại hai số nguyên $x$ và $y$ sao cho $$x^2 - 2012 y^2 = 13^n .$$
Lời giải. Chúng ta sẽ chứng minh bằng quy nạp theo $n$ mệnh đề sau đây
Tồn tại hai số nguyên $x$ và $y$ để cho $x^2 - 2012 y^2 = 13^n$.
Với $n=0$, chúng ta có $$13^0 = 1 = 1^2 - 2012 \times 0^2 .$$
Như vậy mệnh đề trên đúng cho trường hợp $n=0$.
Giả sử rằng mệnh đề trên đúng với các trường hợp $0 \leq n \leq k$. Chúng ta sẽ chứng minh mệnh đề cũng đúng cho trường hợp $n=k+1$, tức là, chúng ta sẽ chứng minh rằng tồn tại hai số nguyên $x$ và $y$ để cho $$x^2 - 2012 y^2 = 13^{k+1} .$$
Thực vậy, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, tức là chúng ta có thể tìm được hai số nguyên $a$ và $b$ sao cho $$a^2 - 2012 b^2 = 13^k$$
Mặt khác, chúng ta lại có $$45^2 - 2012 \times 1^2 = 13$$
Do đó dùng hằng đẳng thức $$(u^2 - d v^2)(s^2 - d t^2) = (us + d vt)^2 - d (ut + vs)^2$$ chúng ta suy ra $$13^{k+1} = (a^2 - 2012 b^2)(45^2 - 2012 \times 1^2) = (45 a + 2012 b)^2 - 2012 (a + 45 b)^2.$$
Mặt khác, chúng ta lại có $$45^2 - 2012 \times 1^2 = 13$$
Do đó dùng hằng đẳng thức $$(u^2 - d v^2)(s^2 - d t^2) = (us + d vt)^2 - d (ut + vs)^2$$ chúng ta suy ra $$13^{k+1} = (a^2 - 2012 b^2)(45^2 - 2012 \times 1^2) = (45 a + 2012 b)^2 - 2012 (a + 45 b)^2.$$
Như vậy chúng ta đã chứng minh được mệnh đề đúng cho trường hợp $n=k+1$.
Theo nguyên lý quy nạp toán học, chúng ta kết luận rằng, với mọi số tự nhiên $n$ thì sẽ tồn tại $x$ và $y$ để $13^n = x^2 - 2012 y^2$. $\blacksquare$
Ở bài toán sau đây thì bước khởi điểm là $n=5$ chứ không phải là $n=0$.
Bài toán 3. Chứng minh rằng với mọi $n \geq 5$, chúng ta có bất đẳng thức $2^n > n^2$.
Lời giải. Chúng ta sẽ chứng minh bất đẳng thức $2^n > n^2$ bằng quy nạp theo $n$.
Với $n =5$, chúng ta có $$2^5 = 32 > 5^2 = 25$$
Do đó bất đẳng thức đúng cho trường hợp $n=5$.
Giả sử rằng bất đẳng thức đúng cho các trường hợp $5 \leq n \leq k$. Chúng ta sẽ chứng minh bất đẳng thức đúng cho trường hợp $n=k+1$.
Thực vậy, theo giả thiết quy nạp thì bất đẳng thức đúng cho trường hợp $n=k$, nên chúng ta có $$2^k > k^2.$$
Do đó $$2^{k+1} = 2 \times 2^k > 2k^2 = (k+1)^2 + (k-1)^2 -2 .$$
Vì $k \geq 5$ nên $(k-1)^2 -2 > 0$, do đó $$2^{k+1} > (k+1)^2.$$
Vậy bất đẳng thức đúng cho trường hợp $n=k+1$. Theo nguyên lý quy nạp thì bất đẳng thức $2^n > n^2$ đúng với mọi số tự nhiên $n \geq 5$. $\blacksquare$
Hẹn các bạn ở kỳ sau, chúng ta sẽ giải thêm một vài bài toán khác bằng phương pháp quy nạp.
Bài tập về nhà.
1. Chứng minh rằng $$1!1 + 2!2 + 3!3 + \dots + n!n = (n+1)! - 1 .$$
2. Chứng minh rằng với mọi số tự nhiên $n$, luôn tồn tại hai số nguyên $x$ và $y$ sao cho $$x^2 + y^2 = 5^n .$$
3. Chứng minh rằng $$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{n^2} \leq 2 - \frac{1}{n}.$$