W
M
P
-U
K
SW
UWAGA! Wykład 9: niekompletny przykład 9.3, był błąd
na wykładzie. Wykład 10: brak przykładu po definicji błędu
względnego (definicja 10.2). Postaram uzupełnić wkrótce. Poza
tym wykłady 8 – 10 nie są sprawdzone. Nie wiem czy czas mi
pozwoli przepisać wykład 7 i pozostałe wykłady. Postaram się,
ale nie obiecuję.
Wykład 8
Równania rekurencyjne
SW
8.1. Przykłady równań rekurencyjnych
W
M
P
-U
K
Przykład 8.1 (Wieża z Hanoi). Rozważamy wieżę złożoną z n krążków,
które ułożone na jednym z trzech prętów A, B, C jeden na drugim w taki
sposób, że krążek o mniejszej średnicy leży na krążku o średnicy większej.
Zadanie polega na przeniesieniu wszystkich krążków wieży z pręta A na C
przekładając tylko po jednym krążku. Nie można położyć większego krążka
na mniejszym. Obliczymy najmniejszą liczbę kroków potrzebną do przeniesienia krążków z pręta A na C.
Rozwiązanie. Niech n będzie liczbą krążków, an liczbą kroków. Mając jeden
krążek możemy go przenieść od razu z A na C, zatem a1 = 1. W przypadku
dwóch krążków liczba kroków będzie równa a2 = 3 – najpierw przekładamy
mniejszy krążek na pręt B, krążek większy z A na pręt C, a następnie krążek
mniejszy z B na C.
Załóżmy teraz, że przenieśliśmy już n − 1 krążków z pręta A na pręt C.
Liczba kroków potrzebnych do ich przeniesienia na pręt B jest równa an−1 ,
aby przenieść krążki z pręta B na pręt C także musimy wykonać an−1 ruchów,
n-ty krążek można przenieść bezpośrednio na pręt C wykonując jeden ruch.
Stąd wynika, że an = 2an−1 + 1. Otrzymujemy zatem następujące równanie
rekurencyjne

