Her n pozitif tam sayisi icin {1,⋯,n}
kumesinin ardasik eleman icermeyen alt kumeleri sayisina
an diyelim.
Bu durumda
a1=2 ve a2=3
olur.
______________________
n≥2 olsun.
Bu kumenin bir alt kumesi ya
n'yi eleman olarak icerir ya da icermez.
(Durum 1) Diyelim ki icermiyor. O zaman soru su olur:
{1,⋯,n−1}
kumesinin ardasik eleman icermeyen alt kumeleri sayisi kac olur. Bu da
an−1 dedigimiz.
(Durum 2) Diyelim ki
n'yi iceriyor. Bu durumda
n−1 elemanini iceremez. Bu durumda da
{n} ile
{1,⋯,n−2}
kumesinin ardasik eleman icermeyen alt kumelerini birlestirmis oluruz. Bu sayi da
an−2 olur.
Dolayisi ile a1=2, a2=3 ve n≥2 icin an=an−1+an−2
olmasi gerektigini elde ederiz. (Fibonacci dizisinin otelenmis hali. Hatta
a0=1 olarak da gorebiliriz).
Sorunun cevabi da
2,3,5,8,13,21,34,55
olur.