A=(1,2,3,4,5,6,7,8,9,10,11) kümesinin içinde ardışık sayı bulundurmayan alt kümelerinin sayısı ile fibonacci serisi arasında nasıl bir bağlantı vardır?
A=(1,2,3,4,5,6,7,8,9,10,11) kümesinin içinde ardışık sayı bulundurmayan alt kümelerinin sayısı ile fibonacci serisi arasında nasıl bir bağlantı vardır?
Bazı n değerleri için ardısık iki eleman bulundurmayan alt kümelerin sayısını
bulalım:
n = 0 ise S = ∅ olduğundan ardısık iki eleman içermeyen 1 tane alt
küme vardır (∅).
n = 1 ise ardısık iki eleman bulundurmayan alt kümeler 2 tanedir (∅ ve
{1}).
n = 2 ise ardısık iki eleman bulundurmayan alt kümeler 3 tanedir (∅,
{1} ve {2}).
n = 3 ise ardısık iki eleman bulundurmayan alt küme sayısı 5 olur (∅,
{1}, {2}, {3}, {1, 3}).
n = 4 ise ardısık iki eleman bulundurmayan alt küme sayısı 8 olur (∅,
{1}, {2}, {3}, {4}, {1, 3}, {1, 4}, {2, 4}).
Elde edilen sayılar Fibonacci sayılarıdır.
S = {1, 2, . . . , n} kümesinin ardısık iki eleman içermeyen alt kümelerinin
sayısını An olsun. Kolay anlasılabilir olması için önce n = 4 iken
S = {1, 2, 3, 4} kümesinin ardısık iki eleman bulundurmayan alt kümelerinin
sayısını yani A4 ü hesaplayalım. Bu alt kümeleri asağıdaki gibi iki gruba
ayırabiliriz:
“4” ü bulunduran ve ardısık eleman
içermeyen alt kümeler {4}, {1,4}, {2, 4}
“4” kümelere ait olduğundan “3” ait olmamalı.
Bu durumda {1, 2} kümesinin
ardısık iki sayı içermeyen her bir alt kümesine
“4” ü ekliyoruz. Bunların sayısı
ise varsayımımızdan A2 olur.
“4” ü bulundurmayan ve ardısık eleman
içermeyen alt kümeler ∅, {1}, {2} , {3}, {1, 3}
Bu kümeler {1, 2, 3} kümesinin ardısık
iki eleman içermeyen alt kümeleri olur.
Bunların sayısı da varsayımımız gereği
A3 olur.
Böylece
A4 = A2 + A3
olur.
Yukarıda “4” yerine n alıp, diğer sayıları da n − 1 ve n − 2 ile değistirirsek,
An = An−1 + An−2
olur.
A0 = 1 ve A1 = 2 olduğundan An = Fn+2 olur.
yani F13
Foruma üye olmana gerek yok! Facebook hesabınla yorumlarını bekliyoruz!