a = 2a
n
n−1 + 1,
a1 = 1.
Wypisując kolejne wyrazy ciągu (an )
a1 = 1,
a2 = 3,
a3 = 7,
a4 = 15,
a5 = 31,
...
łatwo możemy odgadnąć, żę
(8.1)
an = 2n − 1.
Musimy jeszcze udowodnić otrzymany wzór. W tym celu zastosujemy indukcję względem n. Dla n = 1 mamy a1 = 21 − 1 = 1. Przypuśćmy teraz,
że wzór (8.1) jest prawdziwy dla n − 1 krążków, czyli, że prawdziwa jest
równość an−1 = 2n−1 − 1. Stąd
an = 2an−1 + 1 = 2 · (2n−1 − 1) + 1 = 2 · 2n−1 − 2 + 1 = 2n + 1.
Wobec tego wzór (8.1) jest prawdziwy dla każdego n ∈ N.
RK
39
♣
40
Wykład 8. Równania rekurencyjne
Przykład 8.2 (Jednorodne równania rekurencyjne).
Rozważmy równanie rekurencyjne
(8.2)
an = c1 an−1 + c2 an−2 + . . . + cr an−r ,
ci ∈ R
Podstawmy an = λn do równania (8.2). Otrzymamy w ten sposób
λn − c1 λn−1 − c2 λn−2 − . . . − cr λn−r = 0,
dzieląc obie strony powyższego równania przez λn−r otrzymamy
SW
λr − c1 λr−1 − c2 λr−2 − . . . − cr = 0.
(8.3)
Otrzymane równanie (8.2) nazywamy równaniem charakterystycznym.
Równanie to ma r pierwiastków λ1 , λ2 , . . . , λr . Wówczas λnk = an jest szczególnym rozwiązaniem. Jeśli wszystkie pierwiastki są różne, to każda kombinacja
liniowa jest rozwiązaniem równania
(8.4)
r
X
Ak λnk .
-U
K
an =
k=1
Poniższy przykład ilustruje zastosowanie wyżej opisanej metody w praktyce.
W
M
P
Przykład 8.3. Ile podzbiorów zbioru {1, 2, . . . , n} nie zawiera sąsiednich
liczb?
Rozwiązanie. Niech an będzie liczbą podzbiorów zbioru {1, 2, . . . , n} nie zawierających „sąsiadów”. W przypadku zbioru jednoelementowego A1 = {1}
mamy dwa takie podzbiory: zbiór A = {1} oraz zbiór pusty ∅, więc a1 = 2.
Jeśli zbiór jest dwuelementowy, powiedzmy A2 = {1, 2}, wówczas mamy następujące podzbiory:
A11 = ∅,
A21 = {1},
A31 = {2},
Podzbiór A41 = A nie spełnia warunków zadania, ponieważ 1 i 2 są liczbami sąsiednimi. Stąd a2 = 3. Spróbujmy wyznaczyć równanie rekurencyjne
dla n-elementowego zbioru. Liczba wszystkich podzbiorów bez „sąsiadów”,
nie zawierających n jest równa an−1 , natomiast liczba podzbiorów bez „sąsiadów”, ale zawierających n jest równa an−2 . Wówczas an = an−1 + an−2 .
Wypisując kolejne wyrazy ciągu an
a1 = 2,
a2 = 3,
a3 = 5,
a4 = 8,
a5 = 13,
...
Ciąg an jest przesuniętym ciągiem Fibonaciego (Fn )
F0 = 1,
F1 = 1,
Fn = Fn−1 + Fn−2 .
Podstawmy teraz an = λn . Wtedy
λn = λn−1 + λn−2 ,
λ2 = λ + 1.
/ : λn−2 ,
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
8.1. Przykłady równań rekurencyjnych
41
Przekształcając odpowiednio otrzymany wynik dotajemy równanie charakterystyczne
λ2 − λ − 1 = 0.
SW
Jest to równanie kwadratowe, dla którego ∆ = 5. Pierwiastki tego równania
są równe
√
√
1− 5
1+ 5
λ1 =
,
λ2 =
.
2
2
Stąd
√ !n
√ !n
1+ 5
1− 5
(8.5)
+ A2
.
a n = A1
2
2
Zauważmy, że dla zbioru pustego istnieje jeden podzbiór nie zawierający
„sąsiadów”. Jest nim oczywiście zbiór ∅, zatem możemy dodefiniować sobie
a0 = 1. Wtedy
a0 = A 1
Skąd A1 + A2 = 1. Ponadto
√ !1
√ !1
1− 5
1+ 5
+ A2
.
2
2
a 1 = A1
√
√
-U
K
√ !0
√ !0
1+ 5
1− 5
+ A2
= A1 + A2 ,
2
2
Skąd A1 1−2 5 + A2 1+2 5 = 2. Otrzymujemy zatem układ dwóch równań
z dwiema niewiadomymi A1 , A2
W
M
P

A + A = 1,
1
2
√ √ A1 1− 5 + A2 1+ 5 = 2.
2
2
Rozwiązując układ równań otrzymujemy
√
√
5+1
5−1
A2 = √ .
A1 = √ ,
2 5
2 5
Podstawiając A1 , A2 do równania (8.5) otrzymamy
√ !n √
√ !n
√
5−1 1− 5
5+1 1+ 5
an = √
+ √
.
2
2
2 5
2 5
√
√
oraz 5+1
odpowiednio do pierwszego i drugiego składnika
Włączając 5−1
2
2
powyzszej sumy ostatecznie otrzymamy rozwiązanie
1
an = √
5
√ !n+1
1
1+ 5
−√
2
5
√ !n+1
1− 5
.
2
♣
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
W
M
P
-U
K
SW
Wykład 9
Funkcje tworzące. Asymptotyka
SW
9.1. Funkcje tworzące
Definicja 9.1. Zwykłą funkcją tworzącą nazywamy szereg
f (x) =
∞
X
an x n .
n=0
-U
K
Definicja 9.2. Wykładniczą funkcją tworzącą nazywamy szereg
f (x) =
∞
X
an
n=0
n!
xn .
Przykład 9.1. Niech an będzie liczbą wszystkich funkcji ze zbioru n-elementowego w siebie. Wówczas an = nn . Zwykła funkcja tworząca, to szereg
f (x) =
∞
X
nn xn =
∞
X
(nx)n .
n=0
W
M
P
n=0
Szereg ten dla każdego x > 0 jest rozbieżny, natomiast wykładniczą funkcją
tworzącą jest szereg
∞
X
nn n
x .
f (x) =
n=0 n!
Ponieważ n! >
n
n
e
, więc nn < n!en , a zatem
nn xn
n!en xn
<
= en xn = (ex)n .
n!
n!
Wykładniczą funkcję tworzącą stosuje się na ogół w przypadkach, o których wiemy lub spodziewamy się, że an rośnie szybciej niż wykładniczo (wariacje, permutacje).
Przykład 9.2 (Wieża z Hanoi). Rozważmy przykład 8.1. Jawny wzór dla
równania rekurencyjnego

