Một cầu thang có 10 bậc

Để tính số cách Mary có thể đi lên cầu thang, ta có thể sử dụng phương pháp đệ quy.

Gọi f(n) là số cách Mary có thể đi lên cầu thang có n bậc. Ta có các trường hợp sau:
- Nếu n = 1, tức chỉ có 1 bậc, Mary chỉ có 1 cách để đi lên đó.
- Nếu n = 2, Mary có 2 cách để đi lên cầu thang: bước 1 bậc 2 lần hoặc bước 2 bậc 1 lần.
- Nếu n = 3, Mary có 4 cách để đi lên cầu thang: bước 1 bậc 3 lần, bước 1 bậc 2 lần và 1 bậc 1 lần, bước 2 bậc 1 lần và 1 bậc 2 lần, hoặc bước 3 bậc 1 lần.

Ta có thể thấy rằng f(n) = f(n-1) + f(n-2) + f(n-3), với n > 3.

Áp dụng công thức trên, ta có:
f(1) = 1
f(2) = 2
f(3) = 4
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
f(10) = f(9) + f(8) + f(7) = 149 + 81 + 44 = 274

Vậy có tổng cộng 274 cách Mary có thể đi lên cầu thang.