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ą.
Znajdź wzór jawny na t_n i go udowodnij
- 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
Znajdź wzór jawny na t_n i go udowodnij
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...
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...
-
- 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
Czy wiesz może na czym polegałby dowód takiego znalezionego wzoru?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...