Algorytmy rekurencyjne w połączeniu ze strukturami grafowymi doskonale nadają się do reprezentacji wielu

problemów, z którymi możemy spotkać się na co dzień. Analiza efektywności i poprawności rekurencji wraz
umiejętnością prawidłowego jej wykorzystania jest elementem bardzo istotnym w dzisiejszej sztuce programowania.

Rekurencje liniowe

Rozważmy następujące równanie rekurencyjne

(

)

1

1

,

,...,

n k

n

n

n k

f

G f

f

f

+

−

+ −

=

(1)

gdzie

G jest daną funkcją f

n

, f

n+1

,…,

f

n+k-1

, przy czym

f

n

jest funkcją niewiadomą, określoną na zbiorze liczb

naturalnych. Liczbę

k nazywamy rzędem równania rekurencyjnego.

W przypadku gdy

G jest funkcją liniową swych argumentów, tj.

1

1

2

2

...

n k

n k

n l

k

n

n

f

a f

a f

a f

b

+

+ −

+ −

=

+

+ +

+

(2)

równanie jest liniowe, przy czym, gdy współczynniki rzeczywiste a

i

, b

i

(i=1, 2,

…, k) nie zależą od n, to

równanie (2) jest równaniem rekurencyjnym liniowym o stałych współczynnikach, w p.p. równaniem
rekurencyjnym liniowym o współczynnikach zmiennych.

Ponadto w zależności od tego czy w równaniu (2) b

n

= 0 lub b

n

≠

0 równanie rekurencyjne (2) jest

jednorodne lub niejednorodne.

Dla jednoznacznego wyznaczenia funkcji f

n

, określonej przez równanie rekurencyjne, potrzebne są jej

wartości początkowe, przy czym tyle wartości początkowych, ile wynosi rząd równania rekurencyjnego.
Równanie rekurencyjne (1) jest rozwiązane wtedy, gdy dany jest wzór postaci:

(

)

1

2

,

,

,...,

n

k

f

n f

f

f

= ϕ

(3)

gdzie

1

2

,

,...,

k

f

f

f

oznaczają warunki początkowe równania (1). Zauważmy, że rozwiązanie równania w

postaci (3) pozwala obliczyć f

n

dla dowolnego n, bez konieczności wyznaczania wszystkich f

i

dla i < n.

Równanie rekurencyjne ma nieskończenie wiele rozwiązań. Możemy je zapisać w postaci ogólnej,
obejmującej wszystkie rozwiązania szczególne danego równania (w zależności od warunków początkowych

1

2

,

,...,

).

k

f

f

f

Wówczas takie rozwiązanie ogólne równania rekurencyjnego ma tyle stałych dowolnych, ile

wynosi jego rząd.

Podsumowując, rozwiązanie równania rekurencyjnego polega bądź na znalezieniu rozwiązania ogólnego,
bądź w przypadku gdy dane są wartości początkowe równania szukamy rozwiązania szczególnego.

Rozwiązywanie jednorodnych równań rekurencyjnych liniowych o stałych

współczynnikach

Niech będzie dane jednorodne równanie rekurencyjne liniowe rzędu k

1

1

2

2

...

n k

n k

n k

k

n

f

a f

a f

a f

+

+ −

+ −

=

+

+ +

(4)

w którym

1

2

,

,...,

k

a a

a są współczynnikami rzeczywistymi niezależnymi od n, przy czym a

k

≠

0. Jest to

równanie rzędu k, a więc dla jego jednoznacznego rozwiązania potrzeba, aby były dane wartości początkowe

1

2

,

,...,

.

k

f

f

f

Dla rozwiązania równania (4) wprowadza się pewną funkcję pomocniczą p(z) zwaną wielomianem
charakterystycznym równania. Funkcja p(z) zmiennej zespolonej z jest określona jako wielomian tego
samego stopnia k co dane równanie (4) jest rzędu, i którego współczynnikami są te same współczynniki a

i

,

występujące w równaniu (4). Zatem

( )

1

2

1

2

1

...

k

k

k

k

k

p z

z

a z

a z

a

z

a

−

−

−

=

−

−

− −

−

(5)

Równanie

( )

0

p z

=

(6)

z kolei nazywamy równaniem charakterystycznym, a jego pierwiastki (rzeczywiste lub zespolone, których
liczba wraz z ich krotnościami wynosi k) – pierwiastkami charakterystycznymi.

Niech

1

2

,

,..., ,

r

z z

z

r

k

≤

oznaczają różne pierwiastki charakterystyczne o krotnościach równych

odpowiednio

1

2

, ,...,

r

v v

v tak, że

1

.

r

i

i

v

k

=

=

∑

Wówczas

( )

(

)

1

i

r

v

i

