Có một cầu thang gồm 15 bậc, với bậc 5, 10 và các bậc bị gãy và không được dừng lại. Có bao nhiêu cách để đi hết cầu thang này, nếu mỗi lần được phép

Giải thích các bước giải:

Số cách để lên bậc 1: 1 cách (1)

Số cách để lên bậc 2: 2 cách (1;-1; 2)

Số cách để lên bậc 3: 3 cách (1-1-1; 1-2; 2-1) 

Số cách để lên bậc 4: 5 cách (1-1-1-1; 1-1-2; 1-2-1; 2-1-1; 2-2)

Ta thấy dãy trên chính là dãy phibonaci: 1,2,3,5,8,13,21,34, 55, 89, 144,…

Do bậc 5 bị gãy nên khi lên đến bậc 4 thì phải bước thêm 2 bước liền.

Để đến bậc 6 có 5 cách:

Tiếp túc áp dụng dãy phibonacy:

Số cách để lên bậc 9 : 21 cách 

Để đến bậc 11 có 21 cách 

=> Số cách để lên bậc 14 ( hoặc đi hết câu thang) là: 89 cách 

Vậy có 89 cách để lên cầu thang