Bài giảng Quy nạp - Trần Vĩnh Đức

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Quy nạp - Trần Vĩnh ĐứcQuy nạp1Trần Vĩnh ĐứcHUSTNgày 21 tháng 1 năm 20141Tham khảo: E.Lehman, T. Leighton, A. Meyer, Mathematics for CSNội dungNguyên lý quy nạp Ví dụ lát gạch Ví dụ chuyển chữ Quy nạp mạnh Unstacking GameNguyên lý quy nạpXé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=1n(n + 1) 2i=n(n + 1) 2Chứ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.