a = 1,
1
an = 2an−1 + 1,
n ­ 2,
wyprowadzimy korzystając z funkcji tworzących.
RK
43
44
Wykład 9. Funkcje tworzące. Asymptotyka
Rozwiązanie. Skorzystamy ze zwykłej funkcji tworzącej.
1
n
an x = a1 x +
∞
X
an xn =
n=2
n=1
∞
X
=x+
(2an−1 + 1)xn =
n=2
∞
X
=x+2
n
an−1 x +
n=2
∞
X
= x + 2x
∞
X
xn =
n=2
an−1 xn−1 +
n=2
= x + 2f (x) +
Otrzymaliśmy więc
x2
.
1−x
x2
=
1−x
SW
f (x) =
∞
X
x2
.
1−x
Po nietrudnych przekształceniach otrzymujemy
x
.
f (x) =
(1 − x)(1 − 2x)
-U
K
f (x) = x + 2xf (x) +
Po rozłożeniu prawej strony powyższej równości na ułamki proste otrzymamy
−x
2x
+
.
1 − x 1 − 2x
Teraz oba składniki powyższej sumy rozwijamy w szereg otrzymując
f (x) =
W
M
P
∞
X
−x
xn ,
=−
1−x
n=1
∞
X
2x
(2x)n .
=
1 − 2x n=1
Mamy zatem
f (x) = −
∞
X
n=1
xn +
∞
X
(2x)n =
∞
X
n=1
n=1
((2x)n − xn ) =
Mamy zatem an = coeff(xn ) = 2n − 1.
∞
X
n=1
(2n − 1) xn .
♣
Teraz zanotujemy kilka przydatnych wzorów.
∞
X
∞
X
n=0
xn =
n=0
∞
X
1
,
1−x
xn
= ex ,
n!
n=0
!
m+n−1 n
1
x =
,
n
1 − xm
n
X
xk =
k=0
n
X
k=0
!
1 − xn+1
,
1−x
n k n−k
a b
= (a + b)n .
k
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
45
9.2. Asymptotyka. Notacja O
Przykład 9.3. Podamy jawny wzór równania rekurencyjnego


a1 = 0,

a2 = 1,
an = (n − 1)(an−1 + an−2 ), n ­ 3.



