Chứng minh 10 bài toán bằng quy nạp

Chứng minh10 bài toán bằng quy nạp
Có thể nói phương pháp chứng minh bằng quy nạp rất tiện dụng trong việc giải toán, nhất là một số bài toán số học “hóc búa”. Song, vận dụng cách chứng minh bằng quy nạp như thế nào thì cần rèn luyện qua nhiều dạng bài toán. 
TL này sưu tầm, tông hợp 10 bài giải mẫu và 9 Bài tập ứng dung cách chứng minh bằng quy nạp. Hi vọng có ích cho các bạn chuẩn bị thi HSG cũng như thi ĐH-CĐ.
I.- Bài mẫu
Bài toán 1. Chứng minh rằng “Tổng n số lẻ đầu tiên (Sn) bằng bình phương của n” (với n Î N* )
Sn = 1+3+5+7+⋯+(2n-1) = n 2 . [1]
Lời giải. Có nhiều cách CM, Ở đây Chứng minh bằng quy nạp theo các bước sau
Bước 1. Với n = 1 , ta có  
S1 = (1) 2   = 1
Như vậy công thức ở trên đúng cho trường hợp n=1 .
Bước 2. Giả sử công thức đúng cho các trường hợp 1 ≤ n ≤ k . ta phải 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à phải CM  
S (k+1) = 1+3+5+7+⋯+(2k)+(2k + 1)=(k+1) 2 . 
Bước 3 Theo giả thiết quy nạp thì công thức  [1] đúng cho trường hợp n = k  
S k = 1+3+5+7+⋯+(2k)=(k) 2 . 
Do đó,  1+3+5+7+⋯+(2k)+(2k+1)=(k2 +2k+1)=(k+1) 2 . 
Chứng tỏ rằng công thức đúng cho trường hợp n = k+1 .
Như vậy theo nguyên lý quy nạp toán học, . [1] đúng với mọi số tự nhiên n . ■  
Bài toán 2. Chứng minh rằng với mọi n ≥5 , chúng ta có bất đẳng thức 2 n > n   .
 (bài toán sau đây thì bước khởi điểm là n = 5  chứ không phải là n=1) 
Lời giải. 
Với n=5 , rõ ràng có  
2 5 = 32 > 5 2 =25 
 nghĩa là 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 ≤ n ≤ 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×2 k  > 2k 2 = (k+1) 2 +(k−1) 2 −2. 
Vì k≥5  nên (k−1) 2 −2>0  , do đó  
2 k+1 >(k+1) 2 . 
 bất đẳng thức đúng cho trường hợp n = k+1  .
 Vậy theo nguyên lý quy nạp, BĐT 2 n >n 2    đúng với mọi số tự nhiên n ≥ 5  . ■  
Bài toán 3. (bài toán sau đây thì bước khởi điểm là n = 0  chứ không phải là n=1) 
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 −2012y 2 =13 n  . 
Lời giải. 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 −2012y 2=13 n   .
Với n=0  , ta có 13 0 =1=1 2 −2012×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 ≤ n ≤ 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 −2012y 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 −2012b 2 =13 k  
Mặt khác, chúng ta lại có 
45 2 −2012×1 2 =13 
Do đó dùng hằng đẳng thức 
(u 2 −dv 2 )(s 2 −dt 2 )=(us+dvt) 2 −d(ut+vs) 2  
 chúng ta suy ra 
13 (k+1) =(a 2−2012b 2)(45 2 −2012×1 2 )=(45a+2012b) 2 −2012(a+45b) 2. 
Như vậy mệnh đề đúng cho trường hợp n=k+1  .
Theo nguyên lý quy nạp toán học, ta kết luận rằng, 
 với mọi số tự nhiên n , tồn tại x  và y  để 13 n  =x 2 −2012y 2   . ■  
Bài toán 4. Chứng minh đẳng thức
1×2×3+2×3×4+⋯+n(n+1)(n+2)=¼ n(n+1)(n+2)(n+3). [2]
Lời giải.Chứng minh bằng quy nạp rằng với mọi n≥1  thì 
1×2×3+2×3×4+⋯+n(n+1)(n+2)= ¼n(n+1)(n+2)(n+3).  
Với n=1  ta có 
1×2×3=6=¼1×2×3×4 
 công thức ở trên đúng cho trường hợp n=1  .
