Bài giảng Chứng minh qui nạp

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Module #15:Chứng minh qui nạpInductive Proofs Rosen 5th ed., §3.3 ~11 slides, ~1 lecture §3.3: Qui nạp toán học Kỹ thuật mạnh dùng nhiều để chứng minh rằng vị từ P(n) là đúng đối với mỗi số tự nhiên n, không quan trọng lớn như thế nào. Bản chất nguyên lý “hiệu ứng domino”. Dựa trên luật suy diễn của logic vị từ: P(0)n0 (P(n)P(n+1))n0 P(n) “The First Principleof MathematicalInduction” “Hiệu ứng Domino” 0 1 2 3 4 5 6 … Giả thiết #1: Domino #0 đổ. Giả thiết #2: Với mọi nN,nếu domino #n đổ, thì domino #n+1 cũng sẽ đổ. Kết luận: Mọi dominoes đều đổ xuống! Note: this workseven if thereare infinitelymany dominoes! Lập luận qui tắc qui nạp C/m rằng k0 P(k) là khẳng định đúng:Cho trước bất kỳ k0, áp dụng suy luận n0 (P(n)P(n+1)) dễ dàng suy ra rằng n0 (n0, n0, prove P(n)P(n+1). Assuming n1 can be written as a product  pi = p1p2…ps of some series of s prime numbers. Let P(n)=“n has that property” Base case: n=2, let s=1, p1=2. Inductive step: Let n2. Assume 2kn: P(k). Consider n+1. If it’s prime, let s=1, p1=n+1.Else n+1=ab, where 1= 8 xu có thể dán bằng các tem 3 xu và 5 xu Chứng minh: phân trường hợp Không có nghiệm nguyên dương. G/s có:a0 nhỏ nhất là thành phần nghiệm a0 chẵn, a0 = 2a1, suy ra a1 nhỏ hơn a0, mâu thuẫn giả thuyết => không có nghiệm