Állandó együtthatós lineáris rekurziók

1. fejezet Állandó együtthatós lineáris rekurziók 1.1. A megoldás menete. Mese. Idézzük fel a Fibonacci-számokat! Az Fn sorozatot a következő módon definiáltuk: legyen F0 = 0, F1 = 1, és Fn+2 = Fn+1 + Fn (n ≥ 0), azaz a másodiktól kezdve minden tag az őt megelőző két tag összege. Így a sorozat minden tagját kiszámíthatjuk, de nem könnyen: a századik taghoz meg kell határoznunk az összes addigi tagot is. Könnyebb a helyzetünk, ha emlékszünk a Fibonacci-számok explicit képletére, mely szerint Ãà √ !n ! √ !n à 1− 5 1+ 5 1 − Fn = √ . 2 2 5 Ebbe n = 100-at helyettesítve rögtön megkapjuk a kívánt eredményt. E fejezetben rekurzióval megadott sorozatoknak explicit képletének kiszámításával fogunk tüzetesebben foglalkozni. ♦ 1.1. definíció. Egy an (n ∈ N) sorozatra vonatkozó, an+k = c1 an+k−1 + . . . + ck an alakú képletet (homogén, k-adfokú) állandó együtthatós lineáris rekurziónak nevezünk, ahol k rögzített pozitív egész, a c1 , . . . , ck , ck 6= 0 együtthatók pedig rögzített valós számok. ♦

A fenti módon megadott sorozatban tehát minden tag megkapható az őt közvetlenül megelőző k tagból. Természetesen egy ilyen rekurzió csak akkor határozza meg a sorozat tagjait, ha az első k tagot is megadjuk. Pontosabban bármely k szomszédos tag ismerete elegendő, hiszen a rekurzió segítségével visszafelé is számolhatunk. Megjegyezzük, hogy ezen a módon a sorozat nempozitív indexű tagjai is értelmezhetők; ez néha kényelmes.

Megjegyzés. Az elnevezésben az állandó együtthatós jelző arra utal, hogy a c1 , . . . , ck együtthatók rögzítettek (azaz nem függnek n-től), míg a lineáris jelző arra, hogy az an+k t megadó jobboldali kifejezés az an+k−1 , . . . , an lineáris kombinációja. Hogy valóban kadfokú rekurzióról beszéljünk, feltesszük, hogy ck 6= 0. A homogenitás azt jelenti, hogy átrendezve az egyenletet (−1)an+k +c1 an+k−1 +. . .+ck an = 0-t kapunk. Ha a jobb oldalon nem nulla állna, inhomogén rekurziónak neveznénk. ♦ 1

2

1. FEJEZET. ÁLLANDÓ EGYÜTTHATÓS LINEÁRIS REKURZIÓK A továbbiakban a k = 2 esetet vizsgáljuk részletesebben, azaz az a1 = α, a2 = β, an+2 = c1 an+1 + c2 an

(1.1) (1.2)

alakban megadott sorozatokra keresünk explicit képletet (itt α, β, c1 , c2 rögzített valós számok). (1.1)-et kezdeti feltételek nek nevezzük, (1.2)-t pedig rekurziónak. A két feltétel együtt egyértelműen meghatározza az an sorozatot (n ≥ 1).

A módszer a következő: valahogyan keresünk két (valamilyen értelemben független) sorozatot, amelyek kielégítik (1.2)-t. Ezek várhatóan nem teljesítik a kezdeti feltételeket, viszont a segítségükkel előállítunk olyan sorozatot, ami (1.2) mellett (1.1)-et is teljesíti. A feladatunk tehát két (független) megoldást találni az (1.2) rekurzióra. Vegyük észre, hogy az azonosan nulla sorozat persze megfelel, de semmire sem megyünk vele. Az ötlet az, hogy keressünk olyan mértani sorozatot, ami kielégíti (1.2)-t. Rendhagyó módon most előre vesszük a bizonyítást, és csak utána mondjuk ki a tételt. Bizonyítás. Keressünk olyan a′n = xn−1 , x 6= 0 mértani sorozatot, ami kielégíti (1.2)-t, azaz amire teljesül, hogy xn+1 = c1 xn + c2 xn−1 . Leosztva xn−1 -nel (mivel x 6= 0, ezt minden további nélkül megtehetjük), átrendezés után egy másodfokú egyenletet nyerünk x-re, ami ekvivalens a fentivel: x2 − c1 x − c2 = 0. Ennek a gyökeit (amit a megoldóképlettel könnyen kiszámíthatunk) jelölje x1 és x2 . Persze a gyökök egyike sem nulla, hiszen feltettük, hogy c2 6= 0. Levezetésünk éppen azt mutatja, hogy a′n = x1n−1 és a′′n = x2n−1 eleget tesznek az (1.2) rekurziónak. Ha x1 = x2 , akkor a talált sorozatok egybeesnek. Szerencsére ekkor találunk más jó sorozatot: legyen a′′n = (n − 1)x1n−1 . Azt állítjuk, hogy ebben az esetben a′′n is teljesíti (1.2)-t; ehhez a′′n -et (1.2)-be helyettesítve az alábbit kell igazolnunk: (n + 1)xn+1 − c1 nxn1 − c2 (n − 1)x1n−1 = 0. 1 Leosztva x1n−1 -nel és átrendezve ez azzal ekvivalens, hogy (n − 1)(x21 − c1 x1 − c2 ) + 2x21 − c1 x1 = 0. Ebben x21 −c1 x1 −c2 = 0, hiszen x1 éppen az x2 −c1 x−c2 = 0 egyenlet megoldása; ráadásul x1 = x2 , így a megoldóképletben a diszkrimináns nulla, azaz a megoldás x1 = c1 /2, amiből 2x1 − c1 = 0 adódik1 . Ezt x1 -gyel felszorozva látjuk, hogy 2x21 − c1 x1 is egyenlő nullával, és ezzel az alábbi tétel bizonyítását befejeztük. 1.2. tétel. Legyen x1 és x2 az x2 − c1 x − c 2 = 0 1

(1.3)

Ez onnan is látható, hogy x1 kétszeres gyöke a p(x) = x2 − c1 x − c2 polinomnak, így a deriváltjának is gyöke, azaz p′ (x1 ) = 2x1 − c1 = 0.

1.1. A MEGOLDÁS MENETE.

3

egyenlet két gyöke. Ekkor a′n = x1n−1 és a′′n = x2n−1 kielégítik (1.2)-t. Ha x1 = x2 , akkor a′′n = (n − 1)x1n−1 is kielégíti (1.2)-t.

Bizonyítás. Lásd a tétel előtt.

1.3. definíció. Az (1.3) egyenletet az (1.2) lineáris rekurzió karakterisztikus egyenletének nevezzük. ♦ Megjegyzés. Előfordulhat, hogy a karakterisztikus egyenlet gyökei nem valósak, hanem komplex számok. Ez csak annyiban zavarja a megoldás menetét, amennyiben nem szeretünk komplex számokkal számolni; elvi különbséget nem okoz. ♦

Most megnézzük, hogyan lehet két, az (1.2) rekurziót kielégítő sorozatból egy harmadik, hasonló tulajdonságú sorozatot készíteni.