Rozwiązanie. Zastosujemy wykładniczą funkcję tworzącą. Mamy
∞
X
an
n=1
n!
xn .
Różniczkujemy otrzymaną funkcję stronami.
f ′ (x) =
∞
X
an
n=1
∞
X
n!
nxn−1 =
SW
f (x) =
an
xn−1 =
(n
−
1)!
n=1
∞
X
a1
an
a2
= x0 + x1 +
xn−1 =
0!
1!
(n
−
1)!
n=3
∞
∞
X
n−1
(n − 1)an−1 n−1 X
x
+
an−2 xn−1 =
=0+1·x+
(n
−
1)!
(n
−
1)!
n=3
n=3
∞
∞
X
an−2 n−1
an−1 n−1 X
x
+
x
=
=x+
n=3 (n − 2)!
n=3 (n − 2)!
∞
∞
X
X
an−2 n−2
an−1 n−2
x
+x
x
=
=x+x
n=3 (n − 2)!
n=3 (n − 2)!
-U
K
=
!
W
M
P
a1 x 0
= x + x f (x) −
0!
′
= x + xf (x) + xf (x).
′
+ xf (x) =
Stąd, po odpowiednich przekształceniach dostajemy
f ′ (x) =
x(1 + f (x))
.
1−x
♣
9.2. Asymptotyka. Notacja O
Niech
Sn =
n
X
k=0
!
3n
.
k
Nie jest dotoąd znana postać jawna tej sumy. Wiadmo tylko, że
!
3n
.
Sn ∼ 2
n
(n)
Będziemy pisać f (n) ≺ g(n), jeśli n→∞
lim fg(n)
= 0.
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
46
Wykład 9. Funkcje tworzące. Asymptotyka
Przykład 9.4. Dla każdego n ∈ N oraz dla każdego k ­ l
n ≺ n2 ,
nl ≺ nk .
Ponadto, dla stałych c > 1 i ε ∈ (0, 1), (przyjmujemy oznaczenie log n ≡ ln n)
1 ≺ log log n ≺ log n ≺ nε ≺ nc ≺ nlog n ≺ cn ≺ nn .
Definicja 9.3. Będziemy pisali
jeśli istnieje stała c taka, że
|f (n)| ¬ c|g(n)|.
Przykład 9.5. Niech
n
X
SW
f (n) = O(g(n)),
1
1
1
1
1
(n + 1) = n3 + n2 + n.
k = n n+
S=
3
2
3
2
6
k=1
3
-U
K
Możemy napisać S = O(n3 ), ponieważ istnieje stała c = 1 taka, że |S| ¬ |n3 |.
Istotnie,
1 3
1 2 1 1 3
1
1
|S| = n + n + n ¬ |n | + |n2 | + |n| ¬
3
2
6
3
2
1 3
1
1 3
¬ |n | + |n | + |n| = 1 · |n3 |.
3
2
6
6
Możemy również napisać S = 31 n3 +O(n2 ), co jest lepszym oszacowaniem.
W
M
P
Uwaga 9.1. Nie można pisać odwrotnie, tzn.
f (n) = O(g(n)),
ale nie O(g(n)) = f (n).
Równość f (n) = O(g(n)) nie jest symetryczna.
Przykład 9.6. Wiadomo, że n = O(n2 ), ale również n2 = O(n2 ). Gdyby
drugą równość można było zamienić stronami, czyli zapisać jako równość
O(n2 ) = n2 , wówczas prawdziwa byłaby równość następująca
n = O(n2 ) = n2 ,
skąd otrzymalibyśmy n = n2 dla każdego n ∈ N, co jest nieprawdą.
Przykład 9.7. Przez równanie 13 n3 + O(n2 ) = O(n3 ) rozumiemy S1 ⊆ S2 ,
gdzie S1 jest zbiorem wszystkich funkcji postaci 31 n3 +f1 (n) takich, że istnieje
c takie, dla którego |f1 (n)| ¬ c|n2 |, natomiast S2 jest zbiorem wszystkich
funkcji f2 takich, że istnieje stała d, dla której |f2 (n)| ¬ d|n3 |.
Teraz pokażemy, że 13 n3 + O(n2 ) = O(n3 ).
Weźmy dowolną funkcję należącą do S1 . wykażemy, że należy ona również
do S2 . Chcemy pokazać, że
1 3
n + f1 (n) ¬ c|n3 |.
3
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
47
9.3. Notacje Ω, Θ
Istotnie,
1 3
1
1
n + f1 (n) ¬ |n3 | + |f1 (n)| ¬ |n3 | + c1 |n2 | ¬
3
3
3
1
1
¬ |n3 | + c1 |n3 | =
+ c1 |n3 |.
3
3
Wystarczy zatem za stałą c2 przyjąć
1
3
+ c1 .
♣
Przy dolnych granicach używamy notacji Ω:
(9.1)
f (n) = Ω(g(n)) ⇐⇒ |f (n)| ­ C|g(n)|
Prawdziwa jest równoważność
SW
9.3. Notacje Ω, Θ
dla pewnego c.
-U
K
f (n) = Ω(g(n)) ⇐⇒ g(n) = O(f (n)).
Wprowadźmy jeszcze notację Θ, która określa dokładny porządek wzrostu:
f (n) = Θ(g(n)) ⇐⇒ f (n) = O(g(n)) i f (n) = Ω(g(n)).
W
M
P
(9.2)
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
W
M
P
-U
K
SW
Wykład 10
Asymptotyka. Przekształcenia typu O
O(g(n))
10) 1 + O(f (n))
O(1).
-U
K
SW
Twierdzenie 10.1. Prawdziwe są następujące równości
1) nm = O(nk ), dla k ­ m,
2) O(f (n)) + O(g(n)) = O(|f (n)| + |g(n)|),
3) f (n) = O(f (n)),
4) c ·O(f (n)) = O(f (n)),
5) O O(f (n)) = O(f (n)),
6) O(f (n))O(g(n)) = O(f (n)g(n)),
7) O(f (n))O(f (n)) = (O(f (n)))2 ,
8) ln(1 + O(f (n))) = O(f (n)), dla f (n) < 1,
9) eO(f (n)) = 1 + O(f (n)), dla f (n) = O(1),
= 1 + O(f (n))g(n), dla f (n) < 1, f (n)g(n) =
Przykład 10.1.
z2 z3 z4
e =1+z+
+
+
+ O(z 5 ),
2!
3!
4!
W
M
P
z
1
= 1 + z + z 2 + z 3 + z 4 + O(z 5 ),
1−z
z2 z3 z4
+
−
+ O(z 5 ).
ln(1 + z) = 1 −
2
3
4
Dowód twierdzenia 10.1. (8) Weźmy dowolną funkcję należącą do lewej
strony równości (8)
ln(1 + g(n)), gdzie istnieje stała c taka, że|g(n)| ¬ c|f (n)| ¬ c < 1.
Mamy
(g(n))2 (g(n))3 (g(n))4
+
−
+ ... =
2
3
4
!
g(n) (g(n))2 (g(n))3
= g(n) 1 −
+
−
+ ... ¬
2
3
4
!
c c2 c3
¬ g(n) 1 − + − + . . . = c1 g(n).
2
3
4
ln(1 + g(n)) = g(n) −
(9) Weźmy funkcję postaci eg(n) . Wówczas
RK
49
50
Wykład 10. Asymptotyka. Przekształcenia typu O
(g(n))2 (g(n))3
+
+ ... ¬
2!
3!
!
g(n) (g(n))2
¬ 1 + g(n) 1 +
+
+ ... ¬
2!
3!
!
c1 c21
¬ 1 + g(n) 1 + + + . . . = 1 + c2 g(n).
2! 3!
eg(n) = 1 + g(n) +
O(g(n))
1 + O(f (n))
SW
(10)
O(g(n)) = exp ln 1 + O(f (n))
n
=
o
= exp O(g(n)) ln 1 + O(f (n))
na mocy (8)
=
-U
K
= exp {O(g(n))O(f (n))} =
= exp {O(g(n)f (n))} =
na mocy (9)
W
M
P
= 1 + O(g(n)f (n)).
Definicja 10.1. Błąd bezwzglęny przybliżenia asymptotycznego równy
jest O(g(n)), jeśli jest ono postaci f (n) + O(g(n)).
Definicja 10.2. Błąd względny przybliżenia asymptotycznego
równy jest
O(g(n)), jeśli jest ono postaci f (n) 1 + O(g(n)) .
10.1. Najbardziej znane przybliżenia asymptotyczne
Przykład 10.2 (Silnia).
n! ≈
√
n n
2πn
e
1
139
1
1
1+
−
+O 4
+
2
3
12n 288n
51840n
n
.
Przykład 10.3 (Liczby harmoniczne). Oznaczmy przez
n
X
1 1 1
1
1
Hn = 1 + + + + . . . + =
.
2 3 4
n k=1 k
n
Hn
0 1 2
3
4
5
6
7
8
0 1 3/2 11/6 25/12 137/60 49/20 363/140 761/280
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
51
10.1. Najbardziej znane przybliżenia asymptotyczne
Przykład 10.4 (Zadanie o robaku).
Powolny, lecz wytrwały robak R rozpoczyna wędrówkę od metrowej taśmy
i pełznie 1 cm na minutę. Pod koniec każdej minuty równie wytrwały właściciel taśmy W rozciąga taśmę równomiernie o metr, zatem po jednej minucie
robak R jest odległy o 1 cm od początku taśmy i 99 cm od końca. Wówczas W
rozciąga taśmę i robak R znajduje się 2 cm od początku i 198 cm od końca.
Po następnej minucie będzie 4,5 cm od początku i 295,5 cm od końca. Czy
R dotrze kiedyś do końca taśmy?
Rozwiązanie. Po n minutach robak R przebył
Zatem R osiągnie metę, gdy Hn przekroczy 100.
♣
Przykład 10.5. Pokazemy teraz, że lim Hn = +∞
n→∞
Dowód. Grupujemy składniki sumy Hn .
1
1
1
1
1
1
1
1 1 1 1 1 1 1 1
+ + + + + + + +
+
+
+
+
+
+...
5 {z 6 7} |8 9 10 11 {z12 13 14 15}
|2 {z 3} |4
2
3
-U
K
1 +
|{z}
SW
1
1
1
1
1 1
1
Hn
1
+
+
+
=
1 + + + ... +
=
.
100 200 300 n · 100
100
2 3
n
100
4
W grupie drugiej obydwa składniki są między
a 12 , skąd
1
1
¬ S2 ¬ 2 · ,
4
2
1
¬ S2 ¬ 1.
2
W
M
P
2·
1
4
Wszystkie składniki z grupy trzeciej leżą pomiędzy
4·
1
8
i 41 , zatem
1
1
¬ S3 ¬ 4 ,
8
4
1
¬ S3 ¬ 1.
2
Ogólnie, wszystkie składniki w grupie k-tej leżą w przedziale
2k−1
1
, 1 ,
2k 2k−1
skąd
1
1
¬ Sk ¬ 2k−1 k−1 ,
k
2
2
1
¬ Sk ¬ 1,
2
dla k = 1, 2, . . . , n. Stąd możemy już wywnioskować, że lim Hn = +∞.
n→∞
Suma pól prostokątów (rysunek 10.1 (a)) jest równa 1 + 21 + 13 + . . . + n1 =
Hn . Ponadto
Z n
1
dx = ln n.
1 x
Zauważmy również (rysunek 10.1 (b)), że Hn jest mniejsze od sumy
ℓ2 ([0, 1] × [0, 1]) +
Z
1
n
1
dx,
x
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
52
Wykład 10. Asymptotyka. Przekształcenia typu O
f (x)
f (x) =
1
x
1
2
3
4
5
...
n n+1
x
SW
(a)
f (x)
1
x
-U
K
f (x) =
1
2
3
4
5
...
n n+1
x
(b)
Rys. 10.1.
gdzie ℓ2 ([0, 1] × [0, 1]) oznacza pole prostokąta [0, 1] × [0, 1]. Wobec tego
W
M
P
Hn ¬ 1 + ln n.
Ostatecznie otrzymujemy, że ln n ¬ Hn ¬ 1 + ln n.
Asymptotyczny wzór na Hn ma następującą postać
1
1
1
1
+
+O 6 ,
−
Hn ≈ ln n + γ +
2
4
2n 12n
120n
n
gdzie γ = 0,577215664.
Korzystając z tego wzoru możemy obliczyć np. milionową liczbę harmoniczną
Hn ≈ 14,3927267.
Długowieczny
robak...
Przykład 10.6 (Zadanie o robaku cd.). Odpowiedź do zadania o robaku: robak R dotrze do końca taśmy, gdy n ≈ e99,423 , (287 decylionów wieków),
a taśma rozciągnie się na więcej niż 1027 lat świetlnych.
Przykład 10.7. Znaleźć wartość wartość asymptotyczną sumy
Sn = Hn2 +n − Hn2 .
Rozwiązanie. Ponieważ
H
n2 +n
1
1
1
= ln(n + n) + γ +
+O 8 ,
−
2
2
2
2(n + n) 12(n + n)
n
2
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
10.1. Najbardziej znane przybliżenia asymptotyczne
53
oraz
Hn2
1
1
1
= ln(n ) + γ + 2 −
+O 8 .
4
2n
12n
n
2
Ponadto
ln(n + n) = ln n
2
1
1+
n
=
1
=
n
1
1
1
= ln n2 + − 2 + 3 − . . . ,
n 2n
3n
= ln n2 + ln 1 +
oraz
n2
1
1
=
=
+n
n2 1 + n1
1 1
= 2
=
n 1 + n1
2
dalej, podstawiając
=
1
1
1−(− n
)
=
3
1
−
n
+ ... =
∞ P
k=0
− n1
k
1
1
1
1
− 3 + 4 − 5 + ... .
n n
n
n
Dalej skorzystamy ze wzoru
1
(1+x)n
1
1
=
= 4
2
+ n)
n (1 + n1 )2
=
∞ P
n+k−1
k=0
W
M
P
(n2
!
-U
K
1
1
1
= 2 1− +
n
n
n
SW
2
k
xk .
!
∞
1 X
2+k−1 1
= 4
=
n k=0
nk
k
1
= 4
n
1
= 4
n
1
= 4
n
∞
X
(k + 1)
k=0
k
1
n
=
2
4
3
1 + + 2 + 3 + ... =
n n
n
2
3
4
+ 5 + 6 + 7 + ....
n
n
n
Ostatecznie
1
1
1
1
1
1
− 2 + 3 − ... + γ + 2 − 3 + 4−
n 2n
3n
2n
2n
2n
1
2
3
4
1
−
−
−
− ...
− 5 + ... −
2n
12n4 12n5 12n6 12n7
1
1
=
− ln n2 − γ − 2 +
2n
12n4
1
1
1
1
2
1
1
= − 2− 3+ 4−
+
+O 7 .
5
6
n 2n
6n
4n
15n
12n
n
Hn2 +n − Hn2 = ln n2 +
♣
Notatki do wykładu Matematyka dyskretna prowadzonego przez dr Justynę Kurkowiak na WMP UKSW w Warszawie
Download

Wykład - cz. 8-10