Znajdź wzór jawny na t_n i go udowodnij

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
ly000
Użytkownik
Użytkownik
Posty: 33
Rejestracja: 10 lis 2012, o 00:09
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 17 razy

Znajdź wzór jawny na t_n i go udowodnij

Post autor: ly000 »

Niech \(\displaystyle{ \Sigma = \{a, b, c\}}\). Niech \(\displaystyle{ t_n}\) oznacza liczbę słów długości \(\displaystyle{ n}\) nad alfabetem \(\displaystyle{ \Sigma}\), w których jest parzysta liczba liter \(\displaystyle{ a}\). (a) Oblicz pięć pierwszych wyrazów ciągu \(\displaystyle{ t_n}\). (b) znajdź wzór jawny na \(\displaystyle{ t_n}\) i go udowodnij.

Prawdopodobnie należy wykorzystać rekurencję i indukcję matematyczną.
Awatar użytkownika
Premislav
Użytkownik
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

Znajdź wzór jawny na t_n i go udowodnij

Post autor: Premislav »

b) Jak rozumiem, intencją układającego zadanie jest skłonić Cię do napisania równania rekurencyjnego, które np. zliczałoby, jak ma się \(\displaystyle{ t_{n+1}}\) w stosunku do \(\displaystyle{ t_n}\) i \(\displaystyle{ t_{n-1}.}\) (jak je zauważyć - patrz polecenie a)).
Mnie się nie podoba takie podejście, bo trzeba brać pod uwagę taką głupią sytuację, że np. doklejamy dwa \(\displaystyle{ a}\) na początku słowa o dwa znaki krótszego.
Wymyśliłem coś takiego: niech \(\displaystyle{ t_n}\) oznacza liczbę słów n-literowych nad wspomnianym alfabetem \(\displaystyle{ \Sigma}\), w których występuje parzyście wiele \(\displaystyle{ a}\), zaś
\(\displaystyle{ w_n}\) oznacza liczbę słów n-literowych nad alfabetem \(\displaystyle{ \Sigma}\), w których występuje nieparzyście wiele \(\displaystyle{ a}\).
Wówczas mamy
\(\displaystyle{ t_n= \sum_{k=0}^{\left[ \frac n 2\right] }{n \choose 2k}2^{n-2k}}\)
oraz
\(\displaystyle{ w_n= \sum_{k=0}^{\left[ \frac{n-1}{2} \right] } {n \choose 2k+1}2^{n-2k-1}}\)
Zatem
\(\displaystyle{ t_{n+1}= \sum_{k=0}^{\left[ \frac {n+1} 2\right] }{n+1 \choose 2k}2^{n+1-2k}=2^{n+1}+\sum_{k=1}^{\left[ \frac {n+1} 2\right] }{n+1 \choose 2k}2^{n+1-2k}}\)
Teraz korzystamy z tego, że \(\displaystyle{ {n+1 \choose 2k}={n \choose 2k}+{n \choose 2k-1}}\):
\(\displaystyle{ t_{n+1}=2^{n+1}+ \sum_{k=1}^{\left[ \frac{n+1}{2} \right] }{n \choose 2k}2^{n+1-2k}+ \sum_{k=1}^{\left[ \frac{n+1}{2} \right] }{n \choose 2k-1}2^{n+1-2k}=\\=\sum_{k=0}^{\left[ \frac{n+1}{2} \right] }{n \choose 2k}2^{n+1-2k}+ \sum_{k=0}^{\left[ \frac{n+1}{2} \right]-1 }{n \choose 2k+1}2^{n-1-2k}}\)
Jeżeli \(\displaystyle{ n}\) jest parzyste, to \(\displaystyle{ \left[ \frac{n+1}{2} \right]=\left[ \frac{n}{2} \right]}\) oraz \(\displaystyle{ \left[ \frac{n+1}{2} \right]-1=\left[ \frac{n-1}{2} \right]}\)
czyli otrzymaliśmy \(\displaystyle{ t_{n+1}=2t_n+w_n}\).
Analogicznie dostajemy w przypadku \(\displaystyle{ n}\) nieparzystego, gdyż
\(\displaystyle{ {n \choose k}=0}\) gdy \(\displaystyle{ n,k \in \NN, k>n}\).
Czyli mamy:
\(\displaystyle{ \begin{cases}t_{n+1}=2t_n+w_n \\ t_n+w_n=3^n \end{cases}}\)
a stąd:
\(\displaystyle{ t_{n+1}=t_n+3^n}\)
czyli \(\displaystyle{ t_{n+1}-t_n=3^n}\)
Stąd dla \(\displaystyle{ n \ge 2}\) mamy
\(\displaystyle{ t_n=(t_n-t_{n-1})+\dots+(t_2-t_1)+t_1=2+ \sum_{k=1}^{n-1}3^k=\\=2+ \frac{3^n-3}{2}}\)
(suma wyrazów ciągu geometrycznego)
Pewnie można do tego łatwiej dojść, ale ja mam bardzo duży problem z rozumowaniami typowo kombinatorycznymi, tj. że jakaś symetria występuje, tu się coś powtórzy itd.-- 18 kwi 2017, o 02:00 --Chociaż teraz jak tak patrzę, to pewnie chodziło o to, żeby rozpisać dla pierwszych pięciu \(\displaystyle{ n}\), a potem zauważyć wzór i udowodnić go indukcyjnie. Coś takiego też mi się niezbyt podoba...
ly000
Użytkownik
Użytkownik
Posty: 33
Rejestracja: 10 lis 2012, o 00:09
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 17 razy

Znajdź wzór jawny na t_n i go udowodnij

Post autor: ly000 »

Premislav pisze: -- 18 kwi 2017, o 02:00 --

Chociaż teraz jak tak patrzę, to pewnie chodziło o to, żeby rozpisać dla pierwszych pięciu \(\displaystyle{ n}\), a potem zauważyć wzór i udowodnić go indukcyjnie. Coś takiego też mi się niezbyt podoba...
Czy wiesz może na czym polegałby dowód takiego znalezionego wzoru?
ODPOWIEDZ