1.4. állítás. Legyen a′n és a′′n két sorozat, melyek kielégítik az (1.2) rekurziót. Ekkor tetszőleges λ1 és λ2 rögzített (valós vagy komplex) számokra a bn = λ1 a′n + λ2 a′′n sorozat is kielégíti az (1.2) rekurziót. Bizonyítás. A feltételünk alapján a′n+2 = c1 a′n+1 + c2 a′n és a′′n+2 = c1 a′′n+1 + c2 a′′n egyaránt teljesül. Emiatt bn+2 = λ1 a′n+2 + λ2 a′′n+2 = λ1 (c1 a′n+1 + c2 a′n ) + λ2 (c1 a′′n+1 + c2 a′′n ) = = c1 (λ1 a′n+1 + λ2 a′′n+1 ) + c2 (λ1 a′n + λ2 a′′n ) = c1 bn+1 + c2 bn is fennáll. Megjegyzés. Akik már tanultak lineáris algebrát, azok felismerhetik, hogy az előző 1.4. állítás azt mondja, hogy az (1.2) rekurziót kielégítő számsorozatok zártak a lineáris kombinációkra, azaz egy (R vagy C feletti) vektorteret alkotnak. Mivel az első két tag szabadon választható, és a sorozat további tagjait ez egyértelműen meghatározza, eme vektortér dimenziója kettő. Tehát ha találunk valahogyan két, lineárisan független megoldását (1.2)-nek, az egy bázisa lesz ennek a térnek. Azok lineáris kombinációjaként minden olyan sorozat előáll, ami kielégíti (1.2)-t, speciálisan az (1.1) kezdeti feltételeknek eleget tevő sorozat is. ♦ Megjegyzés. Az a′n = x1n−1 helyett nyugodtan vehetnénk az a′n = xn1 , illetve egybeeső gyökök esetén az a′n = (n − 1)x1n−1 helyett az a′n = nx1n−1 sorozatokat is. Ezek ugyanúgy megoldásai (1.2)-nek, ami azonnal látszik az 1.4. állításunkból: pl. xn1 = x1 · x1n−1 + 0 · x2n−1 előáll x1n−1 és x2n−1 -ből λ1 = x1 , λ2 = 0 választással. ♦ Munkánk gyümölcsét learatandó nézzük meg, hogyan kapjuk meg az an sorozat explicit képletét az eddigiek felhasználásával.

1.5. állítás. A keresett, (1.1)-nek és (1.2)-nek eleget tevő an sorozat egyértelműen előállítható λ1 a′n + λ2 a′′n alakban, ahol a′n és a′′n az 1.2. tételben kapott sorozatok. Bizonyítás. Az 1.4. állítás szerint a λ1 a′n +λ2 a′′n alakú sorozatok teljesítik az (1.2) rekurziót, tehát csak a kezdeti értékekkel kell foglalkoznunk. Ehhez úgy kell megválasztanunk λ1 -et

4

1. FEJEZET. ÁLLANDÓ EGYÜTTHATÓS LINEÁRIS REKURZIÓK

és λ2 -t (a többi paraméter ismert), hogy a1 = α = λ1 a′1 + λ2 a′′1 , és a2 = β = λ1 a′2 + λ2 a′′2 egyaránt teljesüljenek. Ha x1 6= x2 , azaz a′n = x1n−1 és a′′n = x2n−1 , ez a α = λ1 + λ 2 β = λ1 x 1 + λ 2 x 2 egyenletrendszert adja, amit a középiskolából ismert módszerekkel megoldva a λ1 = (β − αx2 )/(x1 − x2 ), λ2 = (αx1 − β)/(x1 − x2 ) megoldást kapjuk. Ha x1 = x2 , azaz a′n = x1n−1 és a′′n = (n − 1)x1n−1 , a

α = λ1 β = λ1 x 1 + λ 2 · x 1 egyenletrendszert kapjuk, amiből λ1 = α, λ2 = (β − αx1 )/x1 adódik. Megjegyzés. Láttuk, hogy mértani sorozat formájában keresni a rekurziót kielégítő sorozatokat célravezető és jól kezelhető ötlet. Ezzel együtt nem kötelező: bárhogyan is találunk két – valamilyen értelemben független – jó megoldást (akár próbálgatással), abból elő fogjuk tudni állítani a keresett sorozatot. Erről bővebben az Olvasmányban írunk. ♦ Összefoglalva a fejezet tanulságait: Egy an+2 = c1 an+1 + c2 an egyenlettel és az a1 , a2 tagokkal megadott sorozat explicit képletét megkaphatjuk az alábbi lépésekkel. 1. Keresünk megoldást csak a rekurzióra mértani sorozatként: xn+1 = c1 xn + c2 xn−1 . Átrendezve elég az x2 − c1 x − c2 = 0 egyenlet x1 és x2 gyökeit meghatároznunk. 2. Ha x1 6= x2 , akkor a megoldást an = λ1 x1n−1 + λ2 x2n−1 alakban keressük. 3. Ha x1 = x2 , akkor a megoldást an = λ1 x1n−1 + λ2 (n − 1)x1n−1 alakban keressük. 4. A λ1 és λ2 értékeket az a1 és a2 kezdeti értékekhez igazítjuk (kétismeretlenes egyenletrendszer).

1.2. Példák. Az indexeket néha szándékosan eltolva adjuk meg, ez a megoldás menetét nem befolyásolja. Példa. Adjunk explicit képletet az an = 7an−1 − 12an−2 , a1 = 1, a2 = 6 rekurzióval megadott sorozatra!

1.2. PÉLDÁK.

5

Megoldás. A karakterisztikus egyenlet x2 − 7x + 12 = 0. Ennek két gyöke x1 = 4 és x2 = 3. Ezért a megoldást an = λ1 4n−1 + λ2 3n−1 alakban keressük. A kezdeti értékek figyelembe vételével az alábbi egyenletrendszert kapjuk: (a1 =) 1 = λ1 + λ2 (a2 =) 6 = λ1 · 4 + λ2 · 3. Ezt megoldva (mondjuk λ2 = 1 − λ1 -et behelyettesítve a második egyenletbe) λ1 = 3, λ2 = −2 adódik. Tehát az explicit képlet an = 3 · 4n−1 − 2 · 3n−1 . ♦ Példa. Oldjuk meg az an+2 = 4an+1 − 4an , a1 = 2, a2 = 6 lineáris rekurziót!

Megoldás. A karakterisztikus egyenlet x2 − 4x + 4 = 0, melynek x = 2 kétszeres gyöke. Így an -et λ1 · 2n−1 + λ2 · (n − 1) · 2n−1 alakban keressük, egyenletrendszerünk pedig két egyenletből áll: (a1 =) 2 = λ1 (a2 =) 6 = 2 · λ1 + 2 · λ2 . Ennek azonnal láthatóan λ1 = 2, λ2 = 1 a megoldása, amit visszaírva an kifejezésébe kapjuk, hogy an = (n + 1)2n−1 . ♦ Példa. Oldjuk meg az an+2 = 2an+1 − 2an , a1 = 1, a2 = 2 lineáris rekurziót!

