Gọi SnSn là số cách thỏa ycđb.
Muốn lên và xuống thang n bậc (n>3n>3) có 3 cách:
- Bước tới bậc n-1 rồi bước 1 bậc để lên n và xuống 1 bậc: 1 cách.
- Bước tới bậc n-2 rồi bước 2 bậc để lên n, sau đó xuống 2 bậc hoặc bước lên tửng bậc, xuống từng bậc hoặc xuống 2 bậc: 3 cách.
- Bước tới bậc n-3 để lên n rồi xuống thang: 9 cách (lấy theo VD cho nhanh).
Ta có hệ thức truy hồi, với n>3n>3:
Sn=Sn−1+Sn−2+Sn−3Sn=Sn−1+Sn−2+Sn−3
Khởi tạo: S1=1,S2=3,S3=9S1=1,S2=3,S3=9
Suy ra: S11=157+289+531=977S11=157+289+531=977 cách.