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

1

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 .

ThuVienDeThi.com

2

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

ThuVienDeThi.com