Quy nạp II

Hôm nay chúng ta tiếp tục giải tiếp một số bài toán bằng phương pháp quy nạp.

Bài toán 4. Chứng minh rằng $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$$

Lời giải. Chúng ta sẽ chứng minh bằng quy nạp rằng với mọi $n \geq 1$ thì $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$$

Với $n=1$, chúng ta có $$1 \times 2 \times 3= 6 = \frac{1}{4} 1 \times 2 \times 3 \times 4$$
Như vậy công thức ở trên đúng cho trường hợp $n=1$.

Giả sử công thức trên đúng cho các trường hợp $1 \leq n \leq k$. Chúng ta sẽ chứng minh rằng công thức cũng đúng cho trường hợp $n=k+1$, có nghĩa là chúng ta sẽ chứng minh $$1 \times 2 \times 3 + \dots + k (k+1)(k+2) + (k+1)(k+2)(k+3) = \frac{1}{4} (k+1)(k+2)(k+3)(k+4).$$

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 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + k (k+1)(k+2) = \frac{1}{4} k(k+1)(k+2)(k+3).$$

Do đó $$1 \times 2 \times 3 + \dots + k (k+1)(k+2) + (k+1)(k+2)(k+3)$$ $$= \frac{1}{4} k(k+1)(k+2)(k+3) + (k+1)(k+2)(k+3)$$ $$= \frac{1}{4} (k+1)(k+2)(k+3)(k+4).$$

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 \geq 1$. $\blacksquare$




Bài toán 5. Chứng minh rằng $$49 ~\mid~ 8^n + 42 n - 1.$$

Lời giải. Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau đây $$8^n + 42 n - 1 = 0 \pmod{49}$$

Với $n=0$, chúng ta có $$8^0 + 42 \times 0 - 1 = 0$$
Do đó mệnh đề trên đúng cho trường hợp $n=0$.

Giả sử rằng mệnh đề đúng cho 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$, có nghĩa là chúng ta sẽ chứng minh $$8^{k+1} + 42 (k+1) - 1 = 8^{k+1} + 42 k + 41 = 0 \pmod{49}.$$

Thực vậy, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, cho nên $$8^k + 42 k - 1 = 0 \pmod{49} .$$

Vì vậy, $$8(8^k + 42 k - 1) = 8^{k+1} + 336 k - 8 = 0 \pmod{49} .$$

Do đó $$8^{k+1} + 42 k + 41 = (8^{k+1} + 336 k - 8) - 49(6k - 1) = 0 \pmod{49} .$$

Như vậy chúng ta đã chứng minh mệnh đề đúng cho trường hợp $n=k+1$.

Theo nguyên lý quy nạp toán học thì mệnh đề phải đúng với mọi số tự nhiên $n$. $\blacksquare$




Chúng ta thấy rằng ở các bài toán mà chúng ta đã giải ở trên, ở bước quy nạp, để chứng minh $P(k+1)$ đúng, chúng ta chỉ sử dụng giả thiết là $P(k)$ đúng. Như vậy chúng ta chưa cần dùng đến giả thiết là $P(0)$, $P(1)$, ..., $P(k-1)$ đúng.

Trong bài toán tiếp theo đây, để chứng minh $P(k+1)$ đúng, chúng ta cần sử dụng hai giả thiết là $P(k-1)$ đúng và $P(k)$ đúng.



Bài toán 6. Dãy số Fibonacci được xác định như sau: $F_0 = 0$, $F_1 = 1$, $F_{n+1} = F_n + F_{n-1}$. Do đó
$$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \dots$$
Chứng minh rằng công thức cho số Fibonacci là như sau
$$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$

Lời giải. Để cho ngắn gọn, chúng ta sẽ đặt $$\alpha = \frac{1 + \sqrt{5}}{2}, ~~ \beta = \frac{1 - \sqrt{5}}{2}.$$

Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau $$F_n = \frac{1}{\sqrt{5}} ( \alpha^n - \beta^n )$$

Với $n=0$, chúng ta có $$\frac{1}{\sqrt{5}} ( \alpha^0 - \beta^0 ) = 0 = F_0$$
Do đó mệnh đề trên đúng cho trường hợp $n=0$.

Với $n=1$, chúng ta có $$\frac{1}{\sqrt{5}}  ( \alpha^1 - \beta^1 ) = \frac{1}{\sqrt{5}} \sqrt{5} = 1 = F_1$$
Do đó mệnh đề trên đúng cho trường hợp $n=1$.