Megoldás. A karakterisztikus egyenlet x2 − 2x + 2 = 0, aminek x1 = 1 + i és x2 = 1 − i a megoldásai. A megoldást tehát an = λ1 · (1 + i)n−1 + λ2 · (1 − i)n−1 alakban keressük. A kezdeti értékekből kapott egyenletrenszer (a1 =) 1 = λ1 + λ2 (a2 =) 2 = (1 + i) · λ1 + (1 − i) · λ2 . Ismét például λ2 = 1 − λ1 -et behelyettesítve a második egyenletbe 2 = 2 · i · λ1 + 1 − i, azaz 2 · i · λ1 = 1 + i adódik, amiből λ1 =

1+i 1 + i 2i 2 − 2i −2i(1 + i) = · = = 1/2 − i/2, = 2 2i 2i −4i 4 2i

és λ2 = 1/2 + i/2 kiszámítható. Végeredményben an =

1−i 2

· (1 + i)n−1 + 1+i · (1 − i)n−1 . ♦ 2

Ugyancsak fontos, hogy felismerjük, mikor vezet egy szöveges feladat állandó együtthatós lineáris rekurzióra. Erre általános recept nincs, néhány ötletet láthatunk most. Amikor azt látjuk, hogy a feladat ugyanolyan típusú, csak valamilyen értelemben kisebb részfeladatokra vezethető vissza, próbálkozhatunk rekurzió felírásával. A rekurziókat most nem oldjuk meg (azt már gyakoroltuk), csak a rekurziók felírására koncentrálunk. Példa. Hányféleképpen mehetünk fel az n lépcsőfokból álló lépcsőn, ha egyszerre 1 vagy 2 fokot léphetünk? És ha 3-at is?

6

1. FEJEZET. ÁLLANDÓ EGYÜTTHATÓS LINEÁRIS REKURZIÓK

Megoldás. Az ötlet tipikus: diszjunkt részfeladatokra bontunk az első lépés szerint. Jelölje an a választ n lépcsőfok esetén. Ha az első lépésnél k fokot lépünk, a maradék n − k lépcsőfokon éppen an−k -féleképpen mehetünk fel. (Itt látjuk, hogy az első lépés után egy ugyanolyan jellegű feladatot kapunk.) A k lehetséges értékeit megnézve az első esetben az an = an−1 + an−2 , a másodikban az an = an−1 + an−2 + an−3 rekurziót kapjuk. Az első esetben két, a másodikban három kezdeti tagot kell meghatároznunk, hogy leírjuk a sorozatot. Ezt „kézzel” kiszámolva az első esetben a1 = 1, a2 = 2, míg a másodikban a1 = 1, a2 = 2, a3 = 4 adódik. Így kaptunk egy lineáris rekurziót kezdeti felétételekkel, amit a tanult módszerekkel meg tudunk oldani az első esetben. A másodikban a rekurzió harmadfokú. Magasabbfokú rekurziók megoldásával az Olvasmányban foglalkozunk. ♦ Megjegyzés. Formálisan n = 0 lépcsőfokra is megkérdezhetjük ugyanezt. Egyetlen olyan lépéssorozat van, amellyel nulla lépcsőfokot mászunk meg: az üres sorozat (azaz amikor nem lépünk semmit). Így az a megérzésünk támadhat, hogy a0 = 1 kell legyen mindkét esetben. A rekurzív képletek is alátámasztják ezt a megérzésünket: például az első esetben a képletet az a2 -re felírva a2 = a1 + a0 adódik, ami szintén a0 = 1-et eredményez. ♦ Példa. Hányféleképpen költhetünk el n eurót, ha 1 euróért 3-féle, 2 euróért 4-féle különböző cikket vásárolhatunk? Lényeges, hogy milyen sorrendben vásároltuk a cikkeket! (A megvásárolt cikkek száma nyilván függ attól, hogy miket vettünk; ez a feladat szempontjából azonban lényegtelen.) Megoldás. Jelölje an azt, hogy n eurót hányféleképpen költhetünk el. Megint az első vásárlás szerint bontunk szét. A különbség az, hogy most az első vásárlás többféleképpen alakulhat. Így az an = 3an−1 + 4an−2 rekurziót kapjuk. A jobb oldal első tagjában 3féleképpen költhetjük el egy cikkre az első eurót, ettől függetlenül költhetjük el a maradék n − 1 eurót. Hasonlóan, ha elsőre 2 eurós cikket vásárolunk, azt 4-féleképp tehetjük meg, majd ettől függetlenül elkölthetjük a megmaradt (n − 2) eurónkat.

Figyelem! Az an−2 együtthatója nem az, hogy 2 eurót hányféleképpen költhetünk el, hanem az, hogy 2 eurót egyetlen cikkre hányféleképpen költhetünk el, hiszen az első megvett árucikk értéke szerint esetelünk. ♦ Az első két tag a1 = 3, a2 = 3 · 3 + 4, összhangban az a0 = 1 érzésünkkel. Ez segíthet az ellenőrzésben, a2 -t (illetve ha a3 -ra is szükségünk van, akkor azt) ugyanazzal a részfeladatokra bontással számolhatjuk ki, mint amivel a rekurziót kapjuk. ♦

Példa. Hány olyan n hosszú, az a, b és c betűkből felépülő szó (azaz nem feltétlenül értelmes betűsorozat) van, amelyben nincs két b betű egymás mellett? Megoldás. Szokás szerint jelölje an az n betűből álló jó (azaz bb-mentes) szavak számát. Itt is az első (illetve az első kettő) betű szerint csoportosítjuk az n hosszú, jó szavakat. Két esetet vizsgálunk: • Ha az első betű nem b, akkor ezt tetszőleges n − 1 hosszú jó szó követheti, amiből an−1 darab van. Mivel az első betű kétféle (a vagy c) lehet, összesen 2an−1 olyan n hosszúságú jó szó van, ami nem b-vel kezdődik.

1.2. PÉLDÁK.

7

• Ha az első betű b, akkor utána a vagy c kell jöjjön, azt pedig bármely n − 2 hosszú jó szó köveheti, amiből an−2 van. Tehát b-vel kezdődő, n hosszú jó szóból 2an−2 van. Végeredményben az an = 2an−1 + 2an−2 rekurziót kaptuk. Könnyen megkapható, hogy a1 = 3, a2 = 8 (és a0 = 1 az üres szó miatt). ♦ Nehezebb feladathoz jutunk, ha a bc egymást követő párt zárjuk ki.

Példa. Hány olyan n hosszú, az a, b és c betűkből felépülő szó van, amelyben nincs egymás mellett bc ilyen sorrendben? (Tehát cb vagy bac lehet.) Megoldás. Most fordítva okoskodunk: minden n hosszú jó szót megkapunk akkor, ha egy n − 1 hosszú jó szó elé írunk egy betűt. Így 3an−1 darab szót kaptunk, ám ezek között sajnos vannak rosszak is, mégpedig azok, amelyek bc-vel kezdődnek. Ilyet akkor kaptunk, amikor egy c-vel kezdődő jó szó elé b-t írtunk. Tehát pontosan annyi rossz szót állítottunk elő, ahány c-vel kezdődő, n − 1 hosszú jó szó van. Ezek száma pedig an−2 , hiszen az első c betűt bármelyik n − 2 hosszú jó szó követheti. Kivonva az összesből a rosszakat az an = 3an−1 − an−2 rekurziót kapjuk. Nyilván a1 = 3, a2 = 8, hiszen csak a bc szó rossz. ♦

