Hãy chứng minh công thức H(n) = 2^n-1  bằng quy nạp toán học. Hãy tính H(64) và so sánh

- Nếu chỉ có một đĩa (n=1), H(n) = 1.

- Nếu có n đĩa, để chuyển tất cả các đĩa từ tháp ban đầu sang tháp đích, ta phải thực hiện các bước sau:

Chuyển n-1 đĩa từ tháp ban đầu sang tháp trung gian.

Chuyển đĩa cuối cùng (đĩa lớn nhất) từ tháp ban đầu sang tháp đích.

Chuyển n-1 đĩa từ tháp trung gian sang tháp đích.

Số bước chuyển tất cả các đĩa là H(n) = 2 * H(n-1) + 1.

- Ta sẽ chứng minh công thức này bằng phương pháp quy nạp toán học:

Bước 1: Giả sử công thức đúng với n-1, tức là H(n-1) = 2^(n-1) - 1

Bước 2: Chứng minh công thức đúng với n, tức là H(n) = 2^n - 1

Ta có:

H(n) = 2 * H(n-1) + 1 (theo công thức đề bài)

= 2 * (2^(n-1) - 1) + 1 (theo giả sử ở bước 1)

= 2^n - 2 + 1

= 2^n - 1

Vậy ta đã chứng minh được công thức đúng với mọi n.

Để tính H(64), ta áp dụng công thức đã chứng minh:

H(64) = 2^64 - 1

= 18446744073709551615

Vậy H(64) = 18446744073709551615 trùng với con số ở trên bài báo