Witam.
Mam problem ze zrozumieniem części zadania. Mam \(\displaystyle{ T \left( n \right) =2T \left( \left[ \frac{n}{2} \right] +17 \right) +n}\) i muszę wykazać metodą podstawiania że jest to równe \(\displaystyle{ O \left( n\log n \right)}\). Nie rozumiem pierwszego kroku czyli indukcji matematycznej z której wychodzi \(\displaystyle{ T \left( n \right) =2c\cdot \left( \frac{n}{2}+17 \right) \cdot \log \left( \frac{n}{2}+17 \right) +n}\). Co muszę zrobić aby tak wyszło?
Indukcja matematyczna w rekurencji
-
piotr159
- Użytkownik
- Posty: 7
- Rejestracja: 12 kwie 2018, o 15:51
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
Indukcja matematyczna w rekurencji
Ostatnio zmieniony 27 kwie 2018, o 17:49 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot. Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot. Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd.
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Indukcja matematyczna w rekurencji
Najpierw zauważ:
\(\displaystyle{ T(2n-1)=2T(n+16)+2n-1}\)
\(\displaystyle{ T(2n)=2T(n+17)+2n}\)
\(\displaystyle{ T(2n+1)=2T(n+17)+2n+1}\)
\(\displaystyle{ T(2n+2)=2T(n+18)+2n+2}\)
..........................................................
mamy:
\(\displaystyle{ T(2n+2)-T(2n+1)=2T(n+18)-2T(n+17)+1}\)
Zrób podstawienie:
\(\displaystyle{ T(2n+2)-T(2n+1)=a_{2n}}\)
I wtedy:
\(\displaystyle{ a_{2n}=2a_{n+17}+1 , n \ge 17}\)
Zauważ tu trzba się bawić:
\(\displaystyle{ a_{34}=-1}\)
podstaw sobie np:
\(\displaystyle{ a_{35}=1}\)
\(\displaystyle{ a_{36}=2a_{35}+1=3 , n=18}\)
\(\displaystyle{ a_{38}=2a_{36}+1=7 , n=19}\)
\(\displaystyle{ a_{42}=2a_{38}+1=15 , n=21}\)
\(\displaystyle{ a_{50}=2a_{42}+1=31 , n=25}\)
..............................................................
Ogólnie:
\(\displaystyle{ a_{2^n+34}=2^{n+1}-1}\)
Popatrz tu podobnie:
https://www.matematyka.pl/413512.htm
-- 30 kwietnia 2018, 06:52 --
Lub:
\(\displaystyle{ a_{n}=2n-69}\)
-- 30 kwietnia 2018, 10:54 --
Możesz to zapisać w ten sposób teraz:
Zauważ, że:
(1)\(\displaystyle{ T(2n+2)-T(2n+1)=2n-69}\)
(2)\(\displaystyle{ T(2n+1)-T(2n)=1}\)
Można to więc zapisać tak:
Rozwiązując równanie rekurencyjne (1), nie wdając się w szczegóły otrzymamy:
\(\displaystyle{ T(n)=n^2-72n+1}\)
na razie olewam warunki początkowe, przyjmuję jedynkę...
Możemy to zapisać tak:
\(\displaystyle{ T(n)=\begin{cases}n^2-72n+1 , n=0,2,4,6,... \\ T(n-1)+1 , n=1,3,5,7,...\end{cases}}\)
To jeszcze nie szczyt marzeń, ale zastosujmy szeregi:
\(\displaystyle{ \sum_{n=0}^{ \infty }T(n)x^{n}= \sum_{n=0}^{ \infty }T(2n)x^{2n}+ \sum_{n=0}^{ \infty }T(2n+1)x^{2n+1}=}\)
\(\displaystyle{ = \sum_{n=0}^{ \infty }\left( 4n^2-144n+1\right) x^{2n}+ \sum_{n=0}^{ \infty }\left[ T(2n)+1\right] x^{2n+1}=}\)
\(\displaystyle{ \left( 1+x\right) \sum_{n=0}^{ \infty }\left( 4n^2-144n+1\right) x^{2n}+ \frac{x}{1-x^2}=}\)
\(\displaystyle{ =(1+x)\left[ 4 \sum_{n=0}^{ \infty }n^2x^{2n}-144 \sum_{n=0}^{ \infty }nx^{2n} + \sum_{n=0}^{ \infty }x^{2n} \right]+ \frac{x}{1-x^2}}\)
A teraz zwijanie poszczególnych sum
-- 30 kwietnia 2018, 19:55 --
\(\displaystyle{ \sum_{n=0}^{ \infty }n^2x^{2n}}\)
podstawisz:
\(\displaystyle{ y=x^2}\)
otrzymasz:
\(\displaystyle{ \sum_{n=0}^{ \infty }n^2y^{n}=y^2 \left[ \sum_{n=0}^{ \infty }y^n\right]''+y\left[ \sum_{n=0}^{ \infty }y^n\right]'}\)
Robisz takie sztuczki i na koniec powinno wyjść nie chce mi się już tego wpisywać dokładnie:
\(\displaystyle{ (1+x)\left[ 4 \frac{x^2(1+x^2)}{(1-x^2)^3}-144 \frac{x^2}{(1-x^2)^2}+ \frac{1}{1-x^2} \right]}\)
-- 30 kwietnia 2018, 20:01 --
Po skróceniu:
\(\displaystyle{ =\frac{150x^4-x^3-143x^2+x+1}{(1-x)^3(1+x)^2}=}\)
-- 30 kwietnia 2018, 20:06 --
\(\displaystyle{ = \frac{2}{(1-x)^3} - \frac{76}{(1-x)^2}+ \frac{112}{1-x}+ \frac{1}{(1+x)^2}- \frac{38}{1+x}}\)
-- 30 kwietnia 2018, 20:19 --
\(\displaystyle{ = \sum_{n=0}^{ \infty }(1+n)(2+n)x^n-76 \sum_{n=0}^{ \infty }(1+n)x^n+112 \sum_{n=0}^{ \infty }x^n+ \sum_{n=0}^{ \infty }(-1)^n(1+n)x^n-38 \sum_{n=0}^{ \infty }(-1)^nx^n=}\)
-- 30 kwietnia 2018, 20:24 --
\(\displaystyle{ = \sum_{n=0}^{ \infty }\left[ \left( n^2-73n+38\right)+(-1)^n\left( n-37\right) \right] x^n}\)
-- 30 kwietnia 2018, 23:00 --
Czyli:
\(\displaystyle{ T(n)=n^2-73n+38+(-1)^n(n-37)}\)
I jak sprawdziłem jest ten wzór kompatybilny z tym:
\(\displaystyle{ T(n)=\begin{cases}n^2-72n+1 , n=02468,... \\ T(n-1)+1 , n=1,3,5,7,9,... end{cases}}\)
Ta na porządnie to trzeba by było uwzględniać warunki początkowe i się z tym bawić...
Ale to z tymi logarytmami to dziwne bo wystarczy tam nawet kilka wstawić i wyjdą niewymierne...
Może to chodzi o jakąś aproksymację logarytmem...-- 30 kwietnia 2018, 23:02 --Przepadło wpadło i nie poprawię bo mnie nie będzie więc może jakiś prorok poprawi...
Tu ukłony w kierunku moderacji ...
\(\displaystyle{ T(2n-1)=2T(n+16)+2n-1}\)
\(\displaystyle{ T(2n)=2T(n+17)+2n}\)
\(\displaystyle{ T(2n+1)=2T(n+17)+2n+1}\)
\(\displaystyle{ T(2n+2)=2T(n+18)+2n+2}\)
..........................................................
mamy:
\(\displaystyle{ T(2n+2)-T(2n+1)=2T(n+18)-2T(n+17)+1}\)
Zrób podstawienie:
\(\displaystyle{ T(2n+2)-T(2n+1)=a_{2n}}\)
I wtedy:
\(\displaystyle{ a_{2n}=2a_{n+17}+1 , n \ge 17}\)
Zauważ tu trzba się bawić:
\(\displaystyle{ a_{34}=-1}\)
podstaw sobie np:
\(\displaystyle{ a_{35}=1}\)
\(\displaystyle{ a_{36}=2a_{35}+1=3 , n=18}\)
\(\displaystyle{ a_{38}=2a_{36}+1=7 , n=19}\)
\(\displaystyle{ a_{42}=2a_{38}+1=15 , n=21}\)
\(\displaystyle{ a_{50}=2a_{42}+1=31 , n=25}\)
..............................................................
Ogólnie:
\(\displaystyle{ a_{2^n+34}=2^{n+1}-1}\)
Popatrz tu podobnie:
https://www.matematyka.pl/413512.htm
-- 30 kwietnia 2018, 06:52 --
Lub:
\(\displaystyle{ a_{n}=2n-69}\)
-- 30 kwietnia 2018, 10:54 --
Możesz to zapisać w ten sposób teraz:
Zauważ, że:
(1)\(\displaystyle{ T(2n+2)-T(2n+1)=2n-69}\)
(2)\(\displaystyle{ T(2n+1)-T(2n)=1}\)
Można to więc zapisać tak:
Rozwiązując równanie rekurencyjne (1), nie wdając się w szczegóły otrzymamy:
\(\displaystyle{ T(n)=n^2-72n+1}\)
na razie olewam warunki początkowe, przyjmuję jedynkę...
Możemy to zapisać tak:
\(\displaystyle{ T(n)=\begin{cases}n^2-72n+1 , n=0,2,4,6,... \\ T(n-1)+1 , n=1,3,5,7,...\end{cases}}\)
To jeszcze nie szczyt marzeń, ale zastosujmy szeregi:
\(\displaystyle{ \sum_{n=0}^{ \infty }T(n)x^{n}= \sum_{n=0}^{ \infty }T(2n)x^{2n}+ \sum_{n=0}^{ \infty }T(2n+1)x^{2n+1}=}\)
\(\displaystyle{ = \sum_{n=0}^{ \infty }\left( 4n^2-144n+1\right) x^{2n}+ \sum_{n=0}^{ \infty }\left[ T(2n)+1\right] x^{2n+1}=}\)
\(\displaystyle{ \left( 1+x\right) \sum_{n=0}^{ \infty }\left( 4n^2-144n+1\right) x^{2n}+ \frac{x}{1-x^2}=}\)
\(\displaystyle{ =(1+x)\left[ 4 \sum_{n=0}^{ \infty }n^2x^{2n}-144 \sum_{n=0}^{ \infty }nx^{2n} + \sum_{n=0}^{ \infty }x^{2n} \right]+ \frac{x}{1-x^2}}\)
A teraz zwijanie poszczególnych sum
-- 30 kwietnia 2018, 19:55 --
\(\displaystyle{ \sum_{n=0}^{ \infty }n^2x^{2n}}\)
podstawisz:
\(\displaystyle{ y=x^2}\)
otrzymasz:
\(\displaystyle{ \sum_{n=0}^{ \infty }n^2y^{n}=y^2 \left[ \sum_{n=0}^{ \infty }y^n\right]''+y\left[ \sum_{n=0}^{ \infty }y^n\right]'}\)
Robisz takie sztuczki i na koniec powinno wyjść nie chce mi się już tego wpisywać dokładnie:
\(\displaystyle{ (1+x)\left[ 4 \frac{x^2(1+x^2)}{(1-x^2)^3}-144 \frac{x^2}{(1-x^2)^2}+ \frac{1}{1-x^2} \right]}\)
-- 30 kwietnia 2018, 20:01 --
Po skróceniu:
\(\displaystyle{ =\frac{150x^4-x^3-143x^2+x+1}{(1-x)^3(1+x)^2}=}\)
-- 30 kwietnia 2018, 20:06 --
\(\displaystyle{ = \frac{2}{(1-x)^3} - \frac{76}{(1-x)^2}+ \frac{112}{1-x}+ \frac{1}{(1+x)^2}- \frac{38}{1+x}}\)
-- 30 kwietnia 2018, 20:19 --
\(\displaystyle{ = \sum_{n=0}^{ \infty }(1+n)(2+n)x^n-76 \sum_{n=0}^{ \infty }(1+n)x^n+112 \sum_{n=0}^{ \infty }x^n+ \sum_{n=0}^{ \infty }(-1)^n(1+n)x^n-38 \sum_{n=0}^{ \infty }(-1)^nx^n=}\)
-- 30 kwietnia 2018, 20:24 --
\(\displaystyle{ = \sum_{n=0}^{ \infty }\left[ \left( n^2-73n+38\right)+(-1)^n\left( n-37\right) \right] x^n}\)
-- 30 kwietnia 2018, 23:00 --
Czyli:
\(\displaystyle{ T(n)=n^2-73n+38+(-1)^n(n-37)}\)
I jak sprawdziłem jest ten wzór kompatybilny z tym:
\(\displaystyle{ T(n)=\begin{cases}n^2-72n+1 , n=02468,... \\ T(n-1)+1 , n=1,3,5,7,9,... end{cases}}\)
Ta na porządnie to trzeba by było uwzględniać warunki początkowe i się z tym bawić...
Ale to z tymi logarytmami to dziwne bo wystarczy tam nawet kilka wstawić i wyjdą niewymierne...
Może to chodzi o jakąś aproksymację logarytmem...-- 30 kwietnia 2018, 23:02 --Przepadło wpadło i nie poprawię bo mnie nie będzie więc może jakiś prorok poprawi...
Tu ukłony w kierunku moderacji ...