Más megoldás: Logikailag kevésbé trükkös az alábbi okoskodás. Ismét első betű szerinti esetszétválasztást alkalmazunk. Az eddigiekhez hasonlóan a-val vagy c-vel kezdődő, n hosszú, jó szóból egyaránt an−1 van, ez összesen 2an−1 darab. Ha a szó b-vel kezdődik, akkor két lehetőségünk van: vagy a, vagy b betű követi. Ha a áll utána, azt tetszőleges n − 2 hosszú, jó szó követheti, melyek száma an−2 . Ha b áll utána, ismét két lehetőségünk van: vagy a, vagy b betű követi... Ezt folytatva előbb-utóbb elérünk a végéig. Ezt a gondolatmenetet az alábbi módon kényelmes megfogalmazni: Csoportosítsunk a szó elején álló b betűk száma szerint! Azaz jelölje sk azon n hosszú, jó szavak számát, melyek k darab b betűvel kezdődnek. A fentebbi gondolatmenet szerint s0 = 2an−1 ; sk = an−k−1 , ha 1 ≤ k ≤ n − 1 (hiszen a k darab b betű után egy a betűnek kell állnia, amit egy n − k − 1 hosszú, jó szó követ (a0 = 1 legyen)); végül sn = 1 (ami a csupa b betűből álló szónak felel meg). Ebből (s0 + s1 + . . . + sn =) an = 2an−1 + an−2 + an−3 + . . . + a0 + 1. Felírva ugyanezt a rekurziót an−1 -re az an−1 = 2an−2 + an−3 + an−4 + . . . + a0 + 1 összefüggést kapjuk. Az előbbi egyenletből kivonva az utóbbit az an − an−1 = 2an−1 − an−2 kifejezést kapjuk, átrendezve an = 3an−1 − an−2 , ami éppen a fenti rekurzió. Ez a második ötlet akkor működik, ha az an felírásában szereplő tagok indexei számtani sorozatot alkotnak, mert akkor a kivonás után majdnem minden tag kiesik. ♦

Más megoldás: Jelölje cn azon n hosszú, jó szavak számát, melyek c-vel kezdődnek, és bn azokét, amelyek nem c-vel kezdődnek. Ekkor an = bn + cn . Másrészt cn = an−1 (c után bármi állhat), és bn = an−1 + bn−1 (attól függően, hogy a-val vagy b-vel kezdődik). Tehát an = bn + cn = an−1 + bn−1 + an−1 = 2an−1 + bn−1 = 2an−1 + an−1 − cn−1 = 3an−1 − an−2 .♦

8

1. FEJEZET. ÁLLANDÓ EGYÜTTHATÓS LINEÁRIS REKURZIÓK

Megjegyzés. Az első elem szerinti szétválasztás helyett tekinthettük volna az utolsó elemet is; néha ez kényelmesebb lehet. ♦

Gyakorlófeladatok: Hányféleképpen fedhető le a 2 × n-es sakktábla 2 × 1-es dominókkal? És a 3 × n-es 3 × 1-esekkel? És a 2 × n-es három mezőt elfoglaló L betőkkel? És ha vegyesen használjuk az L betűket és a 2 × 1-eseket? És ha vegyesen használjuk az L betűket és a 3 × 1-eseket, illetve a 4 × 1-eseket? (Mindegyik esetben elég csak a rekurziót felírni.)

1.3. Olvasmány 1.3.1. Ha nem mértani sorozatokból építkezünk Mint azt megjegyeztük, egy lineáris rekurziónak eleget tevő sorozatok vektorteret alkotnak, melynek elég egy bázisát megtalálnunk ahhoz, hogy tetszőleges (a rekurziót kielégítő) sorozatot elő tudjunk állítani. E szakaszban ezt mutatjuk meg másodfokú rekurziókra lineáris algebrai ismeretekre való hivatkozás nélkül. 1.6. definíció. Az a′n és a′′n sorozatok függetlenek, ha egyik sem az azonosan nulla sorozat, továbbá nem egymás számszorosai, azaz semmilyen c ∈ R-re nem teljesül, hogy a′n = ca′′n minden n ∈ N-re. ♦ Megjegyzés. Mivel egy k-adfokú rekurziót kielégítő sorozatot az első k tagja egyértelműen meghatározza, ilyen sorozatok függetlenségéhez elég az első k tagra ellenőrizni, hogy azok nem egymás számszorosai. ♦

Megmutatjuk, hogy bármely két független megoldás megfelel egy explicit képlet előállításához.

1.7. állítás. Legyen a′n és a′′n két, az (1.2) rekurziónak eleget tevő, független sorozat. Ekkor az (1.1) és (1.2) által meghatározott an sorozat egyértelműen előáll an = λ1 a′n +λ2 a′′n alakban (λ1 , λ2 ∈ C). Bizonyítás. Az (1.1) kezdeti feltételek a λ1 és λ2 ismeretlenekre a szokásos módon az α = λ1 a′1 + λ2 a′′1 β = λ1 a′2 + λ2 a′′2 egyenletrendszert adják. Azt kell ellenőriznünk, hogy ez mindig megoldható-e. A függetlenség miatt egyik sorozat sem azonosan nulla, tehát a′1 és a′2 közül legfeljebb egy lehet nulla, szintúgy a′′1 és a′′2 közül is. Továbbá, ha például a′1 = 0, akkor a′′1 6= 0, hiszen ellenkező esetben a c = a′′2 /a′2 szorzóval c · a′1 = a′′ 1 és c · a′2 = a′′ 2 is teljesülne. Azaz az a′1 és a′′1 közül is csak az egyik lehet nulla; szintúgy a′2 és a′′2 közül is. Emiatt feltehetjük (esetleg megcserélve az a′n és a′′n sorozatok szerepét), hogy a′1 6= 0 és a′′2 6= 0. Az első egyenletet a′2 -vel, a másodikat a′1 -gyel szorozva, majd egymásból kivonva a′1 β − a′2 α = λ2 (a′1 a′′2 − a′′1 a′2 )

1.3. OLVASMÁNY

9

adódik, amiből λ2 egyértelműen meghatározható, ha a′1 a′′2 6= a′′1 a′2 . Indirekte tegyük fel, hogy a′1 a′′2 = a′′1 a′2 . A feltevésünk miatt a bal oldal nem nulla, így a jobb oldal sem, tehát átoszthatunk, hogy lássuk: a′1 /a′′1 = a′2 /a′′2 . Ekkor c = a′1 /a′′1 -gyel ca′n ≡ a′′n volna, ellentmondva a függetlenségnek. Tehát λ2 kiszámolható, amiből λ1 azonnal adódik. Megjegyzés. Kis algebrai kitérő: a megoldhatóságnál voltaképpen azt használtuk, hogy · ′ ¸ ′′ a1 a1 az együtthatómátrix determinánsa, det = a′1 a′′2 − a′2 a′′1 nem nulla. Ez fennáll, a′2 a′′2 különben a két oszlopa (tehát a sorozatok első két tagja, és így a rekurzv képzési szabály miatt a sorozatok egésze) lineárisan összefüggő volna, ellentmondva a′n és a′′n (lineáris) függetlenségének. ♦ A teljesség kedvéért megmutatjuk, hogy a karakterisztikus egyenletből kapott megoldások függetlenek.

