Bài giảng Quy nạp do Trần Vĩnh Đức biên soạn có nội dung trình bày nguyên lý quy nạp, ví dụ lát gạch, ví dụ chuyển chữ, quy nạp mạch, unstacking game. Các ví dụ được chứng minh chi tiết dễ hiểu nhằm giúp người học hiểu rõ hơn về nguyên lý trên. | Quy nạp 1 Trần Vĩnh Đức HUST Ngày 21 tháng 1 năm 2014 1 Tham khảo: , T. Leighton, A. Meyer, Mathematics for CS Nội dung Nguyên lý quy nạp Ví dụ lát gạch Ví dụ chuyển chữ Quy nạp mạnh Unstacking Game Nguyên lý quy nạp Xét vị từ P(n) trên N. Nếu ▶ ▶ P(0) đúng, và với mọi n ∈ N, (P(n) ⇒ P(n + 1)), thì P(n) đúng với mọi n ∈ N. Ví dụ Định lý Với mọi n ∈ N, 1 + 2 + ··· + n = Đặt P(n) là mệnh đề n ∑ i=1 n(n + 1) 2 i= n(n + 1) 2 Chứng minh. ▶ ▶ Bước cơ sở: P(0) đúng. Bước quy nạp: Ta sẽ chứng minh: với mọi n ≥ 0, mệnh đề P(n) ⇒ P(n + 1) đúng. Thật vậy, giả sử P(n) đúng, với n là một số nguyên bất kỳ. Vì 1 + 2 + · · · + n + (n + 1) = (1 + 2 + · · · + n) + (n + 1) n(n + 1) + (n + 1) = 2 (n + 1)(n + 2) = 2 nên P(n + 1) đúng. Theo quy nạp ta có P(n) đúng với mọi số n ∈ N.
