[Toán rời rạc/Chương IV] Quy nạp và đệ quy

CHƯƠNG IV: QUY NẠP VÀ ĐỆ QUY

I, Quy tắc quy nạp trong toán học

- Vấn đề: Chứng minh P(n) đúng với mọi n = 1, 2, ...

- Để chứng minh ta thực hiện theo 4 bước:

    B1 (Bước cơ sở): Chứng minh P(1) là đúng 

    B2 (Giả thuyết quy nạp): Giả sử P(k) là đúng với mọi số nguyên dương k

    B3 (Bước quy nạp): Chứng minh P(k+1) là đúng

    B4 (Kết luận): P(n) đúng với mọi số dương n

II, Quy nạp mạnh và Well-Ordering

- Chứng minh tương tự quy nạp nhưng thay vì ta giả sử đúng ở số k thì ta giả sử nó đúng đến số k (ở B2)

- Các bước chi tiết:

    B1: Chứng minh P(1) đúng

    B2: Giả sử P(1), P(2),..., P(k) đúng với mọi k \(\geq\) 1

    B3: Chứng minh nó đúng với P(k+1)

    B4: P(n) đúng với mọi số n dương

* Sử dụng quy nạp mạnh trong tính toán hình học

- Đa giác là 1 hình học khép kín bao gồm 1 chuỗi các đoạn thẳng được gọi là cạnh

- Đường chéo của 1 đa giác đơn là 1 đoạn thẳng nối 2 đỉnh không liên tiếp của đa giác và một đường chéo được gọi là đường chéo trong nếu nó nằm bên trong đa giác, ngoài trừ các điểm cuối của nó 

- Định lý: 1 đa giác đơn có n cạnh, trong đó, n là số nguyên có n \(\geq\) 3 thì có thể có n - 2 tam giác

- Bổ đề: Mọi đa giác đơn có ít nhất bốn cạnh đều có 1 đường chéo trong

* Well-Ordering

- Bất kì tập hợp số nguyên không âm nào không rỗng đều có phần tử nhỏ nhất

III, Định nghĩa đệ quy

- Ta sử dụng 2 bước để định nghĩa 1 hàm với tập hợp các số nguyên không âm trong miền của nó:

    1. Bước cơ bản (basis step): Chọn các giá trị của hàm ban đầu

    2. Bước đệ quy (recursive step): Đưa ra quy tắc để tìm giá trị của hàm tại 1 số nguyên từ các giá trị của nó tại các số nguyên nhỏ hơn

Ví dụ: Cho tập S

    1. Basic step: 3 \(\in\) S

    2. Recursive step: Nếu x, y \(\in\) S thì x + y \(\in\) S

Ta có: Phần tử ban đầu là 3, ta chọn x và y là 3  

Lần 1 dùng bước đệ quy ta thu được 3 + 3 = 6 

Lần 2 dùng bước đệ quy ta thu được 3 + 6 = 6 + 3 = 9 và 6 + 6 = 12

...

Ta chứng minh được tập S là tập các bội số dương của 3

Tương tự với các đệ quy khác, ví dụ như chuỗi (string) thì ta nối vào,...

IV, Thuật toán đệ quy

- 1 thuật toán được gọi là đệ quy nếu nó giải quyết 1 vấn đề bằng cách rút gọn nó thành 1 trường hợp của cùng 1 vấn đề với input nhỏ hơn 

Ví dụ 1: Thuật toán đệ quy tìm n giai thừa (n!)

Ví dụ 2: Thuật toán tìm lũy thừa của 1 số \(a^n\)

P/s: Bài tập và tài liệu nghiên cứu thêm (nếu cần) được tổng hợp ở link dưới sau:

https://drive.google.com/drive/folders/14RWCpJ7g3vUs6OByT6ZqZjlKodl9FvxV?usp=sharing