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

H

huuhuantutin

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

1. Tại sao phải dùng phương pháp quy nạp toán học?
Giả sử có 1mệnh đề chứa biến số tự nhiên. Ta cần chứng minh mệnh đề đó. Tại sao phải dùng phương pháp quy nạp toán học? Để trả lời câu hỏi này, ta xét các bài toán sau:

Bài toán 2. Người ta kiểm tra trên một quần thể ruồi giấm thấy thế hệ đầu tiên có tính trạng mắt đỏ. Kết luận: “Tất cả ruồi giấm ở mọi thế hệ của quần thể này đều mắt đỏ”. Kết luận như vậy có đúng không? Nếu không làm thế nào để có kết luận đúng?

Lời giải. Kết luận như vậy chưa chắc đúng vì chưa kiểm tra xem các thế hệ khác có mắt đỏ không? Ta không thể làm như bài toán 1 vì số lượng ruồi giấm và các thế hệ của quẩn thể là vô số, việc kiểm tra từng cá thể của từng thế hệ là không thể thực hiện được. Để thu được kết luận đúng, ta làm như sau:
  • Kiểm tra với thế hệ thứ nhất (đời F1);
  • Chứng minh sự di truyền của tính trạng mắt đỏ. Tức là chứng minh rằng nếu đời bố mẹ mắt đỏ thì đời con mắt đỏ. Khi đó, chắc chắn tất cả các cá thể ở mọi thế hệ đều mắt đỏ vì thế hệ trước sẽ di truyền lại cho thế hệ sau.
  • Bài toán 3. Với [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]∈[/FONT][FONT=MathJax_AMS]N[/FONT][FONT=MathJax_Main]∗[/FONT], chứng minh rằng
[FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main].[/FONT]​
Phân tích.
Coi mệnh đề [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT] là một "tính trạng" của "quần thể" các số tự nhiên. Để chứng minh mọi số tự nhiên đều có "tính trạng [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT]" ta làm như sau:
  • Kiểm tra "tính trạng [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT]" với "thế hệ đầu (F1)" [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT]
  • Chứng minh sự “di truyền” của [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT] Tức là chứng minh rằng nếu số [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]k[/FONT] có "tính trạng [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT]" thì [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT] cũng có "tính trạng [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT]".
Phương pháp chứng minh như vậy gọi là phương pháp quy nạp toán học. Bạn cũng có thể hiểu phương pháp quy nạp giống như trò chơi Đôminô của người Nhật.
2. Phương pháp và ví dụ
Để chứng minh 1 mệnh đề [FONT=MathJax_Math]A[/FONT] đúng với mọi số nguyên dương bằng phương pháp quy nạp toán học, ta thực hiện 2 bước:

  1. (Bước "khởi tạo") Kiểm tra tính đúng đăn của [FONT=MathJax_Math]A[/FONT] với [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT].
  2. (Bước "di truyền") Giả sử mệnh đề [FONT=MathJax_Math]A[/FONT] đã đúng đến [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]≥[/FONT][FONT=MathJax_Main]1[/FONT], ta chứng minh [FONT=MathJax_Math]A[/FONT] cũng đúng với [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT].

Ta sẽ giải Bài toán 3 như sau:

Bước 1. Với [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT], ta có
[FONT=MathJax_Math]V[/FONT][FONT=MathJax_Math]T[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]V[/FONT][FONT=MathJax_Math]P[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main].[/FONT]​

Vậy [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT] đúng với [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT].
Bước 2. Giả sử [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT] đã đúng đến [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]≥[/FONT][FONT=MathJax_Main]1[/FONT], tức là
[FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]a[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main].[/FONT]​

Ta cần chứng minh rằng [FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]∗[/FONT][FONT=MathJax_Main])[/FONT] cũng đúng với [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT], tức là phải chứng minh
[FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]b[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main].[/FONT]​

Thật vậy:
[FONT=MathJax_Math]V[/FONT][FONT=MathJax_Math]T[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]b[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main].[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]V[/FONT][FONT=MathJax_Math]T[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]a[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT]
[FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]V[/FONT][FONT=MathJax_Math]P[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]a[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]k[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]V[/FONT][FONT=MathJax_Math]P[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]b[/FONT][FONT=MathJax_Main])[/FONT]

Mời các bạn làm thêm ví dụ dưới đây
Ví dụ 1. Với mọi [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]∈[/FONT][FONT=MathJax_AMS]N[/FONT][FONT=MathJax_Main]∗[/FONT] ta có: [FONT=MathJax_Main]2[/FONT][FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]>[/FONT][FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT].
 
R

riverflowsinyou1

Mệnh đề này đúng với 1 vì $2>1$
Giả sử mệnh đề này đúng với k tức là ta có $2k>k$ cần chứng minh $2(k+1)>k+1$
Xét $2(k+1)-k-1=2k-k+2-1=2k-k+1>0$
\Rightarrow đpcm
Bài tiếp cho $a>0$ chứng minh $a^3-a$ chia hết cho 3
 
R

ronaldover7

Mệnh đề này đúng với 1 với 1
Giả sử mệnh đề này đúng với k tức là ta có k^3-k chia hết cho 3 cần chứng minh (k+1)^3-(k+1) chia hết cho 3
=$k^3+3k^2+3k+1-k-1$=$k^3+3k^2+3k+1+ k^3-k-1-k^3$
=3k(k+1)+$k^3$-k chia hết cho 3
\Rightarrow dpcm
 
R

riverflowsinyou1

ronaldover7 said:
Mệnh đề này đúng với 1 với 1
Giả sử mệnh đề này đúng với k tức là ta có k^3-k chia hết cho 3 cần chứng minh (k+1)^3-(k+1) chia hết cho 3
=$k^3+3k^2+3k+1-k-1$=$k^3+3k^2+3k+1+ k^3-k-1-k^3$
=3k(k+1)+$k^3$-k chia hết cho 3
\Rightarrow dpcm
Bấm để xem đầy đủ nội dung ...

Bài này còn 2 cách khác :
Áp dụng định lí Fermat có 3 là số nguyên tố $n^3-n$ chia hết cho 3.
Cách 2: Ta có $n^3-n=n(n-1)(n+1)$ chia hết cho 3
 
You must log in or register to reply here.
Top Bottom