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

.