Weźmy sobie wyrazy zbudowane z liter X,Y,Z,T. Przez \(\displaystyle{ a_n}\) zdefiniujmy liczbę wyrazów długości \(\displaystyle{ n}\) w których X występuję parzystą liczbę razy. Znaleźć rekurencje.
Mam dwa problemy. Gdy rozpiszemy sobie dla kilku wartości \(\displaystyle{ n}\) zauważymy, że \(\displaystyle{ a_{n+1}=3a_n+...}\). Pierwsza trudność pojawia się dla \(\displaystyle{ n}\) parzystego, gdyż wtedy musimy dodać jedną możliwość. Drugi problem jest taki,iż należałoby dołączyć do tego liczbę możliwości ustawień \(\displaystyle{ X}\).
Może inaczej do tego podejść?
Znajdź rekurencję.
- Premislav
- Użytkownik
- Posty: 15685
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 195 razy
- Pomógł: 5219 razy
Re: Znajdź rekurencję.
Ja proponuję coś takiego (wiem, że to toporne, ale po prostu nie jestem za bystry, więc też i moje pomysły zazwyczaj nie należą do błyskotliwych):
niech \(\displaystyle{ a_n}\) oznacza liczbę wyrazów długości \(\displaystyle{ n}\), w których \(\displaystyle{ X}\) występuje nieparzyście wiele razy i niech \(\displaystyle{ b_n}\) oznacza liczbę wyrazów długości \(\displaystyle{ n}\), w których \(\displaystyle{ X}\) występuje nieparzyście wiele razy. Zauważmy, że wówczas oczywiście jest \(\displaystyle{ a_n+b_n=4^n}\).
Ponadto odnotujmy, że \(\displaystyle{ a_{n+1}=b_n+3a_n}\), a oto dlaczego:
zastanawiamy się, co możemy dopisać do ciągu długości \(\displaystyle{ n}\), by uzyskać ciąg długości \(\displaystyle{ n+1}\), w którym parzyście wiele razy występuje \(\displaystyle{ X}\). Jeśli w naszym ciągu długości \(\displaystyle{ n}\) było nieparzyście wiele iksów, to tylko na jeden sposób dostaniemy ciąg długości \(\displaystyle{ n+1}\) o parzystej liczbie iksów, dopisując na końcu \(\displaystyle{ n+1}\). znak: mianowicie dopisujemy \(\displaystyle{ X}\) i \(\displaystyle{ \text{coś nieparzystego}+1=\text{coś parzystego}}\). Natomiast jeśli ciąg długości \(\displaystyle{ n}\) miał parzyście wiele iksów, to na \(\displaystyle{ n+1}\). pozycji dopisujemy jeden z trzech znaków: \(\displaystyle{ Y, Z, T}\).
Podstawiając \(\displaystyle{ b_n=4^n-a_n}\), dostajemy:
\(\displaystyle{ a_{n+1}=2a_n+4^n}\)
i są metody na rozwiązywanie takich rzeczy, sobie bez problemu znajdziesz. Nie jest to też trudne, ja pomyślałem o zapisaniu czegoś takiego:
\(\displaystyle{ a_2=(a_2-2a_1)+2a_1\\ a_3=(a_3-2a_2)+2(a_2-2a_1)+4a_1\\a_4=(a_4-2a_3)+2(a_3-2a_2)+4(a_2-2a_1)+8a_1\\ \ldots \\a_n=2^{n-1}a_1+ \sum_{k=1}^{n-1} 2^{n-k-1}(a_{k+1}-2a_k)=\ldots}\)
Rzecz jasna \(\displaystyle{ a_1=3}\), a dalej masz sumę częściową ciągu geometrycznego.
niech \(\displaystyle{ a_n}\) oznacza liczbę wyrazów długości \(\displaystyle{ n}\), w których \(\displaystyle{ X}\) występuje nieparzyście wiele razy i niech \(\displaystyle{ b_n}\) oznacza liczbę wyrazów długości \(\displaystyle{ n}\), w których \(\displaystyle{ X}\) występuje nieparzyście wiele razy. Zauważmy, że wówczas oczywiście jest \(\displaystyle{ a_n+b_n=4^n}\).
Ponadto odnotujmy, że \(\displaystyle{ a_{n+1}=b_n+3a_n}\), a oto dlaczego:
zastanawiamy się, co możemy dopisać do ciągu długości \(\displaystyle{ n}\), by uzyskać ciąg długości \(\displaystyle{ n+1}\), w którym parzyście wiele razy występuje \(\displaystyle{ X}\). Jeśli w naszym ciągu długości \(\displaystyle{ n}\) było nieparzyście wiele iksów, to tylko na jeden sposób dostaniemy ciąg długości \(\displaystyle{ n+1}\) o parzystej liczbie iksów, dopisując na końcu \(\displaystyle{ n+1}\). znak: mianowicie dopisujemy \(\displaystyle{ X}\) i \(\displaystyle{ \text{coś nieparzystego}+1=\text{coś parzystego}}\). Natomiast jeśli ciąg długości \(\displaystyle{ n}\) miał parzyście wiele iksów, to na \(\displaystyle{ n+1}\). pozycji dopisujemy jeden z trzech znaków: \(\displaystyle{ Y, Z, T}\).
Podstawiając \(\displaystyle{ b_n=4^n-a_n}\), dostajemy:
\(\displaystyle{ a_{n+1}=2a_n+4^n}\)
i są metody na rozwiązywanie takich rzeczy, sobie bez problemu znajdziesz. Nie jest to też trudne, ja pomyślałem o zapisaniu czegoś takiego:
\(\displaystyle{ a_2=(a_2-2a_1)+2a_1\\ a_3=(a_3-2a_2)+2(a_2-2a_1)+4a_1\\a_4=(a_4-2a_3)+2(a_3-2a_2)+4(a_2-2a_1)+8a_1\\ \ldots \\a_n=2^{n-1}a_1+ \sum_{k=1}^{n-1} 2^{n-k-1}(a_{k+1}-2a_k)=\ldots}\)
Rzecz jasna \(\displaystyle{ a_1=3}\), a dalej masz sumę częściową ciągu geometrycznego.
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Znajdź rekurencję.
W skrócie, najpierw wybieramy parzysta liczbę miejsc w których umieszczamy iXy....
A do pozostałych wykonujemy wariację do literek Y, Z, T...
Wzór:
\(\displaystyle{ a_{n}= \sum_{i=0}^{ \left[ \frac{n}{2}\right] } {n \choose 2i}3^{n-2i}}\)
Jakbyś chciał z tego zrobić rekurencję musiałbyś napisać analogiczny wzorek na ilość ixów nieparzystych w tym ciągu...
A do pozostałych wykonujemy wariację do literek Y, Z, T...
Wzór:
\(\displaystyle{ a_{n}= \sum_{i=0}^{ \left[ \frac{n}{2}\right] } {n \choose 2i}3^{n-2i}}\)
Jakbyś chciał z tego zrobić rekurencję musiałbyś napisać analogiczny wzorek na ilość ixów nieparzystych w tym ciągu...