równania rekurencyjne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
paulina95
Użytkownik
Użytkownik
Posty: 25
Rejestracja: 4 kwie 2015, o 12:26
Płeć: Kobieta
Lokalizacja: katowice
Podziękował: 3 razy

równania rekurencyjne

Post autor: paulina95 »

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?
Ostatnio zmieniony 6 kwie 2015, o 20:55 przez paulina95, łącznie zmieniany 1 raz.
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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!
paulina95
Użytkownik
Użytkownik
Posty: 25
Rejestracja: 4 kwie 2015, o 12:26
Płeć: Kobieta
Lokalizacja: katowice
Podziękował: 3 razy

równania rekurencyjne

Post autor: paulina95 »

Edytowałam pierwsze. Powinno już być czytelne.
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

równania rekurencyjne

Post autor: Premislav »

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ę?
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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!
ODPOWIEDZ