Giả sử công thức [2] đúng cho các trường hợp 1 ≤ n ≤ k  . Ta phải chứng minh công thức[2] cũng đúng cho trường hợp n=k+1  , có nghĩa là phải chứng minh 
1×2×3+⋯+k(k+1)(k+2)+(k+1)(k+2)(k+3)=1 4  (k+1)(k+2)(k+3)(k+4). 
Theo giả thiết quy nạp thì [2] đúng cho trường hợp n=k  , cho nên 
1×2×3+2×3×4+⋯+k(k+1)(k+2)=1 4  k(k+1)(k+2)(k+3). 
Do đó 
1×2×3+⋯+k(k+1)(k+2)+(k+1)(k+2)(k+3) =¼k(k+1)(k+2)(k+3)+(k+1)(k+2)(k+3) 
=¼ (k+1)(k+2)(k+3)(k+4). 
ÞTa đã chứng minh rằng công thức đúng cho trường hợp n=k+1  .
Vậy theo nguyên lý quy nạp toán học thì [2]phải đúng với mọi số tự nhiên n ≥1  . ■  
Bài toán 5. Chứng minh rằng 
Biểu thức ( 8 n + 42n−1. ) chia hết cho 49
Lời giải.Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau đây 
8 n + 42n−1=0(mod49) 
Với n=0  , ta có 
8 0 +42×0−1=0 
 Þ 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≤n≤k  . Chúng ta sẽ chứng minh mệnh đề cũng đúng cho n=k+1  , có nghĩa là ta phải chứng minh 
8 k+1 + 42.(k+1)−1=8 k+1 +42k+41 = 0(mod49). 
 Theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp n=k  , cho nên 
8 k +42k−1=0(mod49). 
 Þ8(8 k +42k−1)=8 k+1 +336k−8=0(mod49). 
 Þ8 k+1 +42k+41=(8 k+1 +336k−8)−49(6k−1)=0(mod49). 
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, mệnh đề phải đúng với mọi số tự nhiên n  . ■  
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, 
Chứng minh rằng công thức cho số Fibonacci thứ n () như sau
Lời giải. ta sẽ đặt 
α= ,   β= . 
Phải chứng minh bằng quy nạp mệnh đề sau 
 .*(α n −β n ) 
Với n=0  , chúng ta có 
 (α o − β o  )= 0 = F o   
