Thú vị trong việc chứng minh quy nạp
 

Hôm nay đi học môn Giải tích, thầy dạy về dãy số trong đó có nhiều bài sử dụng phép quy nạp. Và cuối giờ thầy đã nêu ra một bài chứng minh như sau khiến mình cũng cảm thấy khá thú vị khi chứng minh quy nạp, và tuy là phát hiện ra ngay lỗi sai, nhưng mình cũng đánh động phải cẩn thận hơn nữa khi dùng các phép chứng minh.

• Bài toán đưa ra như sau: Trong toàn bộ lớp học này, tôi sẽ chứng minh rằng, nếu có một em là nữ, thì toàn bộ cả lớp này đều là nữ cả (Và hiển nhiên là lớp mình có ít nhất 1 nữ :sexygirl: )
• Phép chứng minh mà thầy đưa ra:
  Gọi mệnh đề P(n): Trong một lớp có n học sinh mà có 1 em là nữ, thì toàn bộ lớp học là nữ.
  Ta có P(1) đúng!
  Giả sử P(n) đúng đến $n=k$, ta sẽ chứng minh P(n) đúng với $n=k+1$.
  Thật vậy giả sử có một tập hợp lớp học gồm $k+1$ phần tử học sinh $S=\{a_1, a_2, ..., a_{k+1} \}$, trong đó $a_1$ là một học sinh nữ.
  Xét $k$ phần tử đầu tiên $\{a_1, a_2, ..., a_k\}$. Vì P(k) đúng, nên toàn bộ các phần tử học sinh $a_2, ..., a_k$ đều là học sinh nữ!
  Xét $k$ phần tử cuối cùng $\{a_2, a_3, ..., a_{k+1} \} $. Vì P(k) đúng nên $a_{k+1}$ cũng là phần tử học sinh nữ. Vậy cả lớp đều là nữ! :))

Đến lượt bạn thử tìm xem bài chứng minh này sai ở đâu nhé :D

Bước cơ sở quy nạp sai vì $n=1$ với số nữ là $k=1$ đúng nhưng tới $n=2$ thì số nữ là $k=2=1$ (1 nữ ban đầu, vô lí). Cái này giống như chứng minh bằng quy nạp tất cả các số nguyên dương bằng nhau vậy :gach:.

Hihi:choleric:
Trong bước chứng minh quy nạp đúng với $n=k+1$ thầy có chia nhỏ tập $S=\{a_1, a_2, ..., a_{k+1} \}$ thành hai tập con là $\{a_1, a_2, ..., a_k\}$ và $\{a_2, a_3, ..., a_{k+1} \}$ thầy đã giả thiết rằng ở mỗi tập con này đều có ít nhất một nữ (như vậy mới dùng giả thiết quy nạp được thấy cũng có vẻ hợp lý quá ha!!!) nhưng với $n=2$ thì cách chia nầy sai (ta chỉ có $1$ nữ),vậy là $n=3,4....$ thiếu cơ sở để quy nạp rồi hihi:))

Để có thể dùng được ý "màu đỏ" thì cần phải có $k\ge2 $. Nếu kông thì tập "màu đỏ" sẽ rỗng, như thế không dùng tiếp để chứng minh cho ý "màu xanh" được.
Như thế bước giả thiết qui nạp cần phải là : Giả sử P(n) đúng đến n=k với k $\ge $ 2.
Vậy thì ở bước cơ sở cần phải kiểm tra P(1), P(2). Và trong chứng minh trên thì chưa kiểm tra P(2).