3.5 Các quy tắc suy diễnTam đoạn luậnĐược thể hiện bởi hằng đúng:[[p → q] ∧ [q → r]] → [p → r]Ví dụ 3.8: Nếu An đi học thì Dũng ở nhàNếu Dũng ở nhà thì Dũng làm bài tậpVậy: Nếu An đi học thì Dũng làm bài tậpVí dụ 3.9: A, B và C là 3 cầu thủ của đội bóng. Huấn luyện viênquy định:Nếu A tham gia trận đấu thì B không được tham giaNếu B không được tham gia trận đấu thì C cũng không đượctham giaVậy: Nếu A tham gia trận đấu thì C không được tham gia. 3.5 Các quy tắc suy diễnPhương pháp phủ định [quy tắc Modus Tollens]Thể hiện bởi hằng đúng:[[p → q] ∧ ¬q] → ¬p 3.5 Các quy tắc suy diễnTam đoạn luận rời[[p ∨ q] ∧ ¬p] → qVí dụ: Giả sử cuộc thi điền kinh có 2 người tham gia Avà B.A phải đạt giải nhất hay B phải đạt giải nhấtmà: A không đạt giải nhấtVậy: B phải đạt giải nhất Các quy tắc suy diễn [tt]Quy tắc mâu thuẩn [phản chứng]Ta có tương đương logic[[p1∧p2 ∧… ∧pn] → q] ⇔ [[p1∧p2 ∧… ∧pn ∧¬q] →0]Quy tắc chứng minh theo trường hợp: Thể hiện bởi hằngđúng:[[p → r] ∧ [q → r]] → [[p ∨ q] → r] Một số ví dụVí dụ 3.7: Cho diễn đạt:Nếu An học chăm thì An được xếp hạng cao trong học tậpMà An không được xếp hạng cao.Vậy An không học chăm [Phương pháp phủ định].Viết một cách hình thức cho suy diễn trên như sau:Gọi p: “An học chăm”q: “An được xếp hạng cao trong học tập”Ta có:p → q [tiền đề]¬ q [tiền đề]∴ ¬p[Phương pháp phủ định] Một số ví dụVí dụ 3.8:Rút gọn[p∨ q] ∧¬ [¬ p∧ q]Ta có:[p∨ q] ∧¬ [¬ p∧ q]⇔ [p∨ q] ∧ [p∨¬ q][luật De Morgan]⇔ [[p ∨ q] ∧ p] ∨ [[p ∨ q] ∧ ¬ q] [luật phân phối]⇔ p ∨ [[p ∧ ¬ q] ∨ [q ∧¬ q]][luật hấp thụ, phân phối]⇔ p ∨ [[p ∧ ¬ q] ∨ 0][luật phần tử bù]⇔ p ∨ [p ∧ ¬ q][luật trung hòa]⇔ p[luật hấp thụ] Một số ví dụTừ nhận xét trên, ta có 2 đoạn chương trình trên là tươngđương:if [[p || q] && [![!p && q]]]if [p]{{Thực hiện S;}Thực hiện S;}Ví dụ 3.8b: Chứng minh [[p ∧ q]→ r] ⇔ [p → [q → r]] Một số ví dụTừ nhận xét trên, ta có 2 đoạn chương trình trên là tươngđương:if [p]if [p && q]if [q]r;r;z=0;z=0;
for [int i=1; i
for [int i=1; i{{x = i+2;x = i+2;y=i-1;y=i-1;if [x>=10]
if [[x>=10] && [y1 thì 12 >1 }
Nhận thấy rằng giả thiết 1>1 là sai, bất chấp kết luận 12 >1 là đúng hay sai thì P[1] là đúng.
Dựa vào dòng 1 và dòng 3 của bảng chân trị, nhận thấy rằng khi Q đúng, bất chấp giả thiết P là đúng hay sai thì mệnh đề P→Q là luôn đúng. Vậy, để chứng minh mệnh đề P→Q là đúng, người ta chỉ cần chứng minh rằng Q là đúng. Phương pháp chứng minh này được gọi là chứng minh tầm thường.
Phương pháp chứng minh tầm thường cũng được sử dụng để chứng minh các trường hợp đặc biệt của định lý. Trường hợp tổng quát thì định lý này luôn đúng với mọi số n nguyên dương.
Ví dụ : Cho hàm mệnh đề
P[n] = { Nếu a và b là 2 số nguyên dương và a ≥ b thì an ≥ bn }
Chứng minh rằng P[0] là đúng.
Giải : Ta có a0 = b0 =1. Do đó a0 ≥ b0 là đúng.
Vậy P[0] là đúng bất chấp giả thiết a≥b là đúng hay sai.
Trong dòng 1 của bảng chân trị, mệnh đề P kéo theo Q có thể được chứng minh bằng cách chỉ ra rằng nếu P đúng thì Q cũng phải đúng. Nghĩa là tổ hợp P đúng Q sai không bao giờ xảy ra. Phương pháp này được gọi là chứng minh trực tiếp.
Vậy để thực hiện phương pháp chứng minh trực tiếp, người ta giả sử rằng P là đúng, sau đó sử dụng các qui tắc suy luận hay các định lý để chỉ ra rằng Q là đúng và kết luận P→Q là đúng.
Ví dụ 1: Chứng minh rằng { Nếu n là số lẻ thì n2 là số lẻ }
Giải : Giả sử rằng giả thiết của định lý này là đúng, tức là n là số lẻ. Ta có
n = 2k + 1 [ k=0,1,2,...]
⇒ n2 = [2k + 1]2 = 4k2 + 4k + 1
= 2[2k + 2k] + 1 là lẻ.
Vậy nếu n là số lẻ thì n2 là số lẻ.
Ví dụ 2 : Cho hàm mệnh đề P[n] = " Nếu n>1 thì n2 >n "
Chứng minh rằng P[n] là đúng với n là số nguyên dương.
Giải : Giả sử n > 1 là đúng, ta có :
n = 1 + k [ k ≥ 1]
⇒ n2 = [ 1 + k ]2 = 1 + 2k + k2 = [1 + k] + k + k2 > n
Vậy Nếu n>1 thì n2 >n .
Vì mệnh đề P→Q ⇔ Q → P. Do đó, để chứng minh mệnh đề P→Q là đúng, người ta có thể chỉ ra rằng mệnh đề Q → P là đúng.
Ví dụ : Chứng minh định lý { Nếu 3n + 2 là số lẻ thì n là số lẻ }
Giải : Giả sử ngược lại kết luận của phép kéo theo là sai, tức n là chẳn.
Ta có n = 2k [ k∈N ]
⇒ 3n + 2 = 3.2k + 2 = 2[ 3k + 1 ] là số chẳn
Vậy Nếu 3n + 2 là số lẻ thì n là số lẻ
Nhận xét
- Có những bài toán có thể sử dụng phương pháp chứng minh trực tiếp hay gián tiếp đều được cả. Tuy nhiên, có những bài toán không thể sử dụng phương pháp chứng minh trực tiếp được hoặc sử dụng trực tiếp thì bài giải sẽ dài dòng phức tạp hơn là sử dụng chứng minh gián tiếp [ hoặc ngược lại]. Đây chính là sự khác biệt của chứng minh trực tiếp và chứng minh gián tiếp.
Ví dụ 1 :
Sử dụng chứng minh gián tiếp để chứng minh rằng " Nếu n>1 thì n2 >n "
Giải : Giả sử ngược lại kết luận của phép kéo theo là sai, tức là n2 < n.
Vì n là nguyên dương nên ta có thể chia 2 vế cho n mà bất đẳng thức không đổi chiều. Ta có : n < 1.
Vậy từ Q đã dẫn đến P. Do đó, Nếu n>1 thì n2 >n.
Ví dụ 2 : Sử dụng chứng minh trực tiếp để chứng minh rằng " Nếu 3n + 2 là số lẻ thì n là số lẻ ".
Giải : Giả sử 3n + 2 là số lẻ là đúng.
Nhận thấy rằng vì 2 là số chẳn nên suy ra được 3n là số lẻ.
Vì 3 là số lẻ do đó n là số lẻ.
Vậy Nếu 3n + 2 là số lẻ thì n là số lẻ.
Ở đây chúng ta phải chứng minh thêm định lý là tích của 2 số lẻ là một số lẻ thì bài giải chặt chẽ hơn. Do đó, trong bài toán này việc sử dụng chứng minh gián tiếp là hay hơn dùng trực tiếp.
- Để chứng minh mệnh đề có dạng :
[P1∨P2∨...∨Pn] → Q
Chúng ta có thể sử dụng hằng đúng sau :
[[P1∨P2∨...∨Pn] →Q] [[P1→Q]∧[P2→Q]∧....∧[Pn→Q]]
Cách chứng minh này gọi là chứng minh từng trường hợp.
Ví dụ 3: Chứng minh rằng:
" Nếu n không chia hết cho 3 thì n2 không chia hết cho 3".
Giải : Gọi P là mệnh đề "n không chia hết cho 3" và Q là mệnh đề "n2 không chia hết cho 3". Khi đó, P tương đương với P1 ∨ P2. Trong đó:
P1 = " n mod 3 =1"
P2 = " n mod 3 =2"
Vậy, để chứng minh P → Q là đúng, có thể chứng minh rằng:
[P1 ∨ P2] → Q hay là [P1 → Q ] ∧ [ P2→ Q]
Giả sử P1 là đúng. Ta có, n mod 3 = 1. Đặt n = 3k + 1
[ k là số nguyên nào đó].
Suy ra
n2 = [ 3k+1]2 = 9k2 + 6k + 1 = 3[3k2 + 2k] + 1 không chia chẳn cho 3.
Do đó, P1 → Q là đúng.
Tương tự, giả sử P2 là đúng. Ta có, n mod 3 = 2. Đặt n = 3k + 2 [ k là số nguyên nào đó].
Suy ra n2 = [ 3k+2]2 = 9k2 + 12k + 4 = 3[3k2 + 4k + 1] + 1 không chia chẳn cho 3.
Do đó, P2 → Q là đúng.
Do P1 → Q là đúng và P2 → Q là đúng, hay là [P1 → Q ] ∧ [ P2→ Q].
Vậy [P1 ∨ P2] → Q.
Chứng minh phản chứng thường được sử dụng để chứng minh mệnh đề P là đúng. Trước hết, người ta giả sử ngược lại rằng P là sai hay P là đúng. Từ mệnh đề P là đúng dẫn đến kết luận Q sao cho P→Q phải đúng. Khi đó, người ta chỉ ra rằng Q là một mâu thuẩn, nghĩa là :
Q = R ∧R. [Sở dĩ có mâu thuẩn này là do ta giả sử P là sai]
Vì P→Q phải đúng và Q là F, suy ra rằng P = F ⇒ P = T.
Phương pháp chứng minh phản chứng thường được sử dụng để chứng minh những vấn đề cơ bản và điều quan trọng trong kỹ thuật này là tìm ra được mâu thuẩn R∧R.
Ví dụ 1: Chứng minh rằng " 2 size 12{ sqrt {2} } {} là số vô tỉ ".
Giải : Gọi P là mệnh đề " 2 size 12{ sqrt {2} } {} là số vô tỉ ". Giả sử ngược lại P là đúng. Vậy, 2 size 12{ sqrt {2} } {} là số hữu tỉ [ vì tập số thực gồm 2 tập con là tập số vô tỉ và tập số hữu tỉ. Hai tập con này không có 3 giao nhau]. Khi đó ∃a,b [a,b∈N] sao cho:
2 size 12{ sqrt {2} } {} = ab size 12{ { {a} over {b} } } {} [ với a, b không có ước chung hay phân số này là tối giản [mệnh đề R]]
Bình phương hai vế : 2 = a2b2 size 12{ { {a rSup { size 8{2} } } over {b rSup { size 8{2} } } } } {} ⇒ 2b2 = a2 ⇒ a2 là số chẳn ⇒ a là số chẳn.
Đặt a = 2c, c ∈ N.
Ta có 2b2 = 4c2 ⇔ b2 = 2c2 ⇒ b2 là số chẳn ⇒ b là số chẳn.
Vậy a, b đều có ước chung là 2 [mệnh đề R].
Điều này mâu thuẩn vì a/b là tối giản. Từ P→ R∧R.
Sở dĩ có mâu thuẩn này là do ta giả sử 2 size 12{ sqrt {2} } {} là số hữu tỉ. Vậy 2 size 12{ sqrt {2} } {} phải là số vô tỉ.
Ví dụ 2 : Một trong những cách giải bài toán tồn tại là dùng lập luận phản chứng.
Cho 7 đoạn thẳng có độ dài lớn hơn 10 và nhỏ hơn 100. Chứng minh rằng luôn tìm được 3 đoạn để có thể ghép thành một tam giác.
Giải : Trước hết sắp xếp các đoạn đã cho theo thứ tự tăng dần của độ dài a1, a2, ..., a7, và chứng minh rằng trong dãy đã xếp luôn tìm được 3 đoạn liên tiếp sao cho tổng của 2 đoạn đầu lớn hơn đoạn cuối [vì điều kiện để 3 đoạn có thể ghép thành một tam giác là tổng của 2 đoạn nhỏ hơn đoạn thứ ba].
Giả sử điều cần chứng minh là không xảy ra, nghĩa là đồng thời xảy ra các bất đẳng thức sau:
a1 + a2 ≤ a3
a2 + a3 ≤ a4
a3 + a4 ≤ a5
a4 + a5 ≤ a6
a5 + a6 ≤ a7
Từ giả thiết a1 , a2 có giá trị lớn hơn 10, ta nhận được a3 > 20 . Từ a2 >10 và a3 > 20
ta nhận được a4 > 30 , a5 > 50, a6 > 80 và a7 > 130. Điều a7 > 130 là mâu thuẩn với giả thiết các độ dài nhỏ hơn 100. Có mâu thuẩn này là do giả sử điểu cần chứng minh không xảy ra.
Vậy, luôn tồn tại 3 đoạn liên tiếp sao cho tổng của 2 đoạn đầu lớn hơn đoạn cuối. Hay nói cách khác là 3 đoạn này có thể ghép thành một tam giác.
Giả sử cần tính tổng n số nguyên lẻ đầu tiên. Với n = 1,2,3,4,5 ta có :
n = 1: 1 = 1 = 12
n = 2: 1 + 3 = 4 = 22
n = 3: 1 + 3 + 5 = 9 = 32
n = 4: 1 + 3 + 5 + 7 = 16 = 42
n = 5: 1 + 3 + 5 + 7 + 9 = 25 = 52
Từ các kết quả này ta dự đoán tổng n số nguyên lẻ đầu tiên là n2. Tuy nhiên, chúng ta cần có phương pháp chứng minh dự đoán trên là đúng.
Qui nạp toán học là một kỹ thuật chứng minh rất quan trọng. Người ta dùng nó để chứng minh những kết quả đã có dựa trên sự suy luận nào đó như ví dụ trên. Tuy nhiên, qui nạp toán học chỉ dùng để chứng minh các kết quả nhận được bằng một cách nào đó chứ không là công cụ để phát hiện ra công thức.
- Nguyên lý chứng minh qui nạp yếu
Nhiều định lý phát biểu rằng P[n] là đúng ∀n nguyên dương, trong đó P[n] là hàm mệnh đề, ký hiệu ∀nP[n]. Qui nạp toán học là một kỹ thuật chứng minh các định lý thuộc dạng trên. Nói cách khác qui nạp toán học thường sử dụng để chứng minh các mệnh đề dạng ∀nP[n].
Nguyên lý chứng minh qui nạp yếu bao gồm 2 bước :
- Kiểm tra P[x0] là đúng với x0 là giá trị đầu tiên của dãy số n
- Giả sử rằng P[k] là đúng khi n=k. Từ đó suy ra rằng P[k+1] là đúng.
Ta có cách viết của suy luận trên như sau:
[P[x0] ∧ [P[k]→P[k+1]]] → ∀nP[n]
Ví dụ 1: Chứng minh rằng
∑ i = 1 n i = 1 + 2 + 3 + . . . + n = n [ n + 1 ] 2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{n} } {i} =1+2+3+ "." "." "." +n= { {n \[ n+1 \] } over {2} } } {}
Giải : Đặt P[n] = ∑i=1ni=n[n+1]2 size 12{ left lbrace Sum cSub { size 8{i=1} } cSup { size 8{n} } {i} = { {n \[ n+1 \] } over {2} } right rbrace } {}
- Với n= 1 : 1 = 1[1+1]2 size 12{ { {1 \[ 1+1 \] } over {2} } } {} P[1] là đúng
- Giả sử P[k] là đúng khi n=k. Ta có : ∑i=1ki=k[k+1]2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{k} } {i} = { {k \[ k+1 \] } over {2} } } {}
Cần chứng minh rằng P[k+1] là đúng. Nghĩa là
∑i=1k+1i=[k+1][k+2]2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{k+1} } {i} = { { \[ k+1 \] \[ k+2 \] } over {2} } } {} [điều phải chứng minh]
Ta có : ∑i=1K+1i=∑i=1Ki+[k+1]=k[k+1]2+[k+1]=[k+1][k+2]2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K+1} } {i} = Sum cSub { size 8{i=1} } cSup { size 8{K} } {i} + \[ k+1 \] = { {k \[ k+1 \] } over {2} } + \[ k+1 \] = { { \[ k+1 \] \[ k+2 \] } over {2} } } {} [đpcm]
Vậy ∀nP[n].
Ví dụ 2: Chứng minh rằng
P[n] = ∑i=1ni[i+1]!=1−1[n+1]! size 12{ left lbrace Sum cSub { size 8{i=1} } cSup { size 8{n} } { { {i} over { \[ i+1 \] !} } } =1 - { {1} over { \[ n+1 \] !} } right rbrace } {}
- Với n=1 : 12=1−12 size 12{ { {1} over {2} } =1 - { {1} over {2} } } {} P[1] là đúng
- Giả sử P[k] là đúng khi n= k. Ta có :
∑ i = 1 K i [ i + 1 ] ! = 1 − 1 [ k + 1 ] ! size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K} } { { {i} over { \[ i+1 \] !} } } =1 - { {1} over { \[ k+1 \] !} } } {}
Cần chứng minh rằng :
∑ i = 1 K + 1 i [ i + 1 ] ! = 1 − 1 [ k + 2 ] ! size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K+1} } { { {i} over { \[ i+1 \] !} } } =1 - { {1} over { \[ k+2 \] !} } } {}
Ta có :
∑ i = 1 K + 1 i [ i + 1 ] ! = ∑ i = 1 K i [ i + 1 ] ! + k + 1 [ k + 2 ] ! = 1 − 1 [ k + 1 ] ! + k + 1 [ k + 2 ] ! size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K+1} } { { {i} over { \[ i+1 \] !} } } = Sum cSub { size 8{i=1} } cSup { size 8{K} } { { {i} over { \[ i+1 \] !} } } + { {k+1} over { \[ k+2 \] !} } =1 - { {1} over { \[ k+1 \] !} } + { {k+1} over { \[ k+2 \] !} } } {}
=1−[k+2]−[k+1][k+2]!=1−1[k+2]! size 12{ {}=1 - { { \[ k+2 \] - \[ k+1 \] } over { \[ k+2 \] !} } =1 - { {1} over { \[ k+2 \] !} } } {} [đpcm]
Vậy ∀nP[n]
Ví dụ 3 : Chứng minh bất đẳng thức sau :
n < 2n với n nguyên dương.
- Khi n=1 : 1 < 2 mệnh đề đúng
- Giả sử mệnh đề đúng khi n=k, ta có k < 2k .
Cần chứng minh rằng k + 1< 2k+1 .
Thật vậy, vì k < 2k ⇒ k +1 < 2k +1 < 2k + 2k = 2k+1.
Do đó, n < 2n với n nguyên dương.
Khi sử dụng nguyên lý chứng minh qui nạp, không được bỏ qua bước kiểm tra P[x] là đúng vì nếu chỉ có [P[n]→P[n+1]] là không đủ để kết luận rằng ∀nP[n] là đúng.
Ví dụ : Xét
P[n]= ∑i=0ni=0+1+2+3+...+n=[n+3][n−2]2 size 12{ left lbrace Sum cSub { size 8{i=0} } cSup { size 8{n} } {i} =0+1+2+3+ "." "." "." +n= { { \[ n+3 \] \[ n - 2 \] } over {2} } right rbrace } {}
Giả sử P[k] là đúng khi n=k. Ta có :
∑ i = 0 K i = 0 + 1 + 2 + 3 + . . . + k = [ k + 3 ] [ k − 2 ] 2 size 12{ Sum cSub { size 8{i=0} } cSup { size 8{K} } {i} =0+1+2+3+ "." "." "." +k= { { \[ k+3 \] \[ k - 2 \] } over {2} } } {}
Cần chứng minh:
∑ i = 0 K + 1 i = 0 + 1 + 2 + 3 + . . . + k + [ k + 1 ] = [ k + 3 ] [ k − 1 ] 2 size 12{ Sum cSub { size 8{i=0} } cSup { size 8{K+1} } {i} =0+1+2+3+ "." "." "." +k+ \[ k+1 \] = { { \[ k+3 \] \[ k - 1 \] } over {2} } } {}
Ta có :
∑ i = 0 K + 1 i = ∑ i = 0 K i + [ k + 1 ] = [ k + 3 ] [ k − 2 ] 2 + [ k + 1 ] size 12{ Sum cSub { size 8{i=0} } cSup { size 8{K+1} } {i} = Sum cSub { size 8{i=0} } cSup { size 8{K} } {i} + \[ k+1 \] = { { \[ k+3 \] \[ k - 2 \] } over {2} } + \[ k+1 \] } {}
VT = k 2 − 2k + 3k − 6 + 2k + 2 2 = k 2 + 3k − 4 2 size 12{ ital "VT"= { {k rSup { size 8{2} } - 2k+3k - 6+2k+2} over {2} } = { {k rSup { size 8{2} } +3k - 4} over {2} } } {}
VT=[k−1][k+4]2=P[k+1] size 12{ ital "VT"= { { \[ k - 1 \] \[ k+4 \] } over {2} } =P \[ k+1 \] } {} [đpcm]
Ta có P[k]→P[k+1] là đúng.
Tuy nhiên, khi xét P[0]: P[0] = {0 = 3} là mệnh đề sai.
Vậy ∀nP[n] là sai.
Trong trường hợp này ta có thể kết luận như sau : Nếu P[k] là đúng và nếu ∀ n≥k[P[k] → P[k+1]] là đúng thì ∀ n≥k, P[n] là đúng.
Đôi khi chúng ta cần tính toán một biểu thức phụ thuộc vào n, bắt đầu là việc đoán ra kết quả, công việc này được làm bằng cách ít hay nhiều dựa vào kinh nghiệm. Sau đó, sử dụng nguyên lý chứng minh qui nạp để chứng minh rằng kết quả vừa tìm được là đúng.
Ví dụ 1: Tính tổng n số lẻ đầu tiên.
S = 1+3+5+7+...+[2n-1] = ∑i=1n[2i−1] size 12{ Sum cSub { size 8{i=1} } cSup { size 8{n} } { \[ 2i - 1 \] } } {}
Khi n=1 : S = 1 = 12
n=2 : S = 1+ 3 = 22
n=3 : S = 1+3 + 5 = 32
n=4 : S = 1+3+5+7 = 42
n=5 S = 1+3+5+7+9 = 52
...........................................
Vậy có thể dự đoán rằng S = ∑i=1n[2i−1] size 12{ Sum cSub { size 8{i=1} } cSup { size 8{n} } { \[ 2i - 1 \] } } {} = n2
Sau đó sử dụng chứng minh qui nạp để chứng minh kết quả vừa tìm được.
Đặt P[n] = ∑i=1n[2i−1]=n2 size 12{ left lbrace Sum cSub { size 8{i=1} } cSup { size 8{n} } { \[ 2i - 1} \] =n rSup { size 8{2} } right rbrace } {}
- Khi n=1 : 1 = 1 P[1] là đúng
- Giả sử rằng P[k] là đúng khi n=k. Ta có :
∑ i = 1 K [ 2i − 1 ] = k 2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K} } { \[ 2i - 1} \] =k rSup { size 8{2} } } {}
cần chứng minh P[k+1] là đúng, nghĩa là :
∑ i = 1 K + 1 [ 2i − 1 ] = [ k + 1 ] 2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K+1} } { \[ 2i - 1} \] = \[ k+1 \] rSup { size 8{2} } } {}
Vế trái = ∑i=1K[2i−1]+[2[k+1]−1]=k2+[2k+1]=[k+1]2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K} } { \[ 2i - 1} \] + \[ 2 \[ k+1 \] - 1 \] =k rSup { size 8{2} } + \[ 2k+1 \] = \[ k+1 \] rSup { size 8{2} } } {} [đpcm]
Vậy ∀nP[n].
Ví dụ 2: Tổng trên có thể tính toán với một cách khác như sau :
S = ∑i=1n[2i−1]=2∑i=1ni−∑i=1n1=2n[n+1]2−n=n[n+1]−n=n2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{n} } { \[ 2i - 1 \] } =2 left [ Sum cSub { size 8{i=1} } cSup { size 8{n} } {i} - Sum cSub { size 8{i=1} } cSup { size 8{n} } {1} right ]=2 left [ { {n \[ n+1 \] } over {2} } - n right ]=n \[ n+1 \] - n=n rSup { size 8{2} } } {}
Ví dụ 3: Tính tổng
S = ∑i=1n1i[i+1] size 12{ Sum cSub { size 8{i=1} } cSup { size 8{n} } { { {1} over {i \[ i+1 \] } } } } {}
Khi n=1: S = 12=11+1 size 12{ { {1} over {2} } = { {1} over {1+1} } } {}
n=2: S = 12+12.3=3+12.3=23=22+1 size 12{ { {1} over {2} } + { {1} over {2 "." 3} } = { {3+1} over {2 "." 3} } = { {2} over {3} } = { {2} over {2+1} } } {}
n=3: S = 23+13.4=2.4+13.4=34=33+1 size 12{ { {2} over {3} } + { {1} over {3 "." 4} } = { {2 "." 4+1} over {3 "." 4} } = { {3} over {4} } = { {3} over {3+1} } } {}
n=4: S = 34+14.5=3.5+14.5=45=44+1 size 12{ { {3} over {4} } + { {1} over {4 "." 5} } = { {3 "." 5+1} over {4 "." 5} } = { {4} over {5} } = { {4} over {4+1} } } {}
..........................................
Vậy có thể dự đoán tổng S = nn+1 size 12{ { {n} over {n+1} } } {}
Sử dụng nguyên lý qui nạp để chứng minh công thức trên.
Đặt P[n] = ∑i=1n1i[i+1]=nn+1 size 12{ left lbrace Sum cSub { size 8{i=1} } cSup { size 8{n} } { { {1} over {i \[ i+1 \] } } } = { {n} over {n+1} } right rbrace } {}
- Khi n=1 : 1/2 = 1/2 P[1] là đúng
- Giả sử P[k] là đúng khi n=k. Ta có
∑ i = 1 K 1 i [ i + 1 ] = k k + 1 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K} } { { {1} over {i \[ i+1 \] } } } = { {k} over {k+1} } } {}
Cần chứng minh P[k+1] là đúng. Nghĩa là :
∑i=1K+11i[i+1]=k+1k+2 size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K+1} } { { {1} over {i \[ i+1 \] } } } = { {k+1} over {k+2} } } {} [đpcm]
Vế trái = ∑i=1K+11i[i+1]=∑i=1K1i[i+1]+1[k+1][k+2]=kk+1+1[k+1][k+2] size 12{ Sum cSub { size 8{i=1} } cSup { size 8{K+1} } { { {1} over {i \[ i+1 \] } } } = Sum cSub { size 8{i=1} } cSup { size 8{K} } { { {1} over {i \[ i+1 \] } } } + { {1} over { \[ k+1 \] \[ k+2 \] } } = { {k} over {k+1} } + { {1} over { \[ k+1 \] \[ k+2 \] } } } {}
=k[k+2]+1[k+1][k+2]=[k+1]2[k+1][k+2]=k+1k+2 size 12{ {}= { {k \[ k+2 \] +1} over { \[ k+1 \] \[ k+2 \] } } = { { \[ k+1 \] rSup { size 8{2} } } over { \[ k+1 \] \[ k+2 \] } } = { {k+1} over {k+2} } } {} [đpcm]
Vậy ∀nP[n].
- Nguyên lý chứng minh qui nạp mạnh
Cho P[n] là một đẳng thức có chứa biến n, nếu P[0] là đúng và nếu [P[0]∧ P[1]∧P[2]∧P[3]∧...P[k]] → P[k+1] là đúng thì P[n] là mệnh đề đúng ∀n [với 0 là phần tử đầu tiên].
Chú ý rằng, để tạo ra giả thiết qui nạp với nguyên tắc qui nạp yếu, người ta chỉ giả thiết rằng P[k] là đúng tại n=k. Với nguyên tắc qui nạp mạnh, người ta chỉ ra rằng giả thiết đúng cho tất cả các mệnh đề P[0]∧ P[1]∧P[2]∧P[3]∧...P[k]. Đây chính là sự khác biệt cơ bản của 2 nguyên tắc qui nạp với giả thiết yếu và giả thiết mạnh.
Ví dụ 1: Chứng minh rằng tích của 3 số liên tiếp luôn chia hết cho 6.
Giải : Đặt P[n] = {n.[n+1].[n+2] chia hết cho 6} [n nguyên dương]
Ta có : P[1] = 1.2.3 chia hết cho 6. Mệnh đề đúng.
P[2] = 2.3.4 chia hết cho 6. Mệnh đề đúng.
P[3] = 3.4.5 chia hết cho 6. Mệnh đề đúng.
................................
Giả sử ∀n≤ k ta có P[k] là đúng. Nghĩa là : k.[k+1].[k+2] chia hết cho 6.
Cần chứng minh rằng P[k+1] là đúng.
Nhận thấy: [k+1][k+2][k+3] = k.[k+1].[k+2] + 3.[k+1].[k+2]
Trong đó : k.[k+1].[k+2] chia hết cho 6.
Và 3.[k+1].[k+2] chia hết cho 6 = 2.3 [vì [k+1].[k+2] là tích của 2 số tự nhiên liên tiếp nên chia chẳn cho 2].
Vì tổng của 2 số chia hết cho 6 sẽ chia hết cho 6 [sinh viên tự chứng minh], do đó [k+1].[k+2][k+3] chia hết cho 6. P[n] đúng với mọi n nguyên dương.
Ví dụ 2: Chứng minh rằng nếu n là một số nguyên lớn hơn 1, khi đó n có thể được viết dưới dạng tích của các số nguyên tố.
Giải : Đặt P[n] = { n = a.b...c } [a, b,..,c là các số nguyên tố]
Ta có P[2] = { 2= 2.1}
P[3] = { 3= 3.1}
P[4] = { 4= 2.4}
......................
P[18] = { 6.3= 3.2.3}
.......................... là các mệnh đề đúng.
Giả sử P[n] đúng ∀n≥ 2 ta có P[k] là đúng.
Cần chứng minh rằng P[k+1] là đúng.
Với n = k+1 ta có 2 trường hợp xảy ra như sau:
- k+1 là số nguyên tố : k+1 = [k+1].1 P[k+1] đúng
- k+1 không là số nguyên tố [hợp số]: k+1 = a.b [ a,b,∈ [2,k] ]
Theo giả thiết qui nạp mạnh, a, b có thể là số nguyên tố hoặc là tích của các số nguyên tố. Vậy nếu k+1 là hợp số thì nó cũng sẽ được viết dưới dạng tích của các số nguyên tố. P[n] đúng vói mọi n ≥ 2.
Ví dụ 3: Chứng minh rằng mọi bưu phí bằng hay lớn hơn 12 xu đều có thể tạo ra bằng các con tem 4 xu hay 5 xu.
Giải : Đặt P[n] = { n = 4 + ...+ 5+....}
Ta có : P[12] = { 12 = 4 + 4 + 4}
P[13] = { 13 = 4 + 4 + 5}
P[14] = { 14 = 4 + 5 + 5}
P[15] = { 15 = 5+ 5 + 5}
P[16] = { 16 = 4 + 4 + 4 + 4 }
P[17] = { 17 = 4 + 4 + 4 + 5 }
Giả sử n > 15 và P[n] là đúng. Nhật thấy rằng để tạo ra bưu phí [n+1] xu ta chỉ cần dùng con tem n-3 xu và cộng thêm một tem 4 xu.