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

Quy nạp<br /> <br /> 1<br /> <br /> Trần Vĩnh Đức<br /> HUST<br /> <br /> Ngày 21 tháng 1 năm 2014<br /> <br /> 1<br /> <br /> Tham khảo: E.Lehman, T. Leighton, A. Meyer, Mathematics for CS<br /> <br /> Nội dung<br /> <br /> Nguyên lý quy nạp Ví dụ lát gạch Ví dụ chuyển chữ Quy nạp mạnh Unstacking Game<br /> <br /> Nguyên lý quy nạp<br /> <br /> Xét vị từ P(n) trên N. Nếu<br /> ▶ ▶<br /> <br /> P(0) đúng, và với mọi n ∈ N, (P(n) ⇒ P(n + 1)),<br /> <br /> thì P(n) đúng với mọi n ∈ N.<br /> <br /> Ví dụ<br /> <br /> Định lý<br /> Với mọi n ∈ N, 1 + 2 + ··· + n = Đặt P(n) là mệnh đề<br /> n ∑ i=1<br /> <br /> n(n + 1) 2<br /> <br /> i=<br /> <br /> n(n + 1) 2<br /> <br /> Chứng minh.<br /> ▶ ▶<br /> <br /> 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.<br /> <br /> Theo quy nạp ta có P(n) đúng với mọi số n ∈ N.<br /> <br />