Ly gửi ạ:33

Do 1 lần chỉ được bước 1 hoặc 2 bước nên để bước lên bậc thứ 6 ta phải bước đến bậc thứ 4. Tương tự với các bậc còn lại. 

Ta sẽ tính số cách bước từ bậc 1 đến bậc 4, số cách bước từ bậc 6 đến bậc 9, từ bậc 11 đến bậc 14.

Từ bậc 1 đến bậc 4 có 5 cách đi: 1 - 1 - 1 - 1, 2 - 1 - 1, 1 - 2 - 1, 1 - 1 - 2, 2 - 2. 

Từ bậc 6 đến 9 có 3 cách đi: 1 - 1 - 1, 1 - 2, 2 - 1. 

Từ 11 đến 14 có 3 cách đi: 1 - 1 - 1, 1 - 2, 2 - 1. 

Tổng cộng có: 5x3x3 = 45 cách.

- 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 vị 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 phibonaci:

- 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 để đi hết cầu thang