Układanie rekurencji zadania

[szym99on]

Zadanie 1. Znajdź zależność rekurencyjną na \(a_n\) - liczbę podzbiorów zbioru {1, 2, . . . , n} (wliczając zbiór pusty),
które nie zawierają dwóch kolejnych liczb.
Zadanie 2. Wiadomo, że co roku pewien pracownik otrzymuje podwyżkę pensji, która wynosi 20% kwoty pensji
wypłacanej przez ostatni rok pomniejszone o 11% kwoty pensji wypłacanej rok wcześniej. Na początku pracownik zarabia
1 tysiąc złotych. Wyznacz wzór rekurencyjny na \(a_n\) - wysokość pensji po \(n\) latach.
Zadanie 3. Franek pożyczył od chłopaków z miasta 1 mln złotych na 50% rocznie (odsetki są naliczane na koniec
każdego roku). Na koniec każdego roku spłaca 0,2 mln. złotych. Ile będzie wynosić jego dług po n latach?
Zadanie 4. Na ile sposobów można wciągnąć na n-metrowy maszt \((n \ge 1)\) flagi, jeżli mamy do dyspozycji nieograniczoną liczbę:
a) nierozróżnialnych flag w kolorze czerwonym o szerokości 2 metry, nierozróżnialnych flag w kolorze zielonym o szerokości 1 metra i nierozróżnialnych flag w kolorze niebieskim o szerokości 1 metra;
b) flag w kolorze białym i czarnym o szerokości 1 metra ( flag w tym samym kolorze s¡ nierozróżnialne), ale żadne dwie białe flagi nie mogą ze sobą sąsiadować na maszcie.
Proszę podać rozwiązanie w postaci rekurencyjnej i nie rozwiązywać rekurencji. UWAGA: Ważna jest dla nas kolejność flag na maszcie i ich szerokość, np. w (a) dla n = 4 przykładowo można powiesi¢ najpierw jedną czerwoną flagę a po niej dwie zielone i zapełnimy cały maszt.
Odpowiedzi:
1) \( \begin{cases} a_1 = 2;\\
a_2 = 3;\\
a_n = a_{n−1} + a_{n−2}, n \ge ­ 3\end{cases} \)
2)\( \begin{cases} a_0 = 1;\\
a_1 = 1,2;\\
a_n = 1,2 · a_{n−1} − 0,11 · an−2, n \ge ­ 2.\end{cases} \)
3) \( \begin{cases}a_0 = 1;\\
a_n = 1,5 · a_{n−1} − 0,2, n \ge 1; \end{cases} \\
a_n = 0,6 · (1,5)^n + 0,4.\)
4 a)\( \begin{cases}a_1 = 2;\\
a_2 = 5;\\
a_n = 2 · a_{n−1} + a_{n−2}, n \ge ­3. \end{cases} \)
b)\( \begin{cases}a_1 = 2;\\
a_2 = 3;\\
a_n = a_{n−1} + a_{n−2}, n \ge ­ 3. \end{cases} \)

[szym99on]

Poprawka odpowiedzi:
2)\( \begin{cases} a_0 = 1;\\
a_1 = 1,2;\\
a_n = 1,2 · a_{n−1} − 0,11 · a_{n−2}, n \ge ­ 2.\end{cases} \)