Page 197 - vol2

A homogén lineáris rekurzió megoldása szorosan kapcsolódik az
úgynevezett karakterisztikus egyenlethez. Ez a következő meggondolásból
adódik: az (1) egyenlet megoldását x = q alakban keressük, ahol q  1
n
n
2
+
így a rekurzió alapján eljutunk az ar + br c = 0 úgynevezett
karakterisztikus egyenlethez.
n
(I) Ha ennek különböző gyökei vannak, akkor a függvény x = n  r + 1 n  r
2
ahol az  , számokat a kezdeti x = 0 , x x = 1 y feltételekből határozzuk
meg.
(II) Ha a karakterisztikus egyenletnek dupla r = r = r gyöke akkor
1 2
x n ( r =  + ) n r n− 1 , és az ,  számokat ugyancsak a kezdeti x = 0 , x x = 1 y
feltételekből határozzuk meg.
(III) Ha a karakterisztikus egyenletnek komplex gyökei vannak, akkor
n
x =  r + n  r és ahol r = (cost i sin ) , így x = t  n ( cosnt +  sinnt )
+
n n
(v.ö. [1], 36. oldal).
Ezen információk birtokában, oldjuk meg a következő feladatokat.
Először azonban nézzük a következőket: A karakterisztikus egyenlet
alapján


2

2
+
−
A − t A dI = O  A = t A d I . Ennek alapján az is felírható, hogy
2
2
2

2
3

A = t A − d A és ha most az előbbi összefüggésből ide behelyettesítjük

+

3


−
az A = t A d I értéket, akkor egy A = x A y I alakú összefüggést
2
3
3
2
2
n
kapunk, ami azt sejteti, hogy A = x  A + y  I alakú lesz. Ezt, a
2
n
n
következő tételben fogalmazzuk meg:
a  b
Tétel: Ha A =   , t TrA= és d = det A , akkor léteznek olyan ( )
x
n n
 c d  0
és ( ) számsorozatok, amelyekre A = x  A + y  I (#) és
n
y
n n 0 n n 2




x n + 1 − t x + d x n − 1 = 0,(1) y n + 1 − t y + d y n − 1 = 0,(2) bármely n 
n
n
esetén, továbbá x = 0 0, y = 0 1 valamint x = 1 1, y = 0 0.
Bizonyítás: a (#) relációt indukcióval igazoljuk. Az n = illetve n =
0
1

+
+



esetben az I = A = x A y I illetve A = x A y I összefüggések,
0
1
2
0
2
1
0
2
1
az x = 0 0, y = 0 1 valamint x = 1 1, y = 0 0.összefüggések alapján

197