Neka je
skup svih podskupova skupa
koji nemaju susednih elemenata.
Svaki element bilo skupa
pripada skupovima
i
. Za svaki skup
napišimo sve skupove
i
takve da je
i
. Ako
, onda je
jedini element skupa
koji u preseku sa skupom
daje skup
, dok u skupu
postoji još jedan takav skup -
. U slučaju kada
onda su elementi skupa
koji u preseku sa skupom
daju skup
zapravo
i
, dok u skupu
postoji još jedan takav skup -
. Dakle, u svakom slučaju u skupu
imamo po jedan takav element više nego u skupu
.
Kada to učinimo za sve elemente skupa
, nabrojali smo sve elemente skupova
i
po jedanput. Međutim, elemenata skupa
ima više od elemenata skupa
i to tačno onoliko koliko ima elemenata skupa
. Dakle,
.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Zaaaaaaaaaaadatak
broj podskupova skupa {1, 2, 3,..., n} koji ne sadrze dva susjedna broja. Naci homogenu linearnu rekurentnu relaciju drugog reda koju zadovoljava niz 
pa zatim odrediti 
.
Registrovani: 8 ( Turmen, Ultrena, rafiki, bakara, Nedeljko, djoka_l, popmilan76, valjan )