Matematyka.pl

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ść?

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.

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...