zad1
Nie korzystając z metod funkcji tworzących, wyznacz rozwiązania szczególne następujących
równań rekurecnyjnych:
\(\displaystyle{ a _{0}= 0, a _{n}= 2 _{a _{n−1} } + 5n}\)
zad2
Ile jest ciągów długości n o wyrazach A, C, G, T, w których A występuje parzystą ilość razy?
równania rekurencyjne
- 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
równania rekurencyjne
W zadaniu drugim dla \(\displaystyle{ n=1}\) może być:
\(\displaystyle{ C,G,T}\) trzy możliwości,
dla \(\displaystyle{ n=2}\)
\(\displaystyle{ AA,CG, GC, CT,TC,GT,TG,CC,GG,TT}\) - 10 możliwości, itd...
dla \(\displaystyle{ n=3}\)
\(\displaystyle{ A-0}\) możliwości: \(\displaystyle{ 3^3}\)
\(\displaystyle{ A-2}\) możliwości: \(\displaystyle{ {3 \choose 2} \cdot 3}\)
dla \(\displaystyle{ n=4}\)
\(\displaystyle{ A-0}\) możliwości: \(\displaystyle{ 3^4}\)
\(\displaystyle{ A-2}\) możliwości: \(\displaystyle{ {4 \choose 2} \cdot 3^2}\)
\(\displaystyle{ A-4}\) możliwości: \(\displaystyle{ {4 \choose 4} \cdot 3^0}\)
dla \(\displaystyle{ n=5}\)
\(\displaystyle{ A-0}\) możliwości: \(\displaystyle{ 3^5}\)
\(\displaystyle{ A-2}\) możliwości: \(\displaystyle{ {5 \choose 2} \cdot 3^3}\)
\(\displaystyle{ A-4}\) możliwości: \(\displaystyle{ {5 \choose 4} \cdot 3^1}\)
Widać jak to idzie teraz dla dowolnego \(\displaystyle{ n}\)
\(\displaystyle{ a_{2n}=3^{2n}+ {2n \choose 2}3^{2n-2}+ {2n \choose 4}3^{2n-4}+...+{2n \choose 2n-2}3^{2}+1}\)
\(\displaystyle{ a_{2n+1}=3^{2n+1}+ {2n+1 \choose 2}3^{2n-1}+ {2n+1 \choose 4}3^{2n-3}+...+{2n+1 \choose 2n-2}3^{1}}\)
Końcówka inna dla parzystych inne dla nieparzystych...
Pierwsze zadanie nieczytelne!
\(\displaystyle{ C,G,T}\) trzy możliwości,
dla \(\displaystyle{ n=2}\)
\(\displaystyle{ AA,CG, GC, CT,TC,GT,TG,CC,GG,TT}\) - 10 możliwości, itd...
dla \(\displaystyle{ n=3}\)
\(\displaystyle{ A-0}\) możliwości: \(\displaystyle{ 3^3}\)
\(\displaystyle{ A-2}\) możliwości: \(\displaystyle{ {3 \choose 2} \cdot 3}\)
dla \(\displaystyle{ n=4}\)
\(\displaystyle{ A-0}\) możliwości: \(\displaystyle{ 3^4}\)
\(\displaystyle{ A-2}\) możliwości: \(\displaystyle{ {4 \choose 2} \cdot 3^2}\)
\(\displaystyle{ A-4}\) możliwości: \(\displaystyle{ {4 \choose 4} \cdot 3^0}\)
dla \(\displaystyle{ n=5}\)
\(\displaystyle{ A-0}\) możliwości: \(\displaystyle{ 3^5}\)
\(\displaystyle{ A-2}\) możliwości: \(\displaystyle{ {5 \choose 2} \cdot 3^3}\)
\(\displaystyle{ A-4}\) możliwości: \(\displaystyle{ {5 \choose 4} \cdot 3^1}\)
Widać jak to idzie teraz dla dowolnego \(\displaystyle{ n}\)
\(\displaystyle{ a_{2n}=3^{2n}+ {2n \choose 2}3^{2n-2}+ {2n \choose 4}3^{2n-4}+...+{2n \choose 2n-2}3^{2}+1}\)
\(\displaystyle{ a_{2n+1}=3^{2n+1}+ {2n+1 \choose 2}3^{2n-1}+ {2n+1 \choose 4}3^{2n-3}+...+{2n+1 \choose 2n-2}3^{1}}\)
Końcówka inna dla parzystych inne dla nieparzystych...
Pierwsze zadanie nieczytelne!
- 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
równania rekurencyjne
Nie jest czytelnie, ale można się domyślić, o co chodziło.
Niech n będzie jakieś tam sobie odpowiednio duże dodatnie. Wtedy \(\displaystyle{ a_{n}=2a_{n-1}+5n=2(2a_{n-2}+5(n-1))+5n=...\mbox{zgadywanie}= \sum_{k=1}^{n} 2 ^{n-k} 5k}\)
To najpierw wykażemy indukcyjnie, że dobrze zgadłem. Dla \(\displaystyle{ n=1}\) mamy \(\displaystyle{ a_{1}=5= \sum_{k=1}^{1}2^{1-k}5k}\) (hiehie), czyli się zgadza. Teraz załóżmy, że formuła jest prawdziwa dla dowolnie ustalonego \(\displaystyle{ n \in \NN^{+}}\) i pokażemy, że działa też dla \(\displaystyle{ n+1}\):
\(\displaystyle{ a_{n+1}=2a_{n}+5(n+1)=\mbox{[zał.ind.]}=5n+5+2 \sum_{k=1}^{n}2^{n-k}5k= \sum_{k=1}^{n+1}2^{n+1-k}5k}\)
Teraz jeszcze można by podać zwartą postać \(\displaystyle{ \sum_{k=1}^{n}2^{n-k}5k}\), ale mi się nie chce klepać. Wskazówka: \(\displaystyle{ \sum_{k=1}^{n}2^{n-k}5k =5\cdot 2^{n} \sum_{k=1}^{n}k \left( \frac{1}{2} \right)^{k}}\). No i jakieś tam rózniczkowanko sumy \(\displaystyle{ n}\) początkowych wyrazów ciągu geometrycznego (łatwiej to zrobić ze zwartej postaci) - rozważaną funkcją będzie ta suma dla argumentu \(\displaystyle{ \frac{1}{2}}\).
BTW Czy w drugim mamy adeninę, cytozynę, guaninę i tyminę?
Niech n będzie jakieś tam sobie odpowiednio duże dodatnie. Wtedy \(\displaystyle{ a_{n}=2a_{n-1}+5n=2(2a_{n-2}+5(n-1))+5n=...\mbox{zgadywanie}= \sum_{k=1}^{n} 2 ^{n-k} 5k}\)
To najpierw wykażemy indukcyjnie, że dobrze zgadłem. Dla \(\displaystyle{ n=1}\) mamy \(\displaystyle{ a_{1}=5= \sum_{k=1}^{1}2^{1-k}5k}\) (hiehie), czyli się zgadza. Teraz załóżmy, że formuła jest prawdziwa dla dowolnie ustalonego \(\displaystyle{ n \in \NN^{+}}\) i pokażemy, że działa też dla \(\displaystyle{ n+1}\):
\(\displaystyle{ a_{n+1}=2a_{n}+5(n+1)=\mbox{[zał.ind.]}=5n+5+2 \sum_{k=1}^{n}2^{n-k}5k= \sum_{k=1}^{n+1}2^{n+1-k}5k}\)
Teraz jeszcze można by podać zwartą postać \(\displaystyle{ \sum_{k=1}^{n}2^{n-k}5k}\), ale mi się nie chce klepać. Wskazówka: \(\displaystyle{ \sum_{k=1}^{n}2^{n-k}5k =5\cdot 2^{n} \sum_{k=1}^{n}k \left( \frac{1}{2} \right)^{k}}\). No i jakieś tam rózniczkowanko sumy \(\displaystyle{ n}\) początkowych wyrazów ciągu geometrycznego (łatwiej to zrobić ze zwartej postaci) - rozważaną funkcją będzie ta suma dla argumentu \(\displaystyle{ \frac{1}{2}}\).
BTW Czy w drugim mamy adeninę, cytozynę, guaninę i tyminę?
- 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
równania rekurencyjne
Dobry jesteś Premislav z chemii czego o sobie nie mogę powiedzieć.
Oświeć mnie co za magiczne znaczenia mają te słowa. A może w tym zadaniu chodzi o jakieś DNA.
a nawet o tym nie wiedziałem!
Oświeć mnie co za magiczne znaczenia mają te słowa. A może w tym zadaniu chodzi o jakieś DNA.
a nawet o tym nie wiedziałem!