Do đó mệnh đề trên đúng cho trường hợp n=0  .
Với n=1  , chúng ta có 
* (α 1 −β 1 )= = 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≤n≤k  trong đó k≥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 = *(α  k+1 −β k+1 ) 
Thực vậy, vì 0≤k−1≤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 = *(α k−1 −β 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 = *(α k −β k ) 
Từ đó suy ra 
F k+1 =F k−1 +F k = *[(α k−1 +α k )−(β k−1 +β k )] 
= *[α  k−1 (1+α)−β k−1 (1+β)] 
Chúng ta thấy rằng α  và β  là hai nghiệm của phương trình 1+x=x 2   , do đó 1+α=α 2   và 1+β=β 2   . Từ đó suy ra 
F k+1 = *(α k−1 α 2 −β k−1 β 2 )=  *(α k+1 −β 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  . ■  
Bài toán 7. Thừ công thức cos2α=2.cos 2α−1 
Chứng minh rằng có thể viết cos nα  thành một đa thức của biến cosα  .
Lời giải. Chúng ta chứng minh mệnh đề sau bằng quy nạp
Với mọi số tự nhiên n  , tồn tại một đa thức P n   sao cho cosnα=P n (cosα)  .
Với n=0  , ta có cos0=1 
do đó chúng ta có thể chọn đa thức P 0 (x)=1  và mệnh đề đúng với trường hợp n=0  .
Mệnh đề hiển nhiên đúng với trường hợp n=1  với đa thức P 1 (x)=x  .
Giả sử mệnh đề đúng với các trường hợp 0≤n≤k  trong đó k≥1  . Chúng ta sẽ chứng minh mệnh đề cũng đúng với trường hợp n=k+1  .
Ta có 
cos(k+1)α+ cos (k−1)α=2 cos kαcosα 
Do đó 
cos (k+1)α=2 cos kα cos α− cos (k−1)α 
Vì 0≤k−1<k , theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp n=k−1 ,
cho nên sẽ tồn tại một đa thức P k−1 (x) để cos (k−1)α=P k−1 (cos α) 
Cũng theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp n=k , Þ sẽ tồn tại một đa thức P k (x) để cos kα=P k (cos α) 
Từ đó suy ra ; cos(k+1)α=2P k (cos α) cos α−P k−1 (cos α) 
Do đó nếu chúng ta chọn đa thức 
P k+1 (x)=2P k (x)x−P k−1 (x) thì cos(k+1)α=P k+1 (cosα) . Như vậy thì mệnh đề đúng cho trường hợp n=k+1 .
Theo nguyên lý quy nạp thì mệnh đề đúng với mọi n . ■ 
Bài toán 8. 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, 
 Tìm tất cả các số n để F n > n 2 .
Lời giải. Ta có thể tính được
F 0 =0=0 2 ,F 1 =1=1 2 , F 2 =1<2 2 , F 3 =2<3 2, F 4 =3<4 2, 
F 5 =5<5 2,F 6 =8<6 2 ,F 7 =13<7 2,F 8 =21<8 2,F 9 =34<9 2
F 10 =55<10 2 , F 11 =89 < 11 2 , F 12 =144=12 2 , 
 F 13 =233>13 2 , F 14 =377>14 2
Chúng ta phải chứng minh bằng quy nạp mệnh đề sau
Với mọi số tự nhiên n ≥13 , F n > n 2 .
Theo tính toán ở trên 
 F 13 =233 >13 2 =169, F 14 =377>14 2 =196 
 do đó mệnh đề đúng với trường hợp n=13 và n=14
Giả sử mệnh đề đúng với các trường hợp 13 ≤ n ≤k  trong đó k≥14  . Chúng ta sẽ chứng minh mệnh đề cũng đúng với trường hợp n=k+1  .
Vì 13≤k−1<k  , theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp n=k−1  , do đó 
F k−1 > (k−1) 2  
Cũng theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp n=k  , 
 do đó F k > k 2  
Þ Từ đó suy ra 
Bởi vì k≥14 , cho nên k 2 −4k>0 , do đó F k+1 >(k+1) 2  . Như vậy mệnh đề đúng cho trường hợp n = k+1 .
Theo nguyên lý quy nạp thì mệnh đề đúng với mọi n ≥ 13 . 
Vậy F n > n 2   khi và chỉ khi n ≥ 13 . ■  
Bài toán 9. 
Cho n số khác nhau là n số bất kỳ. 
Chứng minh rằng tồn tại một đa thức P(x) sao cho 
P(x 1 )=y 1 ,P(x 2 )=y 2 ,,P(x n )=y n 
Lời giải. Chúng ta phảichứng minh mệnh đề sau
Tồn tại đa thức P n (x) thoã mãn 
P n (x 1 )=y 1 , P n (x 2 )=y 2 ,,P n (x n )=y n 
Với trường hợp n=1 , chúng ta chỉ cần chọn đa thức hằng số P 1 (x)=y 1 thì chúng ta sẽ có P 1 (x 1 )=y 1 . Vậy mệnh đề đúng cho trường hợp n=1 .
Giả sử mệnh đề đúng với các trường hợp 1≤n≤k . Chúng ta sẽ chứng minh mệnh đề cũng đúng với trường hợp n=k+1 .
Thực vậy, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp n=k , do đó sẽ tồn tại một đa thức P k (x) thõa mãn 
 P k (x 1 )=y 1 ,P k (x 2 )=y 2 ,,P k (x k )=y k 
Nếu chúng ta chọn 
P k+1 (x)=P k (x)+a(x−x 1 )(x−x 2 )(x−x k ) thì rõ ràng 
P k+1 (x 1 )=P k (x 1 )=y 1 ,P k+1 (x 2 )=P k (x 2 )=y 2 ,,P k+1 (x k )=P k (x k )=y k 
Chúng ta chỉ cần xác định giá trị của a sao cho P k+1 (x k+1 )=y k+1 .
Chúng ta có 
P k+1 (x k+1 )=P k (x k+1 )+a(x k+1 −x 1 )(x k+1 −x 2 )(x k+1 −x k ) 
Vậy để P k+1 (x k+1 )=y k+1 thì 
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 thì mệnh đề đúng với mọi n . ■  
Bài 10 : Chứng minh ngụy biện
Chúng ta có thể thấy rằng phương pháp chứng minh bằng quy nạp rất tiện dụng trong việc giải toán. Song, cách chứng minh bằng quy nạp cũng dễ dẫn đến những kết quả sai ( gọi là Ngụy biện) . Thí dụ mấy bài toán sau:
10.1/ CM đẳng thức vô lí 1=2012 này là đúng ?
 (Ta thử chỉ ra xem cách chứng minh này sai ở đâu ? )
CM Bắt đầu bằng việc xây dựng dãy số như sau:
 a0=2012, a1=1, an+1=2an−an−1. [3]
Chúng ta sẽ chứng minh bằng quy nạp theo biến số n mệnh đề sau đây,
Với mọi m, n thì am=am+1=⋯=am+n
*Với n=0, chúng ta có
am=am+0 è mệnh đề đúng cho trường hợp n=0.
*Giả sử mệnh đề đúng với các trường hợp 0≤n≤k. ta sẽ chứng minh mệnh đề đúng với trường hợp n=k+1. Tức là chứng minh rằng
 am=am+1=⋯=am+k+1
Thực vậy theo giả thiết quy nạp thì mệnh đề đúng với trường hợp n=k, cho nên
 am=am+1=⋯=am+k
Ngoài ra, bởi vì đẳng thức trên đúng với mọi m ta có thể thay m bằng m+1 
è ta có
 am+1=am+2=⋯=am+1+k
Từ đó chúng ta suy ra
 am=am+1=⋯=am+k=am+k+1
Như vậy ta đã chứng minh mệnh đề đúng cho trường hợp n=k+1.
Theo nguyên lý quy nạp thì mệnh đề đúng với mọi n.
Từ kết quả trên ta đã có được đẳng thức sau đây
 am=am+1=⋯=am+n
Thay m=0 và n=1, chúng ta sẽ có đẳng thức
 a0=a1 è tức là 2012=1
10.2 - Chứng minh 1=2013
Dùng dãy số như trên
 a0=2012, a1=1, an+1=2an−an−1. [3]
Chúng ta sẽ chứng minh bằng quy nạp theo biến số n mệnh đề sau đây,
*Với mọi n thì an=n+2012
*Với n=0, chúng ta có
 a0=2012=0+2012
Do đó mệnh đề đúng cho trường hợp n=0.
*Giả sử mệnh đề đúng với các trường hợp 0≤n≤k. ta chứng minh mệnh đề đúng với trường hợp n=k+1. Tức là chúng ta sẽ chứng minh rằng
 ak+1=(k+1)+2012=k+2013
Thực vậy theo giả thiết quy nạp thì mệnh đề đúng với trường hợp n=k−1, cho nên
 ak−1=(k−1)+2012=k+2011
Cũng theo giả thiết quy nạp thì mệnh đề đúng với trường hợp n=k, cho nên
 ak=k+2012
Do đó,
 ak+1=2ak−ak−1=2(k+2012)−(k+2011)=k+2013
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 thì mệnh đề đúng với mọi n.
Kết quả đã chứng minh được đẳng thức sau đây
 an=n+2012
Thay n=1, chúng ta sẽ có đẳng thức a1=1+2012=2013
Nhưng theo định nghĩa của dãy số thì a1=1, è vậy 2013=1
HD gỡ rối 
Hãy xem lại Điều ta đặt ra: “Bắt đầu bằng việc xây dựng dãy số “ [3]
Ta đã coi đây như một “tiên đề” mọi số ao; a1 .an chỉ còn ý nghĩa “ là một con số nào đó tùy chọn “ è a0 = a1 = an è 1 = 2012 = 2013 thế thôi !
II.- Bài tập thực hành
1. Chứng minh rằng  
1!*1+2!*2+3!*3+⋯+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  
. 
4.Tìm công thức tổng quát cho 
1×2×3+2×3×4+⋯+n(n+1)(n+2)=1 /4  n(n+1)(n+2)(n+3). 
5. Chứng minh rằng 
25 < 6 n −5 n−1 
Tìm công thức tổng quát cho bài toán này.
6. 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, 
Tìm tất cả các số n  để F n > 3n  .
7.-Trên mặt phẳng, cho n đường thẳng với hai tính chất sau
hai đường thẳng bất kỳ thì không song song với nhau 
ba đường thẳng bất kỳ thì không cắt nhau tại cùng một điểm
Chứng minh rằng n đường thẳng này cắt nhau tạo thành n(n−1)/2 điểm.
8- Bác bỏ ngụy biện 1>2  
(Đây là một bài ngụy biện; bạn hãy chỉ ra cách chứng minh này sai ở điểm nào.?)
Người ta sẽ dùng quy nạp ngụy biện để chứng minh rằng 1>2  .như sau: 
Cho dãy số xác định như sau: a 0 =1  , a 1 =1  , a n+1 =a n−1 +a n +11  .
Với mọi n  , thì a n >4n−2  
Với n=0  , thìcó 
a 0 =1>4×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≤n≤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 
 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 > 4n−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?!
-----------------------------------------------------------------------------------------------------
ST & biên soạn chỉnh lí Phạm Huy Hoạt 12 – 2012.