Matematyka dyskretna
dla informatyków
Cz¦±¢ I: Elementy kombinatoryki
Jerzy Jaworski
Zbigniew Palka
Jerzy Szyma«ski
Uniwersytet im. Adama Mickiewicza
Pozna« 2007
Matematyka dyskretna
dla informatyków
Cz¦±¢ I: Elementy kombinatoryki
Jerzy Jaworski
Zbigniew Palka
Jerzy Szyma«ski
Uniwersytet im. Adama Mickiewicza
Pozna« 2007
4
Zależności rekurencyjne
Wiele zale»no±ci kombinatorycznych mo»na wyrazi¢ prosto w postaci równa« rekurencyjnych.
Typowym przypadkiem jest, gdy rozwi¡zanie danego problemu mo»emy sprowadzi¢ do rozwi¡za«
mniejszych problemów tego samego typu.
4.1. Proste zale»no±ci rekurencyjne
Przykªad 4.1. Wyznaczy¢ przy pomocy zale»no±ci rekurencyjnej liczb¦ wszystkich permutacji
zbioru {1, 2, ..., n}.
Przykªad 4.2. Na ile spójnych obszarów dzieli pªaszczyzn¦ n prostych, z których »adne dwie nie
s¡ równolegªe i »adne trzy nie przecinaj¡ si¦ w jednym punkcie?
4.2. Jednorodne zale»no±ci rekurencyjne
Zajmiemy si¦ teraz rozwi¡zywaniem tak zwanych jednorodnych (liniowych) równa« rekurencyj-
nych. S¡ one postaci
a
n
= c
1
a
n−1
+ c
2
a
n−2
+ . . . + c
r
a
n−r
,
(4.1)
gdzie c
i
, i = 1, 2, . . . , r, s¡ zadanymi staªymi (niezale»nymi od n) i c
r
6= 0
. Powy»sza zale»no±¢ ma
gª¦boko±¢ r wi¦c, jak za chwil¦ poka»emy, aby j¡ rozwi¡za¢ musimy mie¢ zadanych r warunków
pocz¡tkowych. Zauwa»my, »e to równanie ma zawsze rozwi¡zanie trywialne a
n
= 0
, dla ka»dego
n ∈ N
. Ci¡g a
n
speªniaj¡cy (4.1), taki »e a
k
6= 0
dla pewnego k ∈ N, nazywamy rozwi¡zaniem
nietrywialnym.
Przykªad 4.3. Udowodni¢, »e je»eli ci¡gi a
0
n
i a
00
n
speªniaj¡ równanie rekurencyjne (4.1), a c jest
dowoln¡ staª¡, to ci¡gi a
0
n
+ a
00
n
oraz ca
0
n
speªniaj¡ tak»e to równanie.
Bezpo±redni¡ konsekwencj¡ powy»szego przykªadu jest fakt, i» kombinacja liniowa dwóch (sko«-
czonej liczby) rozwi¡za« jednorodnego liniowego równania rekurencyjnego jest równie» rozwi¡-
zaniem tego równania.
Z ka»dym jednorodnym równaniem rekurencyjnym (4.1) zwi¡zane jest równanie algebraiczne
x
r
− c
1
x
r−1
− c
2
x
r−2
− . . . − c
r
= 0 ,
(4.2)
zwane jego równaniem charakterystycznym. Równanie (4.2) mo»emy otrzyma¢ z (4.1) poprzez
zamian¦ a
k
na x
k
, a nast¦pnie podzielenie przez najmniejsz¡ pot¦g¦ x. Jak zobaczymy w dalszej
cz¦±ci, rozwi¡zanie ogólne zale»no±ci (4.1) zale»y od pierwiastków równania charakterystycz-
nego (4.2) w zbiorze liczb zespolonych C.
Przykªad 4.4. Udowodni¢, »e ci¡g a
n
= α
n
jest nietrywialnym rozwi¡zaniem równania rekuren-
cyjnego (4.1) wtedy i tylko wtedy, gdy α jest pierwiastkiem równania charakterystycznego (4.2).
20
4. Zale»no±ci rekurencyjne
Przykªad 4.5. Udowodni¢, »e je»eli α jest k-krotnym pierwiastkiem równania charakterystycz-
nego (4.2), to ci¡g a
n
= n
i
α
n
jest nietrywialnym rozwi¡zaniem równania rekurencyjnego (4.1),
dla i = 0, 1, . . . k − 1.
W szczególnym przypadku, gdy zale»no±¢ rekurencyjna (4.1) ma gª¦boko±¢ dwa, to równanie
charakterystyczne jest równaniem kwadratowym, zatem mo»emy sformuªowa¢ nast¦puj¡cy fakt.
Lemat 4.1. Je»eli α i β s¡ ró»nymi (nie koniecznie rzeczywistymi) pierwiastkami równania
charakterystycznego
x
2
= Ax + B ,
to równanie rekurencyjne
a
n
= Aa
n−1
+ Ba
n−2
ma rozwi¡zanie ogólne postaci
a
n
= C
1
α
n
+ C
2
β
n
.
(4.3)
W przypadku, gdy α = β, to rozwi¡zanie ogólne ma posta¢
a
n
= (C
1
+ C
2
n)α
n
.
(4.4)
Staªe C
1
oraz C
2
wyst¦puj¡ce powy»ej zale»¡ od warunków pocz¡tkowych naªo»onych na równanie
rekurencyjne.
Zauwa»my, »e w powy»szym przypadku potrzebne s¡ nam dwa warunki pocz¡tkowe, które
dadz¡ ukªad dwóch równa« z dwiema niewiadomymi C
1
i C
2
.
Przykªad 4.6. B¦dziemy mówili, »e rozwi¡zuj¡cy pewien problem student jest na n-tym etapie
je»eli do rozwi¡zania problemu pozostaªo mu n (n > 1) kroków. Na ka»dym etapie ma on pi¦¢
mo»liwo±ci. Dwie z nich prowadz¡ go z n-tego etapu do (n−1)-go etapu, a pozostaªe trzy prowadz¡
go bezpo±rednio do (n − 2)-go etapu. Niech a
n
oznacza liczb¦ sposobów rozwi¡zania problemu
zaczynaj¡c od n-tego etapu. Przyjmuj¡c, »e a
1
= 5
oraz a
2
= 13
wyznaczy¢ wzór na a
n
.
Przykªad 4.7. Rozwi¡za¢ równanie rekurencyjne
a
n
= −6a
n−1
− 9a
n−2
,
z warunkami pocz¡tkowymi a
0
= 1
, a
1
= −9
.
Przykªad 4.8. Ile jest ró»nych sposobów wej±cia po schodach zbudowanych z n stopni, je±li w
ka»dym kroku mo»na pokona¢ jeden lub dwa stopnie?
a
n
= a
n−1
+ a
n−2
, n > 2 ,
a
0
= 1
i a
1
= 1.
(4.5)
Zale»no±¢ rekurencyjna (4.5) nazywa si¦ równaniem Fibonacciego a ci¡g liczb 1, 1, 2, 3, 5, 8, 13, 21,...
nosi nazw¦ ci¡gu Fibonacciego .
Przykªad 4.10. Wyznaczy¢ liczby Lucasa L
n
okre±lone wzorem
L
n
= F
n+1
+ F
n−1
,
gdzie F
k
oznacza liczb¦ Fibonacciego z dodatkowym zaªo»eniem F
0
= 0
.
Przykªad 4.11. Niech b
n
oznacza liczb¦ n-elementowych ci¡gów o elementach ze zbioru {0, 1, 2}
takich, »e »adne dwie po sobie nast¦puj¡ce jedynki ani »adne dwie po sobie nast¦puj¡ce dwójki
nie s¡ dozwolone. Wyznaczy¢ wzór na b
n
.
Lemat 4.1 jest szczególnym przypadkiem nast¦puj¡cego twierdzenia.
4.3. Niejednorodne liniowe zale»no±ci rekurencyjne
21
Twierdzenie 4.2. Je»eli α
1
, α
2
, . . . , α
r
s¡ ró»nymi (nie koniecznie rzeczywistymi) pierwiastkami
równania charakterystycznego
x
r
− c
1
x
r−1
− c
2
x
r−2
− . . . − c
r
= 0 ,
to równanie rekurencyjne
a
n
= c
1
a
n−1
+ c
2
a
n−2
+ . . . + c
r
a
n−r
,
ma rozwi¡zanie postaci
a
n
= C
1
α
n
1
+ C
2
α
n
2
+ . . . + C
r
α
n
r
.
Ogólnie, je»eli
x
r
− c
1
x
r−1
− c
2
x
r−2
− . . . − c
r
= (x − α
1
)
m
1
(x − α
2
)
m
2
· . . . · (x − α
k
)
m
k
,
gdzie m
i
> 1
, i = 1, 2, . . . , k oraz m
1
+m
2
+. . .+m
k
= r
(tzn. α
i
jest m
i
-krotnym pierwiastkiem
równania charakterystycznego), to
a
n
=
¡
C
1
+ C
2
n + . . . + C
m
1
n
m
1
−1
¢
α
n
1
+
¡
D
1
+ D
2
n + . . . + D
m
2
n
m
2
−1
¢
α
n
2
...
+
¡
Z
1
+ Z
2
n + . . . + Z
m
k
n
m
k
−1
¢
α
n
k
.
Staªe wyst¦puj¡ce powy»ej zale»¡ od warunków pocz¡tkowych naªo»onych na równanie rekuren-
cyjne.
Przykªad 4.12. Przypu±¢my, »e pewien prymitywny organizm osi¡ga dojrzaªo±¢ po dwóch go-
dzinach i ma wtedy pierwszych czterech potomków a nast¦pnie ju» co godzin¦ ma sze±ciu kolej-
nych potomków. Zakªadaj¡c, »e wszystkie urodzone organizmy zachowuj¡ si¦ tak samo oraz, »e
rozpoczynali±my z jednym nowourodzonym organizmem, znale¹¢ zale»no±¢ rekurencyjn¡ dla a
n
liczby organizmów po n godzinach.
Przykªad 4.13. Rozwi¡» równanie rekurencyjne
a
n
= 2a
n−1
+ 15a
n−2
+ 4a
n−3
− 20a
n−4
,
z warunkami pocz¡tkowymi
a
0
= 6,
a
1
= 3,
a
2
= 71,
a
3
= 203 .
4.3. Niejednorodne liniowe zale»no±ci rekurencyjne
Niejednorodnym liniowym równaniem rekurencyjnym nazywamy równanie postaci
a
n
= c
1
a
n−1
+ c
2
a
n−2
+ · · · + c
r
a
n−r
+ f (n).
(4.6)
Funkcj¦ f(n) wyst¦puj¡c¡ w tym równaniu nazywamy wyrazem wolnym. Rozwi¡zanie ogólne tej
zale»no±ci jest postaci
a
n
= a
(1)
n
+ a
(2)
n
,
gdzie a
(1)
n
jest rozwi¡zaniem ogólnym równania jednorodnego
a
(1)
n
= c
1
a
(1)
n−1
+ c
2
a
(1)
n−2
+ · · · + c
r
a
(1)
n−r
,
(4.7)
które wyznaczamy zgodnie z zasadami poznanymi w poprzednim paragrae.
22
4. Zale»no±ci rekurencyjne
Natomiast a
(2)
n
jest dowolnym szczególnym rozwi¡zaniem równania niejednorodnego (4.6).
Niestety, nie ma ogólnej metody znajdowania tego rozwi¡zania szczególnego. W dalszej cz¦±ci
tego paragrafu, b¦dziemy wykorzystywa¢ metod¦ przewidywania rozwi¡zania. Polega ona na tym,
»e w zale»no±ci od postaci wyrazu wolnego, mo»emy odgadn¡¢ posta¢ rozwi¡zania. Najwa»niejsze
przypadki, to
1
◦
Je»eli wyraz wolny f(n) jest wielomianem (zmiennej n) stopnia d oraz rozwi¡zanie ogólne
równania jednorodnego a
(2)
n
nie jest wielomianem, to istnieje rozwi¡zanie szczególne, które
jest równie» wielomianem stopnia d, czyli zakªadamy, »e
a
(2)
n
= C
d
n
d
+ C
d−1
n
d−1
+ · · · + C
0
.
2
◦
Je»eli f(n) jest wielomianem (zmiennej n) stopnia d oraz a
(2)
n
jest wielomianem stopnia k,
to przewidujemy rozwi¡zanie szczególne postaci
a
(2)
n
= n
k+1
(C
d
n
d
+ C
d−1
n
d−1
+ · · · + C
0
).
3
◦
Je»eli f(n) jest funkcj¡ wykªadnicz¡ postaci f(n) = Cβ
n
i β nie jest pierwiastkiem rów-
nania charakterystycznego, to przewidywane rozwi¡zanie szczególne jest równie» funkcj¡
wykªadnicz¡ postaci a
(2)
n
= Aβ
n
.
4
◦
Je»eli f(n) jest funkcj¡ wykªadnicz¡ postaci f(n) = Cβ
n
i β jest pierwiastkiem równania
charakterystycznego o krotno±ci k, to przewidywane rozwi¡zanie szczególne jest równie»
funkcj¡ wykªadnicz¡ postaci a
(2)
n
= An
k
β
n
.
5
◦
Je»eli natomiast wyraz wolny f(n) jest sum¡ pewnych funkcji (zmiennej n), to przewi-
dywane rozwi¡zanie szczególne jest sum¡ przewidywanych rozwi¡za« dla poszczególnych
skªadników.
Zwró¢my uwag¦, »e staª¡ mo»emy interpretowa¢ jako wielomian stopnia zero lub jako funkcj¦
wykªadnicz¡ o podstawie 1.
Przykªad 4.16. Rozwi¡za¢ równanie rekurencyjne
a
n
= 7a
n−1
− 10a
n−2
+ 3
n
z warunkami pocz¡tkowymi a
0
= 0
i a
1
= 1
.
Przykªad 4.17. Znale¹¢ rozwi¡zanie ogólne równania rekurencyjnego
a
n
= 3a
n−1
− 2a
n−2
+ 2
n
.
Przykªad 4.18. Znale¹¢ rozwi¡zanie ogólne równania rekurencyjnego
a
n
= 2a
n−1
+ 7n
2
.
Przykªad 4.19. Korzystaj¡c z faktu, »e liczba podziaªów zbioru {1, 2, . . . , n} na dwa niepuste
zbiory równa jest 2
n−1
− 1
(patrz Przykªad ??) pokaza¢, »e a
n
okre±laj¡ce liczb¦ podziaªów zbioru
{1, 2, . . . , n}
na trzy niepuste zbiory, speªnia dla n > 1 zale»no±¢
a
n
=
1
6
3
n
−
1
2
2
n
+
1
2
.
Na zako«czenie tego paragrafu zwró¢my uwag¦, »e równania tu prezentowane mo»na rów-
nie» rozwi¡za¢ innymi metodami, np. wykorzystuj¡c aparat funkcji tworz¡cych (patrz nast¦pny
rozdziaª).
4.4. Zªo»one zale»no±ci rekurencyjne
23
4.4. Zªo»one zale»no±ci rekurencyjne
W paragrae tym przedstawimy przykªady nieliniowych równa« rekurencyjnych oraz sposoby ich
rozwi¡zywania. Zwró¢my uwag¦, »e nie ma ogólnego sposobu rozwi¡zywania wszystkich zale»no-
±ci rekurencyjnych.
Przykªad 4.20. Niech D
n
b¦dzie liczb¡ permutacji rz¦du n bez punktów staªych (nieporz¡dków).
Znale¹¢ równanie rekurencyjne dla ci¡gu D
n
.
Przykªad 4.21. Niech B
n
oznacza liczb¡ wszystkich podziaªów zbioru mocy n na rozª¡czne i
niepuste podzbiory, których kolejno±¢ nie jest wa»na. Liczby B
n
s¡ znane w kombinatoryce jako
liczby Bella. Wyznaczy¢ równanie rekurencyjne na B
n+1
.
Jednym, ze sposobów rozwi¡zywania zªo»onych zale»no±ci rekurencyjnych jest metoda pod-
stawiania nowych zmiennych i sprowadzania równania do znanej postaci.
Przykªad 4.22. Rozwi¡za¢ zale»no±¢ rekurencyjn¡
a
2
n
= 2a
2
n−1
+ 1
z warunkiem pocz¡tkowym a
0
= 2
i zaªo»eniem, »e a
n
> 0
dla ka»dego n naturalnego.
Przykªad 4.23. Rozwi¡za¢ zale»no±¢ rekurencyjn¡
a
2
n
− 2a
n−1
= 0
z warunkiem pocz¡tkowym a
0
= 4
i zaªo»eniem, »e a
n
> 0
dla ka»dego n naturalnego.
Przykªad 4.24. Rozwi¡za¢ zale»no±¢ rekurencyjn¡
a
n
=
v
u
u
t
a
n−1
+
s
a
n−2
+
r
a
n−3
+
q
. . .
√
a
0
(4.8)
z warunkiem pocz¡tkowym a
0
= 4
.
Przykªad 4.25. Niech
©
n
k
ª
oznacza liczb¦ podziaªów zbioru n-elementowego na k niepustych
i rozª¡cznych podzbiorów. Liczby te s¡ znane jako liczby Stirlinga drugiego rodzaju i s¡ okre±lone
dla n, k > 0. Znale¹¢ zale»no±¢ rekurencyjn¡ i warunki pocz¡tkowe dla liczb Stirlinga drugiego
rodzaju.
Oczywi±cie, bezpo±rednio z denicji zachodzi
n
X
k=0
n n
k
o
= B
n
,
(4.9)
gdzie B
n
jest liczb¡ Bella.
Istniej¡ równie» liczby Stirlinga pierwszego rodzaju. Oznaczamy je
£
n
k
¤
i speªniaj¡ one równanie
rekurencyjne
·
n
k
¸
=
·
n − 1
k − 1
¸
+ (n − 1)
·
n − 1
k
¸
.
Przykªad 4.26. Wyznaczy¢ liczb¦ suriekcji zdeniowanych na zbiorze [n] i o warto±ciach w
zbiorze [k].
Przykªad 4.27. Udowodni¢, »e
x
n
=
n
X
k=0
n n
k
o
(x)
k
.
(4.10)
24
4. Zale»no±ci rekurencyjne
Zale»no±ci rekurencyjne znajduj¡ mi¦dzy innymi zastosowanie przy rozwi¡zywaniu z wyko-
rzystaniem komputerów zada« numerycznych, które polegaj¡ na obliczaniu wielko±ci zdeniowa-
nych za pomoc¡ zale»no±ci matematycznych. Jako pierwszy przykªad opiszemy pewien sposób
obliczania warto±ci wielomianu dla danego argumentu.
Przykªad 4.28. Obliczy¢ warto±¢ wielomianu
w
n
(x) = a
0
x
n
+ a
1
x
n−1
+ . . . + a
n−1
x + a
n
(4.11)
dla ustalonej warto±ci argumentu x = z.
Przykªad 4.29. Zadanie polega na wyznaczeniu przybli»enia pierwiastka równania f(x) = 0,
gdzie f(x) jest zadan¡ funkcj¡.
4.5. Zadania
Zadanie 4.1. Znale¹¢ i udowodni¢ wzór na wyraz ogólny ci¡gu, dla którego zachodzi nast¦puj¡ce
równanie rekurencyjne
a
n
= n
2
a
n−1
przy zaªo»eniu, »e a
1
= 1
.
Zadanie 4.2. Ka»dego roku pewna populacja królików podwaja si¦. Je»eli pocz¡tkowo byªo
sze±¢ królików, to ile ich b¦dzie po n latach?
Zadanie 4.3. Niech b
n
oznacza liczb¦ takich n-elementowych ci¡gów binarnych, »e »adne dwa
po sobie nast¦puj¡ce 0 nie s¡ dozwolone. Znale¹¢ zale»no±¢ rekurencyjn¡ dla b
n
.
Zadanie 4.4. Niech h(k, n) b¦dzie liczb¡ rozsadze« w okre±lonym porz¡dku k pacjentów w
poczekalni, w której jest n krzeseª, tak aby »aden pacjent nie siedziaª bezpo±rednio obok drugiego.
Znale¹¢ zale»no±¢ rekurencyjn¡ dla h(k, n).
Zadanie 4.5. Niech p
n
b¦dzie liczb¡ podziaªów zbioru {1, 2, . . . , n} na dwa niepuste zbiory?
Znale¹¢ zale»no±¢ rekurencyjn¡ dla p
n
i na jej podstawie wyznaczy¢ wzór na liczb¦ takich po-
dziaªów.
Zadanie 4.6. Niech s
n
b¦dzie liczb¡ podzbiorów zbioru {1, 2, . . . , n}, wliczaj¡c zbiór pusty,
które nie zawieraj¡ s¡siednich liczb ? Znale¹¢ zale»no±¢ rekurencyjn¡ dla s
n
i na jej podstawie
wyznaczy¢ wzór na liczb¦ takich podzbiorów.
Zadanie 4.7. Przypu±¢my, »e dowolna nowourodzona para królików ma swoj¡ pierwsz¡ par¦
potomstwa po dwóch miesi¡cach, a pó¹niej ju» co miesi¡c rodzi now¡ par¦. Zakªadaj¡c, »e za-
czynamy od jednej pary, znale¹¢ zale»no±¢ rekurencyjn¡ dla k
n
- liczby par po n miesi¡cach.
Zadanie 4.8. Rozwi¡za¢ równania rekurencyjne:
(a) a
n
= 2a
n−1
+ 3a
n−2
, a
0
= a
1
= 1
.
(b) a
n
= 2a
n−1
− a
n−2
, a
0
= a
1
= 2
.
(c) Korzystaj¡c z faktu, »e
(x − 2)
2
(x + 1)(x − 3) = x
4
− 6x
3
+ 9x
2
+ 4x − 12
poda¢ wzór na wyraz ogólny ci¡gu, dla którego zachodzi nast¦puj¡ce równanie rekurencyjne
a
n
= 6a
n−1
− 9a
n−2
− 4a
n−3
+ 12a
n−4
.
4.5. Zadania
25
Zadanie 4.9. Stosuj¡c równanie charakterystyczne rozwi¡za¢ zale»no±¢ rekurencyjn¡
a
n
= a
n−1
+ 6a
n−2
z warunkami pocz¡tkowymi a
0
= 4
, a
1
= 4
.
Zadanie 4.10. Rozwi¡za¢ równania rekurencyjne:
(a) a
n
+ 6a
n−1
+ 9a
n−2
= 3
, a
0
= 0
, a
1
= 1
.
(b) a
n
= 4a
n−1
− 4a
n−2
+ 2
n
, a
0
= a
1
= 2
.
(c) a
n
= a
n−1
+ 7n
, a
0
= 0
.
Zadanie 4.11. Rozwi¡za¢ równanie rekurencyjne
a
n
+ 5a
n−1
+ 6a
n−2
= 3n
2
,
z warunkiem pocz¡tkowym a
0
= 1
, a
1
= 4
.
Zadanie 4.12. Rozwi¡za¢ nast¦puj¡ce liniowe równania rekurencyjne
(a) a
n+1
= 2a
n
− 1
, gdzie a
0
= 3
,
(b) a
n
= 6a
n−1
− 9a
n−2
, gdzie a
0
= 1
i a
1
= 2
,
(c) a
n
= 3a
n−1
+ 3
n
, gdzie a
0
= 2
,
(d) a
n
= a
n−1
+ n
3
, gdzie a
0
= 0
,
(e) a
n
= 3a
n−1
− 4n
, gdzie a
0
= 2
,
(f) a
n
= 5a
n−1
− 6a
n−2
, gdzie a
0
= 2
,
(g) a
n
= 3a
n−1
+ 3
n
, gdzie a
0
= 2
i a
1
= 1
.
Zadanie 4.13. Znajd¹ rozwi¡zanie ogólne nast¦puj¡cych liniowych równa« rekurencyjnych
(a) a
n+2
= 4a
n
,
(b) a
n+2
+ 4a
n+1
+ 16a
n
= 0
.
Zadanie 4.14. Dane jest równanie charakterystyczne
x
4
− 5x
3
+ 6x
2
+ 4x − 8 = 0
pewnego liniowego równania rekurencyjnego z warunkami pocz¡tkowymi a
0
= 1
, a
1
= −9
,
a
2
= −1
i a
3
= 2
. Wyznaczy¢ a
n
.
Zadanie 4.15. Rozwi¡za¢ równanie rekurencyjne
a
n
+ 3a
n−1
+ 2a
n−2
= f (n),
gdzie
f (n) =
(
1,
dla n = 5,
0,
dla n 6= 5,
z warunkiem pocz¡tkowym a
0
= a
1
= 0
.
Zadanie 4.16. Niech a
n
oznacza liczb¦ rozª¡cznych cz¦±ci na jakie dziel¡ n-k¡t wypukªy jego
przek¡tne. Zakªadamy, »e »adne 3 przek¡tne nie przecinaj¡ si¦ w jednym punkcie.
(a) Poka», »e
a
n
= a
n−1
+
(n − 1)(n − 2)(n − 3)
6
+ n − 2
dla n > 3
oraz a
0
= a
1
= a
2
= 0
.
(b) Wyznacz a
n
.
26
4. Zale»no±ci rekurencyjne
Zadanie 4.17. Rozwi¡za¢ równanie rekurencyjne
na
n
+ na
n−1
− a
n−1
= 2
n
z warunkiem pocz¡tkowym a
0
= 3 456
.
Zadanie 4.18. Rozwi¡za¢ równanie rekurencyjne
a
n
= na
n−1
+ n!
z warunkiem pocz¡tkowym a
0
= 2
.
Zadanie 4.19. Znale¹¢ warto±¢ wielomianu
w
n
(x) = 9x
5
+ 8x
4
+ 7x
3
+ 6x
2
+ 5x + 4
dla x = 7 korzystaj¡c ze schematu Hornera.
Zadanie 4.20. Korzystaj¡c z metody Newtona znale¹¢ z dokªadno±ci¡ do 10
−6
pierwiastek
równania
e
−x
= x
Zadanie 4.21. Udowodni¢, »e dla liczb Fibonacciego speªnione s¡ to»samo±ci
(a) F
1
+ F
2
+ · · · + F
n
= F
n+2
− 1
,
(b) F
1
+ F
3
+ · · · + F
2n−1
= F
2n
,
(c) F
2
+ F
4
+ · · · + F
2n
= F
2n+1
− 1
,
(d) F
2
1
+ F
2
2
+ · · · + F
2
n
= F
n
F
n+1
.
Zadanie 4.22. Udowodni¢, »e liczby Fibonacciego speªniaj¡ to»samo±¢
F
n+1
F
n−1
− F
2
n
= (−1)
n
,
(4.12)
znan¡ jako równo±¢ Cassiniego.
Zadanie 4.23. Udowodni¢, »e dla liczb Lucasa speªnione s¡ równania
(a) L
0
+ L
1
+ L
2
+ · · · + L
n
= L
n+2
− 1
,
(b) L
1
+ L
3
+ L
5
+ · · · + L
2n+1
= L
2n+2
− 2
.