Giả sử rằng mệnh đề đúng cho các trường hợp $0 \leq n \leq k$ trong đó $k \geq 1$. Chúng ta sẽ chứng minh mệnh đề cũng đúng cho trường hợp $n=k+1$, có nghĩa là chúng ta sẽ chứng minh $$F_{k+1} = \frac{1}{\sqrt{5}} ( \alpha^{k+1} - \beta^{k+1} )$$

Thực vậy, vì $0 \leq k-1 \leq k$, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k-1$, cho nên $$F_{k-1} = \frac{1}{\sqrt{5}} ( \alpha^{k-1} - \beta^{k-1} )$$

Cũng theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, cho nên $$F_{k} = \frac{1}{\sqrt{5}} ( \alpha^{k} - \beta^{k} )$$

Từ đó suy ra $$F_{k+1} = F_{k-1} + F_k = \frac{1}{\sqrt{5}} [ (\alpha^{k-1} + \alpha^{k}) - (\beta^{k-1} + \beta^{k})]$$ $$= \frac{1}{\sqrt{5}} [ \alpha^{k-1} (1 + \alpha) - \beta^{k-1} ( 1 + \beta)]$$

Chúng ta thấy rằng $\alpha$ và $\beta$ là hai nghiệm của phương trình $1+x=x^2$, do đó $1+\alpha=\alpha^2$ và $1+\beta=\beta^2$. Từ đó suy ra $$F_{k+1} = \frac{1}{\sqrt{5}} ( \alpha^{k-1} \alpha^2 - \beta^{k-1} \beta^2 ) =  \frac{1}{\sqrt{5}} ( \alpha^{k+1} - \beta^{k+1} )$$

Như vậy chúng ta đã chứng minh mệnh đề đúng cho trường hợp $n=k+1$.

Theo nguyên lý quy nạp toán học thì mệnh đề phải đúng với mọi số tự nhiên $n$. $\blacksquare$





Ở bài toán số 6, để chứng minh $P(k+1)$ đúng, chúng ta cần sử dụng hai giả thiết là $P(k-1)$ đúng và $P(k)$ đúng. Vì vậy mà ở bước khởi điểm, chúng ta phải chứng minh rằng $P(0)$ đúng và $P(1)$ đúng. Từ đó, nhờ bước quy nạp chúng ta có:

• 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...

từ đó, suy ra $P(n)$ đúng với mọi $n$.




Chứng minh $1 > 2$

Bây giờ chúng ta sẽ dùng quy nạp để chứng minh rằng $1 > 2$. Đố các bạn chỉ ra cách chứng minh này sai ở điểm nào.

Cho dãy số xác định như sau: $a_0 = 1$, $a_1 = 1$, $a_{n+1} = a_{n-1} + a_n + 11$.

Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau đây

Với mọi $n$, thì $a_n > 4 n - 2$

Với $n=0$, chúng ta có $$a_0 = 1 > 4 \times 0 - 2 = -2$$
Do đó mệnh đề trên đúng cho trường hợp $n=0$.

Giả sử rằng mệnh đề đúng cho 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$, có nghĩa là chúng ta sẽ chứng minh
$$a_{k+1} > 4(k+1) - 2 = 4k + 2$$

Thực vậy, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k-1$, cho nên
$$a_{k-1} > 4(k-1) - 2 = 4k - 6$$

Cũng theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, cho nên
$$a_{k} > 4k - 2$$

Từ đó suy ra
$$a_{k+1} = a_{k-1} + a_k + 11 > (4k - 6) + (4k - 2) + 11 = 8k + 3 > 4k + 2$$

Như vậy chúng ta đã chứng minh mệnh đề đúng cho trường hợp $n=k+1$.

Theo nguyên lý quy nạp toán học thì mệnh đề phải đúng với mọi số tự nhiên $n$.

Vậy chúng ta chứng minh xong bất đẳng thức
$$a_n > 4 n - 2$$

Thay $n=1$ vào bất đẳng thức trên chúng ta có
$$1 > 2$$

Vậy lời giải trên sai ở đâu?!




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. Tìm công thức tổng quát cho $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$$

2. Chứng minh rằng $$25 ~\mid~ 6^n - 5n - 1$$
Tìm công thức tổng quát cho bài toán này.

3. Với dãy số Fibonacci
$$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \dots$$
Tìm tất cả các số $n$ để $F_n > 3n$.