1.8. állítás. Legyen x1 és x2 az (1.2) karakterisztikus egyenlet két gyöke. Ekkor az a′n = x1n−1 és a′′n = x2n−1 sorozatok függetlenek, ha x1 6= x2 ; ha x1 = x2 , akkor az a′n = x1n−1 és az a′′n = (n − 1)x1n−1 sorozatok függetlenek.

Bizonyítás. Először tegyük fel, hogy x1 6= x2 . Mivel a′1 = a′′1 = 1, így csak a′n ≡ a′′n ronthatná el a függetlenséget (a c = 1 szorzóval), amit a′2 = x1 6= x2 = a′′2 cáfol. A másik eset hasonlóan meggondolható.

1.3.2. Komplex megoldások lecserélése valósakra Előfordulhat, hogy az x2 − c1 x − c2 = 0 karakterisztikus egyenlet gyökei (x1 és x2 ) nem valós, hanem komplex számok. Ez tehát azt jelenti, hogy a kezdeti értékekre vonatkozó egyenletrendszert a komplex számok halmazán kell megoldanunk. Ha valaki el akarja kerülni a komplex számokkal való számolást, akkor a következőt teheti. Mivel a karakterisztikus egyenlet valós együtthatós, a komplex gyökök egymás konjugáltjai, azaz x1 = z, x2 = z, z ∈ C. Legyen z = r(cos ϕ + i sin ϕ) a z komplex szám trigonometrikus alakja. Itt r cos ϕ = Re(z) és r sin ϕ = Im(z) a z valós, illetve képzetes része. Idézzük fel, hogy z k = rk (cos(kϕ) + i sin(kϕ)), z k = rk (cos(kϕ) − i sin(kϕ)).

Az 1.4. állítás szerint az a′n = (z n−1 + z n−1 )/2 = rn−1 cos((n − 1)ϕ) és az a′′n−1 = (z n−1 − z n−1 )/(2i) = rn−1 sin((n − 1)ϕ) valós sorozatok is kielégítik a karakterisztikus egyenletet (és függetlenek). Így kereshetjük a megoldást an = λ1 rn−1 cos((n − 1)ϕ) + λ2 rn−1 sin((n − 1)ϕ) alakban is. A kezdeti értékekre vonatkozó egyenletrendszer ekkor az a1 = λ 1 a2 = λ1 r cos ϕ + λ2 r sin ϕ = λ1 Re(z) + λ2 Im(z) alakot ölti, amit megoldhatunk a valós számok halmazán. Nézzük meg a korábban már bemutatott példán, hogyan alkalmazható ez a módszer! Példa. Oldjuk meg az an+2 = 2an+1 − 2an , a1 = 1, a2 = 2 lineáris rekurziót!

10

1. FEJEZET. ÁLLANDÓ EGYÜTTHATÓS LINEÁRIS REKURZIÓK