i

p z

z

z

=

=

−

∏

(7)

Ogólnym rozwiązaniem równania (4) o współczynnikach rzeczywistych

1

2

,

,...,

k

a a

a niezależnych od n oraz

a

k

≠

0 jest

1

1

0

i

v

r

n

m

n

s

sm

s

m

f

z

C n

−

=

=

=

∑ ∑

(8)

gdzie z

s

(s = 1,

…,r) jest pierwiastkiem charakterystycznym równania o krotności v

i

, C

sm

(s = 1,

…,r;

m

= 0,1,

…,v

i

-1) jest dowolną stałą.

W przypadku gdy wszystkie pierwiastki charakterystyczne z

i

są pojedyncze, tj. równanie (6) ma k

pierwiastków z

i

o krotnościach

v

i

= 1 (i = 1,

…,k), rozwiązanie (8) przyjmuje uproszczoną postać

1

k

n

n

s

s

s

f

z C

=

=

∑

(9)

gdzie C

s

(s = 1,

…,k) są dowolnymi stałymi wyznaczanymi z warunków początkowych.

Dla otrzymania rozwiązania szczególnego wzoru (4) o warunkach początkowych

1

2

,

,...,

k

f f

f

należy

najpierw rozwiązać równanie charakterystyczne, zapisać postać ogólną rozwiązania (8) bądź (9) zależnie od
pierwiastków, a następnie rozwiązać układ k równań liniowych względem k niewiadomych, którymi są C

10

,

C

11

,

…, C

r,v

-1

1

2

1

2

1

1

1

1

1

1

2

2

1

1

0

0

0

1

1

1

2

2

2

1

1

2

2

2

0

0

0

1

1

1

0

...

2

2

...

2

.............................................................................

r

r

v

v

v

m

m

r

m

m

m

m

v

v

v

m

m

m

m

m

r

rm

m

m

m

v

k

m

m

m

z

C

z

C

z

C

f

z

C

z

C

z

C

f

z

C k

z

−

−

−

=

=

=

−

−

−

=

=

=

−

=

+

+ +

=

+

+ +

=

+

∑

∑

∑

∑

∑

∑

∑

2

1

1

2

2

0

0

...

r

v

v

k

m

k

m

m

r

rm

k

m

m

C k

z

C k

f

−

−

=

=

+ +

=

∑

∑

(10)

Obliczone wartości wstawiamy do wzoru (8) uzyskując w ten sposób szukane rozwiązanie szczególne
danego równania.

U

WAGA

Jeżeli współczynniki równania charakterystycznego

( )

0

p z

=

są liczbami rzeczywistymi, to

równanie, jeśli ma pierwiastki zespolone, to są one parami sprzężone.

Rozwiązywanie niejednorodnych równań rekurencyjnych liniowych o stałych

współczynnikach

Niech będzie dane niejednorodne równanie rekurencyjne liniowe rzędu k

1

1

2

2

...

n k

n k

n k

k

n

f

a f

a f

a f

b

+

+ −

+ −

=

+

+ +

+

(11)

W którym

1

2

,

,...,

,

k

a a

a b są współczynnikami rzeczywistymi niezależnymi od n, przy czym a

k

≠

0 oraz b ≠ 0.

Jest to równanie rzędu k, a więc dla jego jednoznacznego rozwiązania potrzeba, aby były dane wartości
początkowe

1

2

,

,...,

.

k

f

f

f

Równanie jednorodne, które otrzymujemy z danego równania (4) przez przyjęcie b = 0, nosi nazwę równania
uzupełniającego to równanie i ma postać

1

1

2

2

...

n k

n k

n k

k

n

f

a f

a f

a f

+

+ −

+ −

=

+

+ +

(12)

Wielomianem charakterystycznym równania uzupełniającego jest

( )

1

2

1

2

1

...

k

k

k

k

k

p z

z

a z

a z

a

z

a

−

−

−

=

−

−

− −

−

(13)

Napiszmy teraz (12) zastępując n → n+1

1

1

2

1

1

2

1

...

n k

n k

n k

k

n

k

n

f

a f

a f

a

f

a f

b

+ +

+

+ −

−

+

+

=

+

+ +

+

+

(14)

Odejmując stronami (11) i (14) otrzymamy równanie jednorodne rzędu k+1

(

)

(

)

(

)

1

1

1

2

1

1

1

1

...

0

n k

n k

n k

k

k

n

k

n

f

a

f

a

a

f

a

a

f

a f

+ +

+

+ −

−

+

− +

+

−

+ +

−

+

=

(15)

o równaniu charakterystycznym

(

)

(

)

(

)

1

1

1

1

2

1

1

...

0

k

k

k

k

k

k

z

a z

a

a z

a

a

z

a

+

−

−

− +

+

−

+ +

−

+

=

(16)

Ostatnie równanie można zapisać jako

( )(

)

1

0

p z z

− =

(17)

Z drugiej strony wydzielając czynnik związany z ewentualnym pierwiastkiem z = 1

i

wielomianu

charakterystycznego

( ) (

)

( )

1

p z

z

z

α

= −

ϕ

(18)

gdzie

( )

1

0

ϕ ≠

otrzymujemy

( )(

) (

)

( )

1

1

1

p z z

z

z

α+

− = −

ϕ

(19)

Wówczas rozwiązanie ogólne równania (11) jest postaci

( )

1

!

n

n

bn

f

g

α

=

+ ϕ α

(20)

Gdzie g

n

jest rozwiązaniem ogólnym równania uzupełniającego (12),

( )

z

ϕ

zaś oraz

α

jak we wzorze (18).

i

Jeśli wielomian charakterystyczny p(z) ma pierwiastek z = 1, to a jest równe jego krotności.

Ć

WICZENIA

1)

Znaleźć rozwiązanie równania rekurencyjnego

3

2

1

6

11

6

0

n

n

n

n

f

f

f

f

+

+

+

−

+

−

=

przy warunkach początkowych

1

2

3

0,

1,

0.

f

f

f

=

=

=

R

OZWIĄZANIE

Równanie charakterystyczne jest postaci

3

2

6

11

6

0

z

z

z

−

+

− =

Pierwiastki tego równania można znaleźć korzystając z tw. Bezou

’ta zauważając, że

2

z

−

dzieli bez reszty wielomian

3

2

6

11

6.

z

z

z

−

+

−

Stąd otrzymujemy, że

(

)(

)

(

)

1

2

3

0

z

z

z

−

−

− =

A zatem pierwiastkami charakterystycznymi są

1,

2,

3, wszystkie jednokrotne.

z

z

z

=

=

=

Wobec tego rozwiązaniem ogólnym

danego równania rekurencyjnego według wzoru (9) jest

1

2

3

2

3

n

n

n

f

C

C

C

=

+

+

Dla znalezienia rozwiązani szczególnego o danych warunkach początkowych trzeba

jeszcze

rozwiązać układ równań liniowych względem

1

2

3

,

,

C C C

odpowiadający układowi

1

2

3

1

2

3

1

2

3

2

3

0

4

9

1

8

27

0

C

C

C

C

C

C

C

C

C

+

+

=

+

+

=

+

+

=

Stąd otrzymujemy

1

2

3

5

1

,

2,

.

2

2

C

C

C

= −

=

= −

Podstawiając te wartości do wzoru na

rozwiązanie ogólne uzyskujemy rozwiązanie szczególne postaci

1

5

1

2

3

2

2

n

n

n

f

+

= − +

− ⋅

2)

Znaleźć rozwiązanie równania rekurencyjnego

3

2

1

n

n

n

n

f

f

f

f

+

+

+

=

+

−

przy warunkach początkowych

1

2

3

1,

2,

3.

f

f

f

=

=

=

R

OZWIĄZANIE

Równanie charakterystyczne jest postaci

3

2

1

0

z

z

z

− − + =

czyli

(

) (

)

2

1

1

0

z

z

−

+ =

Stąd pierwiastkami charakterystycznymi są

1

1

2

2

1 o krotności

2

1 o krotności

1

z

z

=

α =

= −

α =

Rozwiązanie ogólne równania rekurencyjnego ma więc postać

( )

10

11

20

1

n

n

f

C

C n C

=

+

+

−

Współczynniki

10

11

20

,

,

C

C C

wyznaczmy z układu równań

10

11

20

10

11

20

10

11

20

1

2

2

3

3

C

C

C

C

C

C

C

C

C

+

−

=

+

+

=

+

−

=

Dostajemy

10

20

11

0,

1,

C

C

C

=

=

=

co prowadzi di rozwiązania szczególnego

.

n

f

n

=

3)

Znaleźć rozwiązanie równania rekurencyjnego

2

1

4

3

0

n

n

n

f

f

f

+

+

+

+

=

przy warunkach początkowych

1

2

1,

5

f

f

= −

=

R

OZWIĄZANIE

Równanie charakterystyczne jest postaci

2

4

3

0

z

z

+ + =

Stąd pierwiastkami charakterystycznymi są

1

1

2

2

3 o krotności

1

1 o krotności

1

z

z

= −

α =

= −

α =

Wobec tego rozwiązaniem ogólnym danego równania rekurencyjnego według wzoru

(9) jest

( )

( )

1

2

3

1

n

n

n

f

C

C

= −

+ −

Dla znalezienia rozwiązani szczególnego o danych warunkach początkowych trzeba

jeszcze

rozwiązać układ równań liniowych względem

1

2

oraz

C

C

odpowiadający

układowi

1

2

1

2

3

1

9

5

C

C

C

C

−

−

= −

+

=

Stąd otrzymujemy

1

2

2 ,

1.

3

C

C

=

= −

Podstawiając te wartości do wzoru na

rozwiązanie ogólne

uzyskujemy rozwiązanie szczególne postaci

( )

( )

1

1

2

3

1

n

n

n

f

+

−

= ⋅ −

+ −

4)

Znaleźć rozwiązanie równania rekurencyjnego niejednorodnego

2

1

4

3

5

n

n

n

f

f

f

+

+

+

+

=

przy warunkach początkowych

1

2

1,

5

f

f

= −

=

R

OZWIĄZANIE

Rozwiązanie równania uzupełnionego już policzyliśmy

( )

( )

1

1

2

3

1

n

n

n

g

+

−

= ⋅ −

+ −

Pozostało zauważyć, że wielomian charakterystyczny równania jednorodnego nie ma

pierwiastka

1

z

=

zatem

0

α =

oraz

( )

( )

z

p z

ϕ

=

i stąd

( )

1

8

ϕ =

oraz

5.

b

=

Podstawiając

do

wzoru (20)

( )

( )

1

1

5

2

3

1

8

n

n

n

f

+

−

= ⋅ −

+ −

+

5)

Znaleźć rozwiązanie równania rekurencyjnego niejednorodnego

3

2

1

3

3

5

n

n

n

n

f

f

f

f

+

+

+

−

+

−

=

przy warunkach początkowych

1

2

3

1,

0,

1.

f

f

f

=

=

= −

R

OZWIĄZANIE

Równanie charakterystyczne równania uzupełniającego jest

(

)

3

1

0

z

−

=

Stąd

1

1

z

=

o krotności

1

3

α =

Wobec tego rozwiązaniem ogólnym danego równania według wzoru (9) przy uwzględnieniu (2)

( )

( ) (

)

(

)

3

1 bo

1

1,

5

z

p z

z

b

ϕ

=

= −

⋅

=

jest

3

2

1

2

3

5

3!

n

n

f

C

C n C n

=

+

+

+

Dla spełnienia warunków początkowych musi być

1

2

3

1

2

3

1

2

3

1
6

20

2

4

3

47

3

9

2

C

C

C

C

C

C

C

C

C

+

+

=

+

+

= −

+

+

= −

Rozwiązaniem tego układu są

1

2

3

49

3,

,

5.

6

C

C

C

= −

=

= −

Zatem rozwiązaniem równania rekurencyjnego

niejednorodnego spełniającego podane warunki początkowe jest

2

3

49

5

3

5

6

6

n

f

n

n

n

= − +

−

+

R

OZWIĄZAĆ

1)

1

2

6

9

n

n

n

a

a

a

−

−

= −

−

z warunkami początkowymi

0

1

1,

9.

a

a

=

= −

2)

2

1

n

n

n

a

a

a

+

+

=

+

z warunkami początkowymi

0

1

0,

1.

a

a

=

=

3)

2

1

5

6

n

n

n

a

a

a

+

+

=

+

z warunkami początkowymi

0

1

1,

4.

a

a

=

= −

4)

1

2

3

2

n

n

n

a

a

a

−

−

=

−

z warunkami początkowymi

1

2

2,

3.

a

a

=

=

5)

1

2

6

n

n

n

f

f

f

−

−

=

+

z warunkami początkowymi

0

1

3,

4.

f

f

=

=

6)

1

2

3

3

4

12

n

n

n

n

f

f

f

f

−

−

−

=

+

−

z warunkami początkowymi

0

1

2

1,

2,

3.

f

f

f

=

=

=

7)

2

4

2

n

n

n

f

f

f

−

−

=

−

z warunkami początkowymi

0

1

2

3

1,

1,

2,

2.

f

f

f

f

=

=

=

=

O

DPOWIEDZI

1)

( ) (

)

3

1 2

n

n

a

n

= −

+

2)

( ) ( )

1

1

5

1

5

2

2

5

n

n

n

a





+

−

=

−









3)

( )

10

3

1

6

7

7

n

n

n

a

= −

⋅

− ⋅

4)

1

2

1

n

n

a

−

=

+

5)

( )

2

2 3

n

n

n

f

= −

+ ⋅

6)

( )

1

2

3

2

2

3

n

n

n

n

f

C

C

C

=

+ −

+

7)

( )

(

)

10

11

20

21

1

n

n

f

C

C n

C

C n

=

+

+ −

+

( )

3

1

1

1

4

2

4

n

n

f

n

= +

+ ⋅ −