Module #15 – Inductive Proofs University of Florida Dept of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr Michael P Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H Rosen 12/03/15 (c)2001-2003, Michae Module #15 – Inductive Proofs Module #15: Chứng minh qui nạp Inductive Proofs Rosen 5th ed., §3.3 ~11 slides, ~1 lecture 12/03/15 (c)2001-2003, Michae Module #15 – Inductive Proofs §3.3: Qui nạp toán học • Kỹ thuật mạnh dùng nhiều để chứng minh vị từ P(n) số tự nhiên n, không quan trọng lớn • Bản chất nguyên lý “hiệu ứng domino” • Dựa luật suy diễn logic vị từ : P(0) “The First Principle of Mathematical ∀n≥0 (P(n)→P(n+1)) Induction” ∴∀n≥0 P(n) 12/03/15 (c)2001-2003, Michae Module #15 – Inductive Proofs “Hiệu ứng Domino” • Giả thiết #1: Domino #0 đổ • Giả thiết #2: Với n∈N, domino #n đổ, domino #n+1 đổ • Kết luận: Mọi dominoes đổ xuống! 12/03/15 (c)2001-2003, Michae … Note: this works even if there are infinitely many dominoes! Module #15 – Inductive Proofs Lập luận qui tắc qui nạp C/m ∀k≥0 P(k) khẳng định đúng: Cho trước k≥0, áp dụng suy luận ∀n≥0 (P(n)→P(n+1)) dễ dàng suy ∀n≥0 (n nghiệm 12/03/15 (c)2001-2003, Michae 36 [...]... thiết qui nạp 12/03 /15 (c)2001-2003, Michae 23 Module #15 – Inductive Proofs Kết luận 12/03 /15 (c)2001-2003, Michae 24 Module #15 – Inductive Proofs Chứng minh sai 12/03 /15 (c)2001-2003, Michae 25 Module #15 – Inductive Proofs Bước qui nạp 12/03 /15 (c)2001-2003, Michae 26 Module #15 – Inductive Proofs Lập luận 12/03 /15 (c)2001-2003, Michae 27 Module #15 – Inductive Proofs Kết luận 12/03 /15 (c)2001-2003,... nguyên lý qui nạp 1 12/03 /15 (c)2001-2003, Michae 18 Module #15 – Inductive Proofs Đặt tên mệnh đề qui nạp 12/03 /15 (c)2001-2003, Michae 19 Module #15 – Inductive Proofs Trường hợp cơ sở 12/03 /15 (c)2001-2003, Michae 20 Module #15 – Inductive Proofs Điều chỉnh lại 12/03 /15 (c)2001-2003, Michae 21 Module #15 – Inductive Proofs Bước qui nạp 12/03 /15 (c)2001-2003, Michae 22 Module #15 – Inductive Proofs Sử... Michae 28 Module #15 – Inductive Proofs Tìm chỗ sai 12/03 /15 (c)2001-2003, Michae 29 Module #15 – Inductive Proofs Sai trong t/h n = 1 12/03 /15 (c)2001-2003, Michae 30 Module #15 – Inductive Proofs Dùng nguyên lý qui nạp 2 và nguyên lý sắp xếp tốt 12/03 /15 (c)2001-2003, Michae 31 Module #15 – Inductive Proofs Bưu phẩm dùng tem 3 xu và 5 xu 12/03 /15 (c)2001-2003, Michae 32 Module #15 – Inductive Proofs... xu và 5 xu 12/03 /15 (c)2001-2003, Michae 33 Module #15 – Inductive Proofs Chứng minh: phân trường hợp 12/03 /15 (c)2001-2003, Michae 34 Module #15 – Inductive Proofs Không có nghiệm nguyên dương G/s có: a0 nhỏ nhất là thành phần nghiệm 12/03 /15 (c)2001-2003, Michae 35 Module #15 – Inductive Proofs a0 chẵn, a0 = 2a1, suy ra a1 nhỏ hơn a0, mâu thuẫn giả thuyết => không có nghiệm 12/03 /15 (c)2001-2003,... 12/03 /15 (c)2001-2003, Michae 13 Module #15 – Inductive Proofs Another 2nd Principle Example • C/m mọi bưu phí bằng hay lớn hơn 12 xu đều có thể dán bằng các con tem 4-xu và 5xu P(n)=“n có thể…” • Base case: 12=3(4), 13=2(4)+1(5), 14=1(4)+2(5), 15= 3(5), so ∀12≤n 15, P(n) • Inductive step: Let n 15, assume ∀12≤k≤n P(k) Note 12≤n−3≤n, so P(n−3), so add a 4-cent stamp to get postage for n+1 12/03 /15 (c)2001-2003,...Module #15 – Inductive Proofs Example cont • Inductive step: Prove ∀n≥1: P(n)→P(n+1) – Let n≥1, assume P(n), and prove P(n+1)  n  (2i − 1) =  ∑ (2i − 1)  + (2(n + 1) − 1) ∑ i =1  i =1  By inductive 2 = n + 2n + 1 hypothesis P(n) n +1 = (n + 1) 2 12/03 /15 (c)2001-2003, Michae 11 Module #15 – Inductive Proofs Another Induction Example • Prove that ∀n>0, n ... 12/03 /15 (c)2001-2003, Michae 27 Module #15 – Inductive Proofs Kết luận 12/03 /15 (c)2001-2003, Michae 28 Module #15 – Inductive Proofs Tìm chỗ sai 12/03 /15 (c)2001-2003, Michae 29 Module #15 –... với n 12/03 /15 (c)2001-2003, Michae 17 Module #15 – Inductive Proofs Dùng nguyên lý qui nạp 12/03 /15 (c)2001-2003, Michae 18 Module #15 – Inductive Proofs Đặt tên mệnh đề qui nạp 12/03 /15 (c)2001-2003,... Michae 19 Module #15 – Inductive Proofs Trường hợp sở 12/03 /15 (c)2001-2003, Michae 20 Module #15 – Inductive Proofs Điều chỉnh lại 12/03 /15 (c)2001-2003, Michae 21 Module #15 – Inductive Proofs