Megoldás. A karakterisztikus egyenlet x2 − 2x + 2 = 0, aminek x1 = 1 + i = z = √ 2(cos 45◦ + i sin 45◦ ) és x2 = 1 − i = z a megoldásai. A megoldást tehát kereshetjük √ n−1 √ n−1 cos(n − 1)45◦ + λ1 · 2 (cos(n − 1)45◦ + sin(n − 1)45◦ ) alakban, ahol an = λ 1 · 2 (a1 =) 1 = λ1 (a2 =) 2 = λ1 Re(z) + λ2 Im(z) = λ1 + λ2 . √ n−1 ◦ ) adódik. Kis számolással Ebből√λ1 = λ2 = 1, így an = 2 (cos(n−1)45◦ +sin(n−1)45 √ n n ◦ ◦ ◦ ◦ an = 2 (sin 45 cos(n − 1)45 + cos 45 sin(n − 1)45 ) = 2 sin(n · 45◦ ) kapható. ♦

1.3.3. Inhomogén rekurziók megoldása Tekintsük az alábbi másodfokú, de inhomogén rekurzióval megadott sorozatot: an+2 = c1 an+1 + c2 an + c3 ,

(1.4)

ahol aza1 és a2 kezdeti értékeket adottnak tekintjük. Erre a mértani sorozatos ötlet első közelítésben nem működik, mert xn−1 -gyel leosztva nem kapunk másodfokú egyenletet. Az ötlet az, hogy először keresünk valahogyan egy tetszőleges a∗n sorozatot, ami teljesíti (1.4)t (úgynevezett partikuláris megoldást), majd áttérünk a feladat homogenizált változatára, azaz a bn+2 = c1 bn+1 + c2 bn (1.5) megoldásait keressük. A rekurziót teljesítő bn sorozat esetén a∗n+2 + bn+2 = c1 a∗n+1 + c2 a∗n + c3 + c1 bn+1 + c2 bn = c1 (a∗n+1 + bn+1 ) + c2 (a∗n + bn ) + c3 , tehát az a∗n +bn sorozat megoldása (1.4)-nek. A kezdeti értékek beállításához a bn sorozatra a b1 = a1 − a∗1 , b2 = a2 − a∗2 feltételeket kell tennünk. Tehát ha találunk alkalmas a∗n sorozatot, a feladatot visszavezettük a homogén esetre. Ilyen sorozatot pedig egyszerűen találunk, az alábbi állítás szerint szinte mindig konstans sorozat formájában. 1.9. állítás. Midnig találunk a∗n = anh alakú megoldást (1.4)-re, ahol 0 ≤ h ≤ 2, a ∈ R, mégpedig a következőek szerint. Ha c1 + c2 6= 1, akkor az a∗n = c3 /(1 − c1 − c2 ) teljesíti (1.4)-t. Ha c1 + c2 = 1, de c1 6= 2, akkor a∗n = (c3 /(2 − c1 ))n teljesíti (1.4)-t. Ha c1 = 2 és c2 = −1, akkor a∗n = (c3 /2) · n2 teljesíti (1.4)-t. Bizonyítás. Az a∗n ≡ a konstans sorozat pontosan akkor megoldás, ha a = c1 a + c2 a + c3 , azaz a = c3 /(1 − c1 − c2 ); ez mindig jó lesz, ha c1 + c2 6= 1. Ha c1 + c2 = 1, keressünk a∗n = a · n alakú megoldást. Ez pontosan akkor jó, ha a(n + 2) = c1 a(n + 1) + c2 an + c3 = (c1 + c2 )an + ac1 + c3 = an + ac1 + c3 . Átrendezve a = c3 /(2 − c1 ). Ez mindig jó, kivéve, ha c1 = 2, és így c2 = −1. Ekkor a rekurziónk an+2 − 2an+1 + an = c3 alakú. Legyen a∗n = c3 · n2 /2. Behelyettesítve a∗n+2 − 2a∗n+1 + a∗n = c23 ((n + 2)2 − 2(n + 1)2 + n2 ) = c23 · 2 = c3 , tehát a∗n megfelelő. Illusztráljuk egy példán a módszert! Példa. Oldjuk meg az an = 6an−1 − 9an−2 + 4, a1 = 2, a2 = 4 rekurziót!

1.3. OLVASMÁNY

11

Megoldás. Először keresünk egy partikuláris megoldást konstans sorozat formájában: a = 6a − 9a + 4, tehát az a∗n ≡ 1 sorozat megoldja a rekurziót. Ezután keresünk egy, a bn = 6bn−1 −9bn−2 homogén rekurziót kielégítő bn sorozatot, amit hozzáadva a∗n -hez kapjuk a megoldást az eredeti feladatra. Hogy a kezdeti értékek a végén az előírtak legyenek, a bn sorozatra a b1 = a1 − a∗1 = 2 − 1 = 1 és a b2 = a2 − a∗2 = 4 − 1 = 3 kezdeti feltételeket írjuk elő. A bn sorozatot a szokásos módon megkapjuk, miszerint bn = 3n−1 , tehát a megoldás an = bn + a∗n = 3n−1 + 1. ♦

1.3.4. Magasabb fokú rekurziók megoldása Tekintsük most az an+k = c1 an+k−1 + . . . + ck an

(1.6)

alakban megadott an sorozatot, ahol a kezdeti a1 , . . . , ak értékeket adottnak vesszük (kezdeti feltétel), a rekurziót leíró c1 , . . . , ck együtthatók pedig rögzített valós számok. Emlékeztetünk, hogy feltevésünk szerint ck 6= 0.

Ebben az esetben is teljesen analóg módon járhatunk el, a módszereink működnek. A bizonyítások során támaszkodni fogunk alapvető algebrai ismeretekre (polinomok, determinánsok, lineáris függetlenség). Először is vegyük észre, hogy az 1.4. állítás minden további nélkül általánosítható. 1.10. állítás. Ha az a(1) , a(2) , . . . , a(r) sorozatok teljesítik az (1.6) rekurziót, akkor tetPr szőleges i=1 αi a(i) lineáris kombinációjuk is. (Itt a sorozatok jobb felső sarkában sorszám (index) áll, nem kitevő.)

Bizonyítás. Teljesen analóg 1.4. bizonyításával. Lényegében annyit mond, hogy lineáris kombinációk lineáris kombinációja is az eredeti elemek lineáris kombinációja. Ekkor persze karakterisztikus egyenletünk k-adfokú: xk − c1 xk−1 − . . . − ck = 0.

Legyenek ennek gyökei x1 , x2 , . . . , xk . (Persze ha k ≥ 5, általános megoldóképlet híján ezeket a gyököket nem biztos, hogy meg tudjuk határozni.) Ezek egyike sem nulla, hiszen ck 6= 0. Ha a gyökök páronként különbözőek, akkor ugyanúgy, mint a k = 2 esetben, az xin−1 sorozatok (1 ≤ i ≤ k) egy bázisát alkotják a (1.6) egyenletet kielégítő sorozatok terének, magyarán an egyértelműen előáll an = λ1 x1 n−1 + . . . + λk xk n−1 alakban megfelelő λi ∈ R számokra (1 ≤ i ≤ k). A λi -k meghatározásához ugyanis az a1 = λ 1 + . . . + λ k a2 = λ 1 x 1 + . . . + λ k x k a3 = λ 1 x 1 2 + . . . + λ k x k 2 .. . ak = λ1 x1 k−1 + . . . + λk xk k−1

12

1. FEJEZET. ÁLLANDÓ EGYÜTTHATÓS LINEÁRIS REKURZIÓK

lineáris egyenletrendszert kell megoldanunk. Lineáris algebrából ismert, hogy ennek az egyenletrendszernek mindig van megoldása (méghozzá egyértelmű), hiszen a szóbanforgó egyenletrendszer együtthatómátrixának determinánsa 

  det  

1 x1 .. .

1 x2 .. .

1 x3 .. .

xk−1 1

xk−1 2

xk−1 3

... ...

1 xk .. .

... . . . xk−1 k

    

Vandermonde-féle, így nem nulla (ezt később általánosabban is belátjuk). Aprópénzre váltva ez annyit jelent, hogy biztosak lehetünk benne, hogy a középiskolából ismert módszerekkel megoldva az egyenletrendszert, megkapjuk a kívánt megoldást. Lássunk erre is egy példát! Példa.

Oldjuk meg az an+3 = 2an+2 + an+1 − 2an , a1 = 1, a2 = 3, a3 = 7 rekurziót!

Megoldás. A karakterisztikus egyenlet x3 − 2x2 − x + 2 = 0, aminek x1 = 1, x2 = −1 és x3 = 2 a megoldásai, így an = λ1 + λ2 (−1)n−1 + λ1 2n−1 alakú. Egyenletrendszerünk: 1 = λ1 + λ2 + λ3 3 = λ1 − λ2 + 2λ3 7 = λ1 + λ2 + 4λ3 , amelynek λ3 = 2, λ2 = 0 és λ1 = −1 a megoldása, azaz an = −1 + 2n .

♦

Az alábbi állítás szerint akkor sincs baj, ha a karakterisztikus egyenletnek vannak többszörös gyökei, ahogy ez nem okozott megoldhatatlan problémát a k = 2 esetben sem. 1.11. állítás. Tegyük fel, hogy q a karakterisztikus egyenletnek r+1-szeres gyöke. Ekkor a q n−1 , nq n−1 , . . . , nr q n−1 sorozatok kielégítik a (1.6) egyenletet. Bizonyítás. A c0 = −1 választással a (1.6) karakterisztikus egyenletet p(x) =

k X

ci xk−i = 0

i=0

alakra hozható. Jelölje p (x) a p(x) polinom j-edik deriváltját. Ha q r + 1-szeres gyök, akkor gyöke az első r deriváltnak is, azaz (j)

(j)

p (q) =

k X i=0

ci (k − i)(k − i − 1) · · · (k − i − j + 1)q k−i−j = 0

(0 ≤ j ≤ r).

Itt a nulladik derivált, p(0) (x) szokás szerint magát p(x)-et takarja; az összegzésben pedig azért mehetünk el negatív kitevőjű hatványokig is (azaz megengedjük i > k − j-t), mert akkor az előtte levő szorzótényezők valamelyike úgyis nulla. Azt akarjuk ellenőrizni, hogy az a′n = ns q n−1 kielégíti-e a (1.6) rekurziót (0 ≤ s ≤ r), azaz hogy (n + k)s q n+k−1 = c1 (n + k − 1)s q n+k−2 + c2 (n + k − 2)s q n+k−3 + . . . + ck ns q n−1

1.3. OLVASMÁNY

13

teljesül-e. Leosztva q n−1 -gyel és kivonva a bal oldalt, az alábbi ekvivalens egyenlőséget nyerjük: k X ci (n + k − i)s q k−i = 0. i=0

A binomiális tétel felhasználásával tovább alakítjuk ezt az egyenletet: k X

ci

à s µ ¶ X s j=0

i=0

j

n

s−j

j

(k − i)

!

q

k−i

=

s µ ¶ X s

j

j=0

ns−j

k X i=0

ci (k − i)j q k−i = 0.

P P Azt fogjuk megmutatni, hogy fj (q) = ki=0 ci (k − i)j q k−i előáll fj (q) = ji=0 dj,i p(i) (q) alakban alkalmas dj,0 , . . . , dj,j szorzókkal minden 0 ≤ j ≤ s-re. Ez bizonyítja az állítást, hiszen p(i) (q) = 0 minden 0 ≤ i ≤ s-re.

Teljes indukciót alkalmazunk j szerint. A j = 0 és j = 1 esetekben f0 (q) = p(q) és f1 (q) = qp ′ (q) bizonyítja az állítást. Tegyük hát föl, hogy fj−1 (q)-ig igaz az állítás. Válasszunk olyan α1 , . . . , αj−1 egészeket, melyre x(x − 1)(x − 2) · · · (x − j + 1) + α1 xj−1 + . . . + αj−1 x ≡ xj teljesül (ez megtehető). Ekkor fj (q) =

k X i=0

(j)

= p (q) + α1

¡ ¢ ci q k−i (k − i) . . . (k − i − j + 1) + α1 (k − i)j−1 + . . . + αj−1 (k − i) =

k X i=0

j−1 k−i

ci (k − i)

q

+ α2

k X i=0

(j)

j−2 k−i

ci (k − i)

= p (q) +

j−1 X

q

+ . . . + αj−1

k X i=0

ci (k − i)q k−i =

αi fj−i (q).

i=1

Indukciós feltevésünk szerint a jobb oldalon található szummás kifejezések mindegyike előáll a p(i) (q)-k kombinációjaként (i ≤ j), így azok fenti kombinációja, azaz fj (q) is. Megjegyzés. Az x1n−1 , nx1n−1 , . . . , ns x1n−1 jó sorozatokat lecserélhetjük az x1n−1 , (n − 1)x1n−2 , . . . , (n − 1)(n − 2) · · · (n − s)xn−1−s sorozatokra is, mert előállnak az előzőek 1 n−2 lineáris kombinációjaként (például (n − 1)x1 = 1/x1 (nx1n−1 − x1n−1 )), így az 1.10. állítás szerint ezek is teljesítik a rekurziót. Ez a deriváltak felbukkanása miatt természetesebb volna, viszont az állításokat kényelmesebb megfogalmazni a korábban látott módon. ♦

Kérdés még, hogy a talált sorozatok valóban lineárisan függetlenek-e, azaz hogy a kezdeti értékekre felírt egyenletrendszerünknek van-e (egyértelmű) megoldása.

1.12. állítás. Tegyük föl, hogy az (1.3.4) karakterisztikus egyenletnek s különböző gyöke van, az i-edik (valós vagy komplex) gyöke xi , annak multiplicitása αi + 1 (αi ≥ 0), ahol 1 ≤ i ≤ s (ekkor persze α1 + . . . + αs = k − s). Ekkor az x1n−1 , nx1n−1 , . . . , nα1 x1n−1 , x2n−1 , nx2n−1 , . . . , nα2 x2n−1 , . . . , xsn−1 , nxsn−1 , . . . , nαs xsn−1 sorozatok lineáris kombinációjaként tetszőleges, az (1.6)-et kielégítő an sorozat előállítható.

14

1. FEJEZET. ÁLLANDÓ EGYÜTTHATÓS LINEÁRIS REKURZIÓK

Bizonyítás. Vezessük be a cn,j = (n − 1)(n − 2) · · · (n − j) jelölést, valamint legyen cn,0 = 1 (az üres szorzatra vonatkozó konvenciónak is megfelelően). Ha j ≥ n, akkor cn,j = 0, hiszen szerepel benne egy nullás szorzótényező. Használjuk továbbá a t = k − 1 jelölést2 . Az előző megjegyzés alapján a sorozatainkból lineáris kombinációval előállíthatóak a cn,j xn−1−j sorozatok is (1 ≤ i ≤ s, 0 ≤ j ≤ αi ), tehát elegendő i az an sorozatot αi s X X λi,j cn,j xin−1−j an = i=1 j=0

alakban előállítanunk. A kezdeti értékekre vonatkozó lináris egyenletrendszer k × k-as M együtthatómátrixa ekkor   c1,0 0 0 ... 0 . . . c1,0 0 0 ... 0  c2,0 x1 c2,1  0 ... 0 . . . c2,0 xk c2,1 0 ... 0   2  c3,0 x2 c3,1 x1  c . . . 0 . . . c x c x c . . . 0 3,2 3,0 3,1 k 3,2 1 k  .  ..  .. .. .. .. .. .. .. ... ...  .  . . . ... . . . . t−α1 t−αs t−1 t−2 t t t−1 t−2 ck,0 x1 ck,1 x1 ck,2 x1 . . . ck,α1 x1 . . . ck,0 xs ck,1 xs ck,2 xs . . . ck,αs x1 . . . {z } {z } | | α1 + 1 αs + 1 Megmutatjuk, hogy a mátrix sorai lineárisan függetlenek, azaz a determinánsa nem nulla. Legyen pi (x) = xi−1 , i = 1, . . . , k. Tekintsük a ´ ³ (α ) (1) (α ) (1) pi = pi (x1 ), pi (x1 ), . . . , pi 1 (x1 ), . . . , pi (xs ), pi (xs ), . . . , pi k (xs )

vektorokat. (Az első α1 +1 koordinátába a pi 0., 1., . . . , α1 -edik deriváltjának az x1 helyen vett értékét, a következő α2 + 1 koordinátába a pi 0., 1., . . . , α2 -edik deriváltjának az x2 helyen vett értékét stb. írjuk.) Mivel pi (x)(j) = (i−1)(i−2) · · · (i−j)xi−1−j = ci,j xi−1−j , így P pi éppen M i-edik sora. Indirekte tegyük föl, M sorai összefüggőek. Ekkor ki=1 ai pi = 0 P P alkalmas nem csupa nulla ai együtthatókkal. Legyen f (x) = ki=1 ai pi (x) = ki=1 ai xi−1 . Tehát f (x) egy nem azonosan nulla, legfeljebb k − 1-edfokú polinom. A pi vektorok definíciójából P adódik, hogy f (x)-nek xj éppen αj + 1-szeres gyöke (1 ≤ j ≤ s), így f (x) foka legalább si=1 (αi + 1) = k, ellentmondás. Így det(M ) 6= 0, tehát tetszőleges an sorozat előáll alkalmas λi,j együtthatókkal.

Megjegyzés. Vegyük észre, hogy k darab egyszeres gyök esetén (azaz ha s = k és αi = 0 minden 1 ≤ i ≤ k-ra) a mátrixunk Vandermonde-típusú, tehát speciálisan a Vandermonde-féle determinánsok nemnulla voltát is beláttuk. ♦ Lássunk erre is egy példát!

Példa. Oldjuk meg az an+7 = an+6 − 3an+5 + 3an+4 − 3an+3 + 3an+2 − an+1 + an , q1 = 3, a2 = −13, a3 = −5, a4 = 43, a5 = 11, a6 = −85, a7 = −13 rekurziót! 2

Ez szigorúan technikai paraméter, csak hogy kiférjen a mátrix a lapra.

1.3. OLVASMÁNY

15

Megoldás. A karakterisztikus egyenlet x7 − x6 + 3x5 − 3x4 + 3x3 − 3x2 + x − 1 = 0. Észrevehetjük, hogy x = 1 megoldás, így x7 − x6 + 3x5 − 3x4 + 3x3 − 3x2 + x − 1 = (x − 1)(x6 + 3x4 + 3x2 + 1) = (x − 1)(x2 + 1)3 , tehát az x1 = 1 egyszeres, x2 = i és x3 = −i pedig háromszoros gyök. Ekkor a megoldást kereshetjük an = λ1 1n−1 + λ2 in−1 + λ3 nin−1 + λ4 n2 in−1 + λ5 (−i)n−1 + λ6 n(−i)n−1 + λ7 n2 (−i)n−1 alakban. A kezdeti értékekre vonatkozó egyenletrendszerünk (a1 (a2 (a3 (a4 (a5 (a6 (a7

=) =) =) =) =) =) =)

= = = = = = =

λ1 + λ2 + λ3 + λ4 + λ5 + λ6 + λ7 λ1 + λ2 i + 2λ3 i + 4λ4 i + λ5 i + 2λ6 i + 4λ7 i λ1 − λ2 − 3λ3 − 9λ4 − λ5 − 3λ6 − 9λ7 λ1 − λ2 i − 4λ3 i − 16λ4 i − λ5 i − 4λ6 i − 16λ7 i λ1 + λ2 + 5λ3 + 25λ4 + λ5 + 5λ6 + 25λ7 λ1 + λ2 i + 6λ3 i + 36λ4 i + λ5 i + 6λ6 i + 36λ7 i λ1 − λ2 − 7λ3 − 49λ4 − λ5 − 7λ6 − 49λ7

Ennek megoldása némi erőfeszítéssel meghatározható, az eredmény λ1 = 1, λ2 = i, λ3 = 1 + i, λ4 = i, λ5 = −i, λ6 = 1 − i, λ7 = −i, tehát an = 1 + in + (1 + i)nin−1 + n2 in + (−i)n + (1 − i)n(−i)n−1 + n2 (−i)n . ♦ Komplex megoldások valósra cserélése magasabb fokú rekurziók esetén Most is előfordulhat, hogy az (1.3.4) karakterisztikus egyenletnek komplex gyökei is vannak. Mivel az (1.3.4) egyenlet valós együtthatós, ezek a komplex gyökök konjugált gyökpárokban fordulnak elő. A komplex számokkal való számolást teljesen hasonló módon lehet elkerülni, mint a k = 2 esetben; persze k > 2 miatt előfordulhat az is, hogy egy komplex gyök magasabb multiplicitással szerepel (a konjugáltjával együtt). Ha tehát x1 = z = r(cos ϕ + i sin ϕ) ∈ C \ R több mint s-szeres komplex gyök (ekkor z is az), akkor az ns z n−1 és az ns z n−1 sorozatokat lecserélhetjük az ns (z n−1 + z n−1 )/2 = ns cos(n − 1)ϕ és az ns (z n−1 − z n−1 )/2i = ns sin(n − 1)ϕ sorozatokra. Ezekkel pedig a kezdeti értékekre vonatkozó lineáris egyenletrendszerünk valós együtthatós lesz, melynek megoldása a szokásos módon történik. A függetlenséget garantálja, hogy az új sorozatokból elő tudjuk állítani az eredetieket is. Inhomogén magasabb fokú rekurziók megoldása Tekintsük az an+k = c1 an+k−1 + . . . + ck an + ck+1

(1.7)

rekurziót! Most is az első k tagot adottnak tekintjük, és explicit képletet keresünk az általános tagra. A módszer pontosan ugyanaz, mint korábban is: először keresünk egy

16

1. FEJEZET. ÁLLANDÓ EGYÜTTHATÓS LINEÁRIS REKURZIÓK

partikuláris megoldást (ahol nem vesszük figyelembe a kezdeti értékeket), majd a homogenizált változatra írunk fel egy megfelelően módosított kezdetiérték-feladatot. A kérdés csak az, hogy hogyan találunk partikuláris megoldást? A másodfokú esetben látott, amolyan „kalapból nyuszi” módszert általánosítjuk. 1.13. állítás. Az (1.7) rekurziónak mindig van a∗n = anh alakú partikuláris (a kezdetiérték-feltételeket figyelmen kívül hagyó) megoldása alkalmas a konstanssal, 0 ≤ h ≤ k. Bizonyítás. Legyen tehát a∗n = anh . Próbáljuk meg, hogy h = 0 esetén találunk-e megfelelő a szorzót. Ez annyit tesz, hogy a=

k X i=1

aci + ck+1 ⇐⇒ a = Pk

tehát mindig van jó megoldás, kivéve, ha gyel. Ekkor az alábbinak kell teljesülnie: a(n+k) =

k X

i=1 ci

k X

aci (n+k−i)+ck+1 = a(n+k)

i=1

i=1 ci

,

= 1. Ez esetben próbálkozzunk h = 1-

ci −a

i=1

1−

ck+1 Pk

k X

ici +ck+1 = a(n+k)−a

i=1

k X

ici +ck+1 ,

i=1

átrendezve a

k X

ici = ck+1 ,

i=1

ami mindig megoldható, kivéve, ha a(n + k)2 =

k X i=1

= a(n + k)2

k X i=1

Pk

i=1

ici = 0. Ez esetben próbálkozzunk h = 2-vel:

aci (n + k − i)2 + ck+1 =

ci − 2a(n + k)

k X

ici + a

i=1

k X i=1

k X

¡ ¢ aci (n + k)2 − 2(n + k)i + i2 + ck+1 =

i2 ci + ck+1 = a(n + k)2 + a

i=1

k X

i2 ci + ck+1

i=1

aPkorábban problémát okozó egyenlőségek miatt. Ez megintcsak megoldható, kivéve, ha k 2 i=1 i ci = 0. P P Tegyük hát fel, hogy ki=1 ci = 1, és egy s > 0 számig ki=1 is ci = 0. Vegyük észre, P hogy s akár páros, akár páratlan, ez ekvivalens ki=1 (−i)s ci = 0-val. Próbálkozzunk most h = s + 1-gyel: h

a(n + k) =

k X i=1

=a

h µ ¶ X h j=0

j

j

(n+k)

h

aci (n + k − i) + ck+1 = k X i=1

h−j

(−i)

ci +ck+1

k X i=1

h µ ¶ X h aci (n + k)j (−i)h−j + ck+1 = j j=0

k h−1 µ ¶ k X X X h h j =a (−i) ci +a (n+k) (−i)h−j ci + j i=1 j=1 i=1

1.3. OLVASMÁNY

17 h

+a(n + k)

k X

ci + ck+1 = a

i=1

k X

(−i)h ci + a(n + k)h + ck+1 ,

i=1

Pk

ami mindig megoldható, kivéve, ha i=1 (−i)s+1 ci = 0. Meddig görgethetjük magunkkal ezt a „pechsorozatot”? Állítjuk, hogy egyszer vége legkésőbb a k-as Pk szakad, mégpedig P k s kitevőnél. Tegyük fel ugyanis indirekte, hogy c = 1, továbbá i=1 i i=1 (−i) ci = 0 minden 1 ≤ s ≤ k-ra. Tekintsük az A=

k X i=1

(i − 1)(i − 2) . . . (i − k)ci

kifejezést. Egyrészt minden tagjában valamelyik szorzótényező nulla, tehát A = 0; másrészt (i − 1)(i − 2) · · · (i − k) felírható γk ik + γk−1 ik−1 + . . . + γ1 i + γ0 alakban alkalmas γj egészekre (1 ≤ j ≤ k). Könnyen kiolvasható, hogy γk = 1 és γ0 = (−1)k k! 6= 0. Így tehát à k ! k k k k X X X X X j j A= γj i c i = c i = γ0 , i c i = γ0 γj i=1

j=0

j=0

i=1

i=1

hiszen γj szorzója feltevésünk szerint nulla minden j > 0-ra, j = 0-ra pedig egy. Így a 0 = A = γ0 6= 0 ellentmondáshoz jutottunk, ami bizonyítja az állítást.