1 cầu thang có 9 bậc. Mỗi lần đi, Chelsea có thể bước lên 1 hoặc 2 bậc và 3 bậc. Hỏi cô bé có bao nhiêu cách để đi hết cầu thang?

Để giải quyết bài toán này, chúng ta sẽ áp dụng phương pháp quy nạp để tìm số cách đi lên cầu thang có 9 bậc. Chúng ta sẽ bắt đầu từ các trường hợp cơ bản và mở rộng dần dần. Gọi \( f(n) \) là số cách để đi lên cầu thang có \( n \) bậc. - Với \( n = 1 \): Chelsea chỉ có thể bước lên 1 bậc duy nhất. Do đó, \( f(1) = 1 \). - Với \( n = 2 \): Chelsea có thể bước lên 2 bậc một lần hoặc bước lên 1 bậc hai lần. Do đó, \( f(2) = 2 \). - Với \( n = 3 \): Chelsea có thể bước lên 3 bậc một lần, hoặc bước lên 2 bậc rồi 1 bậc, hoặc bước lên 1 bậc rồi 2 bậc, hoặc bước lên 1 bậc ba lần. Do đó, \( f(3) = 4 \). Bây giờ, chúng ta sẽ áp dụng quy luật quy nạp để tính \( f(n) \): \[ f(n) = f(n-1) + f(n-2) + f(n-3) \] Áp dụng công thức trên để tính các giá trị tiếp theo: - \( f(4) = f(3) + f(2) + f(1) = 4 + 2 + 1 = 7 \) - \( f(5) = f(4) + f(3) + f(2) = 7 + 4 + 2 = 13 \) - \( f(6) = f(5) + f(4) + f(3) = 13 + 7 + 4 = 24 \) - \( f(7) = f(6) + f(5) + f(4) = 24 + 13 + 7 = 44 \) - \( f(8) = f(7) + f(6) + f(5) = 44 + 24 + 13 = 81 \) - \( f(9) = f(8) + f(7) + f(6) = 81 + 44 + 24 = 149 \) Vậy, Chelsea có 149 cách để đi hết cầu thang có 9 bậc.