XXXIV OM - I - Zadanie 11

Wyznaczyć liczbę takich podzbiorów zbioru $ \{1, 2, \ldots, n\} $ które nie zawierają dwóch kolejnych liczb.

Rozwiązanie

Dla $ n= 1 $ są dwa takie podzbiory $ \emptyset $, $ \{1\} $, dla $ n = 2 $ jest ich trzy: $ \emptyset $, $ \{1\} $, $ \{2\} $. Przypuśćmy, że $ n > 2 $. Każdy podzbiór zbioru $ \{1, 2,\ldots, n+1\} $ nie zawierający dwóch kolejnych liczb, do którego nie należy liczba $ n+1 $ jest podzbiorem żądanej postaci zbioru $ \{1,2,\ldots, n\} $. Każdy podzbiór zbioru $ \{1, 2,\ldots, n+1\} $ nie zawierający dwóch kolejnych liczb, do którego należy liczba $ n+1 $ jest podzbiorem postaci $ \{k_1, k_2,\ldots, k_m, n+1\} $, przy czym liczby $ k_1, k_2, \ldots, k_m $ są mniejsze od $ n $ i nie ma wśród nich dwóch liczb kolejnych. Jeśli więc $ a_n $ jest liczbą omawianych podzbiorów zbioru $ \{1, 2,\ldots, n\} $, to dla $ n > 1 $ jest

\[<br /> a_{n+1} = a_n + a_{n-1}.<br /> \]

Ciąg $ (a_n) $ spełnia poniższe warunki:

\[<br /> a_1 = 2,\ a_2 = 3,\ a_n = a_{n-1}+a_{n-2} \ \textrm{dla} \ n>2.<br /> \]

Jest to ciąg Fibonacciego. Jak wiadomo (łatwo to zresztą sprawdzić przez indukcję), wyrazy tego ciągu można zadać jawnym wzorem

\[<br /> a_n = \frac{(1+\sqrt{5})^{n+2} - (1-\sqrt{5})^{n+1}}{2^{n+2} \sqrt{5}}.<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź