Liczba ciągów
Liczba ciągów
Zliczamy ciągi długości \(\displaystyle{ n}\) złożonych z cyfr \(\displaystyle{ 0,1,2}\) takich, że każdy z nich zawiera parzystą liczbę cyfr \(\displaystyle{ 0}\) i parzystą liczbę cyfr \(\displaystyle{ 1}\). Znaleźć zależność rekurencyjną.
Ostatnio zmieniony 21 lut 2014, o 20:16 przez Qń, łącznie zmieniany 1 raz.
Powód: Wszystkie wyrażenia matematyczne umieszczaj w tagach[latex] [/latex] .
Powód: Wszystkie wyrażenia matematyczne umieszczaj w tagach
-
- Użytkownik
- Posty: 70
- Rejestracja: 1 lip 2012, o 20:02
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 2 razy
- Pomógł: 7 razy
Liczba ciągów
Wzór rekurencyjny \(\displaystyle{ x_n = 3x_{n-1}}\), jeśli n jest parzyste oraz \(\displaystyle{ x_n = 3x_{n-1} - 2}\) gdy nie jest.
Udowodnię zależność dla n parzystych (dla nieparzystych jest podobnie).
Niech a liczba ciągów długości \(\displaystyle{ n-1}\) takich, że wszystkie liczby (0, 1 i 2) występują nieparzystą liczbę razy. Liczba wszystkich ciągów wynosi \(\displaystyle{ 3^{n-1}}\), a zatem
\(\displaystyle{ a + 3x_{n-1}=3^{n-1}}\)
Niech b liczba ciągów długości n takich, że jedna ustalona liczba występuje parzystą liczbę razy, a pozostałe nieparzystą. Wtedy:
\(\displaystyle{ x_n + 3b = 3^n}\)
Zauważmy teraz, że \(\displaystyle{ b = a + 2x_{n-1}}\), zatem \(\displaystyle{ x_n = 3^n - 3b = 3^n - 3a - 6x_{n-1} = 3^n - (3^n - 9x_{n-1}) - 6x_{n-1} = 3x_{n-1}.}\)
Gdyby któraś z użytych równości była niejasna, to pomogę.
Udowodnię zależność dla n parzystych (dla nieparzystych jest podobnie).
Niech a liczba ciągów długości \(\displaystyle{ n-1}\) takich, że wszystkie liczby (0, 1 i 2) występują nieparzystą liczbę razy. Liczba wszystkich ciągów wynosi \(\displaystyle{ 3^{n-1}}\), a zatem
\(\displaystyle{ a + 3x_{n-1}=3^{n-1}}\)
Niech b liczba ciągów długości n takich, że jedna ustalona liczba występuje parzystą liczbę razy, a pozostałe nieparzystą. Wtedy:
\(\displaystyle{ x_n + 3b = 3^n}\)
Zauważmy teraz, że \(\displaystyle{ b = a + 2x_{n-1}}\), zatem \(\displaystyle{ x_n = 3^n - 3b = 3^n - 3a - 6x_{n-1} = 3^n - (3^n - 9x_{n-1}) - 6x_{n-1} = 3x_{n-1}.}\)
Gdyby któraś z użytych równości była niejasna, to pomogę.