Witam, mam problem z takimi przykładami, kompletnie nie wiem jak za nie sie zabrać.:
1. Podaj wzór jawny na \(\displaystyle{ s_{2^m}}\)
a) \(\displaystyle{ S_{2n}=2_{sn}+5n, s_{1}=0}\)
b) \(\displaystyle{ S_{2n}=2_{sn}-7, s_{1}=1}\)
2.Korzystając z czynnika sumacyjnego rozwiązać podane rekurencje:
\(\displaystyle{ t_{0}=5, 2t_{n}=nt_{n-1} + 3n!, n \ge 1}\)
Proszę o jakąkolwiek pomoc.
Wzor jawny i czynnik sumacyjny
-
arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Wzor jawny i czynnik sumacyjny
Pokaże ci na przykładzie zadania 2 bo w pierwszym nie wiem co pisze:
trzeba zrobić tak:
\(\displaystyle{ a_{n}=2, b_{n}=n, c_{n}=3n!}\)
weź sobie teraz ciąg sn
\(\displaystyle{ s_{n}= \frac{a_{n-1}}{b_{n}}s_{n-1}= \frac{2}{n}s_{n-1}}\)
Pomnożymy teraz równanie wyjściowe przez sn i mamy:
\(\displaystyle{ 2t_{n}s_{n}= \frac{2}{n}nt_{n-1}s_{n-1}+3n!s_{n}}\)
\(\displaystyle{ 2t_{n}s_{n}= 2t_{n-1}s_{n-1}+3n!s_{n}}\)
zróbmy następne podstawienie:
\(\displaystyle{ U_{n}=2t_{n}s_{n}}\)
Czyli:
\(\displaystyle{ U_{n}=U_{n-1}+3n!s_{n}}\)
łatwo zauważyć, że:
\(\displaystyle{ U_{n}=2t_{n}s_{n}=U_{0}+3 \sum_{k=1}^{n}k!s_{k}=s_{0}*2*t_{0}+3 \sum_{k=1}^{n}k!s_{k}=10s_{0}+3 \sum_{k=1}^{n}k!s_{k}}\)
ostatecznie:
\(\displaystyle{ t_{n}= \frac{1}{2s_{n}}(10s_{0}+3 \sum_{k=1}^{n}k!s_{k})}\)
łatwo zauważyć, że przyjmując za s0=1 rekurencyjnie otrzymasz
\(\displaystyle{ s_{n}= \frac{2^{n}}{n!}}\)
a co za tym idzie:
\(\displaystyle{ t_{n}= \frac{n!}{2^{n+1}}(10+3 \sum_{k=1}^{n}k! \frac{2^{k}}{k!})}\)
lub:
\(\displaystyle{ t_{n}= \frac{n!}{2^{n+1}}(10+3 \sum_{k=1}^{n}2^{k})}\)
lub jeszcze prościej:
\(\displaystyle{ t_{n}=(2^{-n+1}+3)*n!}\)
mogłem się gdzieś walnąć ale idea jest waśnie taka-- 7 stycznia 2011, 03:44 --Ciekawi mnie tylko skąd wytrzasnąłeś takie zadanie z jakiego zbioru???
i kto to zadaje???
trzeba zrobić tak:
\(\displaystyle{ a_{n}=2, b_{n}=n, c_{n}=3n!}\)
weź sobie teraz ciąg sn
\(\displaystyle{ s_{n}= \frac{a_{n-1}}{b_{n}}s_{n-1}= \frac{2}{n}s_{n-1}}\)
Pomnożymy teraz równanie wyjściowe przez sn i mamy:
\(\displaystyle{ 2t_{n}s_{n}= \frac{2}{n}nt_{n-1}s_{n-1}+3n!s_{n}}\)
\(\displaystyle{ 2t_{n}s_{n}= 2t_{n-1}s_{n-1}+3n!s_{n}}\)
zróbmy następne podstawienie:
\(\displaystyle{ U_{n}=2t_{n}s_{n}}\)
Czyli:
\(\displaystyle{ U_{n}=U_{n-1}+3n!s_{n}}\)
łatwo zauważyć, że:
\(\displaystyle{ U_{n}=2t_{n}s_{n}=U_{0}+3 \sum_{k=1}^{n}k!s_{k}=s_{0}*2*t_{0}+3 \sum_{k=1}^{n}k!s_{k}=10s_{0}+3 \sum_{k=1}^{n}k!s_{k}}\)
ostatecznie:
\(\displaystyle{ t_{n}= \frac{1}{2s_{n}}(10s_{0}+3 \sum_{k=1}^{n}k!s_{k})}\)
łatwo zauważyć, że przyjmując za s0=1 rekurencyjnie otrzymasz
\(\displaystyle{ s_{n}= \frac{2^{n}}{n!}}\)
a co za tym idzie:
\(\displaystyle{ t_{n}= \frac{n!}{2^{n+1}}(10+3 \sum_{k=1}^{n}k! \frac{2^{k}}{k!})}\)
lub:
\(\displaystyle{ t_{n}= \frac{n!}{2^{n+1}}(10+3 \sum_{k=1}^{n}2^{k})}\)
lub jeszcze prościej:
\(\displaystyle{ t_{n}=(2^{-n+1}+3)*n!}\)
mogłem się gdzieś walnąć ale idea jest waśnie taka-- 7 stycznia 2011, 03:44 --Ciekawi mnie tylko skąd wytrzasnąłeś takie zadanie z jakiego zbioru???
i kto to zadaje???
-
abc666
Wzor jawny i czynnik sumacyjny
wagus1, jeśli
\(\displaystyle{ s_{2n}=2s_n+f(n)}\)
to
\(\displaystyle{ s_{2^m}=2^m\left(s_1 +\frac{1}{2}\sum_{i=0}^{m-1} \frac{f(2^i)}{2^i} \right)}\)
W szczególności jeśli \(\displaystyle{ f(n)=An+B}\)
to
\(\displaystyle{ s_{2^m}=2^ms_1+(2^m-1)A+2^{m-1}mB}\)
Żeby dojść do tego pierwszego wzoru wystarczy podstawić pod \(\displaystyle{ 2^{m-1}}\) pod \(\displaystyle{ n}\).
\(\displaystyle{ s_{2n}=2s_n+f(n)}\)
to
\(\displaystyle{ s_{2^m}=2^m\left(s_1 +\frac{1}{2}\sum_{i=0}^{m-1} \frac{f(2^i)}{2^i} \right)}\)
W szczególności jeśli \(\displaystyle{ f(n)=An+B}\)
to
\(\displaystyle{ s_{2^m}=2^ms_1+(2^m-1)A+2^{m-1}mB}\)
Żeby dojść do tego pierwszego wzoru wystarczy podstawić pod \(\displaystyle{ 2^{m-1}}\) pod \(\displaystyle{ n}\).
To zadanie każde musi być z jakiego zbioru? To są standardowe zadania.arek1357 pisze:Ciekawi mnie tylko skąd wytrzasnąłeś takie zadanie z jakiego zbioru???
i kto to zadaje???
-
arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Wzor jawny i czynnik sumacyjny
Sprawdzałem indukcyjnie i się zgadza.
Mam dużo zbiorów ale podobnych zadań nie widziałem, dlatego mnie to dziwi bo co do standartowego zbioru to nie znam takiego. Bo ciekawi mnie i chodzi mi o to w jakich szkołach zadają zadania określonego
typu. Robię sobie potem mapy szkół i widzę co gdzie jaki typ zadań i jaki poziom się plasuje.
Ostatnio się spotkałem , że w szkole średniej uczą ułamków, itd...w innej czytanie danych liczbowych z grafu, w innej mówili już o grupach cyklicznych. Podobna różnorodność jest w placówkach wyższych,
w jednej mówią o grafach w innych o tym nie wspominają, przykładów można mnożyć...
Ja natomiast po rodzaju zadań i problemów, z którymi jacyś znajomi do mnie przyjdą mam obraz tego co dana szkoła przekazuje słuchaczowi i dlatego ten problem poruszyłem...
A druga sprawa dobrze by było na bazie tego zadania postawić inny problem:
dla jakich n w ciągu:
\(\displaystyle{ t_{n}=(2^{-n+1}+3)*n!}\)
Wyrazy są całkowite, a które niecałkowite i właśnie stawiam ten problem.
Może jest banalny albo i nie na razie nic niewiem.
-- 7 stycznia 2011, 11:53 --
W 1b wyszło mi:
\(\displaystyle{ S_{n}=7-6n}\)
pod warunkiem że prawidłowo pisze tam:
\(\displaystyle{ S_{2n}=2*S_{n}-7}\)
Sn to ciąg sum ciągu jakiegoś an
Mam dużo zbiorów ale podobnych zadań nie widziałem, dlatego mnie to dziwi bo co do standartowego zbioru to nie znam takiego. Bo ciekawi mnie i chodzi mi o to w jakich szkołach zadają zadania określonego
typu. Robię sobie potem mapy szkół i widzę co gdzie jaki typ zadań i jaki poziom się plasuje.
Ostatnio się spotkałem , że w szkole średniej uczą ułamków, itd...w innej czytanie danych liczbowych z grafu, w innej mówili już o grupach cyklicznych. Podobna różnorodność jest w placówkach wyższych,
w jednej mówią o grafach w innych o tym nie wspominają, przykładów można mnożyć...
Ja natomiast po rodzaju zadań i problemów, z którymi jacyś znajomi do mnie przyjdą mam obraz tego co dana szkoła przekazuje słuchaczowi i dlatego ten problem poruszyłem...
A druga sprawa dobrze by było na bazie tego zadania postawić inny problem:
dla jakich n w ciągu:
\(\displaystyle{ t_{n}=(2^{-n+1}+3)*n!}\)
Wyrazy są całkowite, a które niecałkowite i właśnie stawiam ten problem.
Może jest banalny albo i nie na razie nic niewiem.
-- 7 stycznia 2011, 11:53 --
W 1b wyszło mi:
\(\displaystyle{ S_{n}=7-6n}\)
pod warunkiem że prawidłowo pisze tam:
\(\displaystyle{ S_{2n}=2*S_{n}-7}\)
Sn to ciąg sum ciągu jakiegoś an
-
abc666
Wzor jawny i czynnik sumacyjny
Ja to miałem na dyskretnej w pierwszym semestrze.
\(\displaystyle{ t_n=3n!+\frac{n!}{2^{n-1}}}\)
Kwestia teraz ile dwójek ma w rozkładzie \(\displaystyle{ n!}\). Ze znanego wzoru
\(\displaystyle{ \alpha_p(n!)=\sum_{i=1}^\infty \left[\frac{n}{p^i}\right]}\)
wynika że musi znaleźć takie n dla których
\(\displaystyle{ \alpha_2(n!)\ge n-1}\)
Najpierw rozpatrzmy \(\displaystyle{ n=2^k}\), mamy wtedy
\(\displaystyle{ \alpha_2((2^k)!)=2^{k-1}+2^{k-2}+...+1=2^k-1}\)
Więc nierówność jest spełniona (mamy równość)
Teraz weźmy n nie będące potęgą dwójki tzn
\(\displaystyle{ n=2^k+l}\), gdzie \(\displaystyle{ l\in\{1,2,...,2^{k}-1\}}\)
Mamy wtedy
\(\displaystyle{ \alpha_2((2^k+l)!) \le (2^{k-1}+\frac{l}{2})+(2^{k-2}+\frac{l}{2^2})+...+(2+
\frac{l}{2^{k-1}})+(1+\frac{l}{2^{k}})=2^k-1+l(1-\frac{1}{2^{k}})<2^k-1+l}\)
Stąd \(\displaystyle{ t_n}\) jest całkowite tylko dla \(\displaystyle{ n}\) będącego potęgami dwójki.
Trochę off-topic się robi ale:arek1357 pisze: \(\displaystyle{ t_{n}=(2^{-n+1}+3)*n!}\)
Wyrazy są całkowite, a które niecałkowite i właśnie stawiam ten problem.
\(\displaystyle{ t_n=3n!+\frac{n!}{2^{n-1}}}\)
Kwestia teraz ile dwójek ma w rozkładzie \(\displaystyle{ n!}\). Ze znanego wzoru
\(\displaystyle{ \alpha_p(n!)=\sum_{i=1}^\infty \left[\frac{n}{p^i}\right]}\)
wynika że musi znaleźć takie n dla których
\(\displaystyle{ \alpha_2(n!)\ge n-1}\)
Najpierw rozpatrzmy \(\displaystyle{ n=2^k}\), mamy wtedy
\(\displaystyle{ \alpha_2((2^k)!)=2^{k-1}+2^{k-2}+...+1=2^k-1}\)
Więc nierówność jest spełniona (mamy równość)
Teraz weźmy n nie będące potęgą dwójki tzn
\(\displaystyle{ n=2^k+l}\), gdzie \(\displaystyle{ l\in\{1,2,...,2^{k}-1\}}\)
Mamy wtedy
\(\displaystyle{ \alpha_2((2^k+l)!) \le (2^{k-1}+\frac{l}{2})+(2^{k-2}+\frac{l}{2^2})+...+(2+
\frac{l}{2^{k-1}})+(1+\frac{l}{2^{k}})=2^k-1+l(1-\frac{1}{2^{k}})<2^k-1+l}\)
Stąd \(\displaystyle{ t_n}\) jest całkowite tylko dla \(\displaystyle{ n}\) będącego potęgami dwójki.
-
arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Wzor jawny i czynnik sumacyjny
Bardzo ładne i pożyteczne rozwiązanie wszystko jasne!!!
AAA miałeś coś takiego w pierwszym semestrze to ja się pytam jeśli można jaka to uczelnia.
Już mam dobre zdanie o tej szkole bo niestety jak mówiłem na razie się z czynnikami sumacyjnymi nigdzie nie spotkałem dlatego pytam.
AAA miałeś coś takiego w pierwszym semestrze to ja się pytam jeśli można jaka to uczelnia.
Już mam dobre zdanie o tej szkole bo niestety jak mówiłem na razie się z czynnikami sumacyjnymi nigdzie nie spotkałem dlatego pytam.
-
manduka
- Użytkownik
- Posty: 350
- Rejestracja: 7 lis 2011, o 20:48
- Płeć: Mężczyzna
- Podziękował: 83 razy
- Pomógł: 15 razy
Wzor jawny i czynnik sumacyjny
mam pytanie odnośnie tej części, dlaczego 2 podstawiliśmy za \(\displaystyle{ a_{n-1}}\)skoro \(\displaystyle{ a_{n}=2}\) ??Pokaże ci na przykładzie zadania 2 bo w pierwszym nie wiem co pisze:
trzeba zrobić tak:
\(\displaystyle{ a_{n}=2, b_{n}=n, c_{n}=3n!}\)
weź sobie teraz ciąg sn
\(\displaystyle{ s_{n}= \frac{a_{n-1}}{b_{n}}s_{n-1}= \frac{2}{n}s_{n-1}}\)
Wzor jawny i czynnik sumacyjny
Masz w tym kombinatoryka-i-matematyka-dyskretna-f4 ... 78985.html temacie odpowiedź, dokładnie o to samo pytałam, 6 ostatnich postów.manduka pisze:
mam pytanie odnośnie tej części, dlaczego 2 podstawiliśmy za \(\displaystyle{ a_{n-1}}\)skoro \(\displaystyle{ a_{n}=2}\) ??
Wzor jawny i czynnik sumacyjny
od tego momentu nie rozumiem co się dzieje. Czy można prosić o trochę więcej komentarza dlaczego tak i skąd?arek1357 pisze:(...)
łatwo zauważyć, że:
\(\displaystyle{ U_{n}=2t_{n}s_{n}=U_{0}+3 \sum_{k=1}^{n}k!s_{k}=s_{0}*2*t_{0}+3 \sum_{k=1}^{n}k!s_{k}=10s_{0}+3 \sum_{k=1}^{n}k!s_{k}}\)
ostatecznie:
\(\displaystyle{ t_{n}= \frac{1}{2s_{n}}(10s_{0}+3 \sum_{k=1}^{n}k!s_{k})}\)
łatwo zauważyć, że przyjmując za s0=1 rekurencyjnie otrzymasz
\(\displaystyle{ s_{n}= \frac{2^{n}}{n!}}\)
a co za tym idzie:
\(\displaystyle{ t_{n}= \frac{n!}{2^{n+1}}(10+3 \sum_{k=1}^{n}k! \frac{2^{k}}{k!})}\)
lub:
\(\displaystyle{ t_{n}= \frac{n!}{2^{n+1}}(10+3 \sum_{k=1}^{n}2^{k})}\)
lub jeszcze prościej:
\(\displaystyle{ t_{n}=(2^{-n+1}+3)*n!}\)
mogłem się gdzieś walnąć ale idea jest waśnie taka