Hej mam zadanie przy którym potrzebuję pomocy.
Niech \(\displaystyle{ b_{n}}\) oznacza ilość ciągów długości \(\displaystyle{ n}\) utworzonych z liczb \(\displaystyle{ 0}\),\(\displaystyle{ 1}\) i \(\displaystyle{ 2}\), w których występuje
nieparzysta liczba zer. Uzasadnij, że ciąg \(\displaystyle{ b_{n}}\) spełnia następującą rekurencję: \(\displaystyle{ b_{1} = 1}\), \(\displaystyle{ b_{n+1} =
b_{n} + 3^{n}}\)
Z góry dziękuję za pomoc.
(Najpierw było tu parę zadań stąd tytuł posta ale znalazłem rozwiązania na forum)
Parę zadań
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Parę zadań
To, że \(\displaystyle{ b_1=1}\) jest oczywiste (w ciągu długości \(\displaystyle{ 1}\) musi być dokładnie jedno zero, by spełniał on warunki zadania).
Mamy \(\displaystyle{ 3^n}\) ciągów długości \(\displaystyle{ n}\) o wyrazach ze zbioru \(\displaystyle{ \left\{ 0,1,2\right\}}\), wśród nich jest \(\displaystyle{ b_n}\) ciągów, w których nieparzyście wiele razy występuje zero i \(\displaystyle{ 3^n-b_n}\) ciągów, w których parzyście wiele razy występuje zero.
Do tych, w których parzyście wiele razy występowała zero, dopisujemy na \(\displaystyle{ n+1}\). pozycji \(\displaystyle{ 0}\), uzyskując w ten sposób \(\displaystyle{ (3^n-b_n)\cdot 1=3^n-b_n}\) ciągów długości \(\displaystyle{ n+1}\) o nieparzyście wielu wystąpieniach zera,
natomiast do tych, w których nieparzyście wiele razy występowało zero, dopisujemy na \(\displaystyle{ n+1}\). pozycji jedną z dwóch liczb - \(\displaystyle{ 1}\) bądź \(\displaystyle{ 2}\)
Łącznie uzyskujemy więc \(\displaystyle{ 3^n-b_n+2\cdot b_n=3^n+b_n}\) ciągów długości \(\displaystyle{ n+1}\) o nieparzyście wielu zerach, tj. rzeczywiście \(\displaystyle{ b_{n+1}=b_n+3^n}\)
Mamy \(\displaystyle{ 3^n}\) ciągów długości \(\displaystyle{ n}\) o wyrazach ze zbioru \(\displaystyle{ \left\{ 0,1,2\right\}}\), wśród nich jest \(\displaystyle{ b_n}\) ciągów, w których nieparzyście wiele razy występuje zero i \(\displaystyle{ 3^n-b_n}\) ciągów, w których parzyście wiele razy występuje zero.
Do tych, w których parzyście wiele razy występowała zero, dopisujemy na \(\displaystyle{ n+1}\). pozycji \(\displaystyle{ 0}\), uzyskując w ten sposób \(\displaystyle{ (3^n-b_n)\cdot 1=3^n-b_n}\) ciągów długości \(\displaystyle{ n+1}\) o nieparzyście wielu wystąpieniach zera,
natomiast do tych, w których nieparzyście wiele razy występowało zero, dopisujemy na \(\displaystyle{ n+1}\). pozycji jedną z dwóch liczb - \(\displaystyle{ 1}\) bądź \(\displaystyle{ 2}\)
Łącznie uzyskujemy więc \(\displaystyle{ 3^n-b_n+2\cdot b_n=3^n+b_n}\) ciągów długości \(\displaystyle{ n+1}\) o nieparzyście wielu zerach, tj. rzeczywiście \(\displaystyle{ b_{n+1}=b_n+3^n}\)