aa Hugo: Ile podzbiorów zbioru [n] = {1, 2, ..., n}, wliczając zbiór pusty, nie zawiera sąsiednich liczb? jak to rozwiazać?

Vax: Niech a_n oznacza ilość takich podzbiorów zbioru {1, 2, ..., n} o których mowa w zadaniu. Wtedy a₁ = 2, a₂ = 3. Popatrzmy ile wynosi a_n. Mamy dwa przypadki, albo bierzemy n'ty element albo go nie bierzemy, w pierwszym przypadku mamy a_n−2 możliwości (bo n−1 elementu nie możemy już wziąć i bierzemy wszystkie ,,dobre" podzbiory {1,2,...,n−2}), a w drugim po prostu a_n−1. Stąd a_n = a_n−1+a_n−2, a to już się nam kojarzy z ciągiem fibonacciego, tylko skoro a₁ = 2, a₂ = 3 to przesuniętym o 2, tj a_n = F_n+2.

Hugo: Dziekuje