XXXIV OM - I - Zadanie 11

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

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