Soru, Fibonacci dizisinin genişletilmiş hali. Bu kişi n. basamağa ya (n-1). basamaktan bir basamaklık adımda, ya (n-2). basamaktan iki basamaklık adımda, ya da (n-3). basamaktan 3 basamaklık adımda çıkar. Dolayısıyla
sn=sn-1+sn-2+sn-3 'tür.
1. basamağa s1=1, 2. basamağa s2=2, 3. basamağa s3=4 farklı şekilde çıkar.
s4=1+2+4=7
s5=2+4+7=13 farklı şekilde çıkıp 13 farklı şekilde iner. Dolayısıyla 13*13=169 farklı şekilde çıkıp iner.
Soru: Her adımda en fazla k basamak çıkabilen bir kişi n. basamağa kaç farklı şekilde çıkabilir?
Yanıt
a) n küçük eşit k ise: Bu kişi ilk n basamak içinden istediği her basamağa çıkabilir. Basamaklar kümesini Bn={b1,b2, ... , bn} ile gösterirsek Bn-1 kümesinin herhangi bir alt kümesini seçer, bu alt kümenin elemanlarını indisleri artan sırada olacak şekilde dizer ve oluşan sıraya göre basamakları çıkar.En son da bn'e çıkar. Bu durumda farklı çıkışların sayısı n-1 elemanlı Bn-1 kümesinin tüm alt kümeleri sayısı olan 2n-1 'e eşittir.
b) n > k ise: Bu kişi n. basamağa (n-1). , (n-2). , ... , (n-k). basamaklardan çıkabilir. Bu durumda
sn=sn-1+sn-2+...+sn-k eşitliği oluşur.