Bardzo proszę o rozwiązanie któregoś z podanych zadań. W zadaniu 3 odkryłem, że wzór to 2^((2^n)-1), ale nie wiem jak to formalnie wykazać.
Ile różnych n-elementowych ciągów można otrzymać z 0 i 1, jeśli żadne
dwa po sobie następujące 0 nie są, dozwolone. Wyznacz wzór rekuren-
cyjny, a następnie jawny.
Ile jest słów długości n złożonych z liter a; b; c; w których nie ma dwóch
kolejnych a? Znajdź zależność rekurencyjną oraz wzór.
Rozwiąż rekurencję \(\displaystyle{ a_{n+1} = a^{2}_{n}}\)
n gdzie n>=1, z warunkiem \(\displaystyle{ a_{1} = 2.}\)
Ciągi rekurencyjne
-
mateuszek89
- Użytkownik
- Posty: 1106
- Rejestracja: 1 lip 2010, o 15:27
- Płeć: Mężczyzna
- Lokalizacja: toruń
- Pomógł: 153 razy
Ciągi rekurencyjne
jeśli chodzi o zadanie \(\displaystyle{ 3}\) to wzór będzie wyglądał tak \(\displaystyle{ a_n=2^{2^{n-1}}}\). Możesz go wykazać indukcyjnie. pozdrawiam!
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Ciągi rekurencyjne
W trzecim, skoro już masz wzór, to wystarczy go przez indukcję udowodnić, co jest łatwe.
Dopiszę może pierwsze.
Niech:
\(\displaystyle{ a_n}\) oznacza liczbę ciągów n-elementowych spełniających warunki zadania kończących się jedynką
\(\displaystyle{ b_n}\) oznacza liczbę ciągów n-elementowych spełniających warunki zadania kończących się zerem.
Interesuje nas ciąg:
\(\displaystyle{ c_n=a_n+b_n}\).
Mamy:
\(\displaystyle{ a_n=a_{n-1}+b_{n-1}}\) (jedynkę można dopisać na końcu dowolnego ciągu)
\(\displaystyle{ b_{n}=a_{n-1}}\) (zero można dopisać na końcu ciągu kończącego się jedynką)
skąd:
\(\displaystyle{ c_n=a_{n+1}=a_n+b_n=a_n+a_{n-1}=c_{n-1}+c_{n-2}}\).
Oraz \(\displaystyle{ c_0=1, c_1=2}\).
Zauważmy, że \(\displaystyle{ c_n}\) to prawie ciąg Fibonacciego, to znaczy \(\displaystyle{ c_n=F_{n+2}}\), skąd:
\(\displaystyle{ c_n=\frac{\varphi^{n+2}-(-1/\varphi)^{n+2}}{\sqrt 5}}}\)
gdzie \(\displaystyle{ \varphi=\frac{1+\sqrt 5}2}\).
Dopiszę może pierwsze.
Niech:
\(\displaystyle{ a_n}\) oznacza liczbę ciągów n-elementowych spełniających warunki zadania kończących się jedynką
\(\displaystyle{ b_n}\) oznacza liczbę ciągów n-elementowych spełniających warunki zadania kończących się zerem.
Interesuje nas ciąg:
\(\displaystyle{ c_n=a_n+b_n}\).
Mamy:
\(\displaystyle{ a_n=a_{n-1}+b_{n-1}}\) (jedynkę można dopisać na końcu dowolnego ciągu)
\(\displaystyle{ b_{n}=a_{n-1}}\) (zero można dopisać na końcu ciągu kończącego się jedynką)
skąd:
\(\displaystyle{ c_n=a_{n+1}=a_n+b_n=a_n+a_{n-1}=c_{n-1}+c_{n-2}}\).
Oraz \(\displaystyle{ c_0=1, c_1=2}\).
Zauważmy, że \(\displaystyle{ c_n}\) to prawie ciąg Fibonacciego, to znaczy \(\displaystyle{ c_n=F_{n+2}}\), skąd:
\(\displaystyle{ c_n=\frac{\varphi^{n+2}-(-1/\varphi)^{n+2}}{\sqrt 5}}}\)
gdzie \(\displaystyle{ \varphi=\frac{1+\sqrt 5}2}\).
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Ciągi rekurencyjne
Do kompletu szkic drugiego - jeśli przez \(\displaystyle{ S_n}\) oznaczymy ilość ciągów długości \(\displaystyle{ n}\) spełniających żądany warunek, to mamy:
\(\displaystyle{ S_n=2S_{n-1}+2S_{n-2}}\)
"Dobre" ciągi długości \(\displaystyle{ n}\) mogą się bowiem kończyć na \(\displaystyle{ b}\) (tych jest \(\displaystyle{ S_{n-1}}\)), mogą się kończyć na \(\displaystyle{ c}\) (tych też jest \(\displaystyle{ S_{n-1}}\)), mogą się kończyć na \(\displaystyle{ ba}\) (tych jest \(\displaystyle{ S_{n-2}}\)), mogą się też kończyć na \(\displaystyle{ ca}\) (tych też jest \(\displaystyle{ S_{n-2}}\)).
Warunki początkowe łatwo znaleźć, a rekurencję rozwiązuje się standardowo (np. przy użyciu równania charakterystycznego).
Q.
\(\displaystyle{ S_n=2S_{n-1}+2S_{n-2}}\)
"Dobre" ciągi długości \(\displaystyle{ n}\) mogą się bowiem kończyć na \(\displaystyle{ b}\) (tych jest \(\displaystyle{ S_{n-1}}\)), mogą się kończyć na \(\displaystyle{ c}\) (tych też jest \(\displaystyle{ S_{n-1}}\)), mogą się kończyć na \(\displaystyle{ ba}\) (tych jest \(\displaystyle{ S_{n-2}}\)), mogą się też kończyć na \(\displaystyle{ ca}\) (tych też jest \(\displaystyle{ S_{n-2}}\)).
Warunki początkowe łatwo znaleźć, a rekurencję rozwiązuje się standardowo (np. przy użyciu równania charakterystycznego).
Q.