7 Recurrente betrekkingen

7

Recurrente betrekkingen

Bij de analyse van allerlei verschijnselen komen we rijen tegen waarvan de termen niet rechtstreeks door een formule worden gegeven, maar waarvoor alleen bekend is hoe je een element van de rij kunt berekenen uit een aantal voorgaande elementen. Een dergelijke definitie van een rij noemen we een recurrente betrekking. Vaak zijn we erin ge¨ınteresseerd vanuit de recurrente beschrijving van de rij een formule te vinden die een term van de rij rechtstreeks beschrijft.

7.1

Definitie en voorbeelden

Definitie 7.1 Zijn (an ) een rij reële getallen en k > 0 een geheel getal. Een recurrente betrekking (van diepte k) is een beschrijving waarin a n wordt uitgedrukt in an−1 , an−2 , . . . , an−k . Voorbeeld 7.1 (1) De rij an = n! kan worden gedefinieerd door de recurrente betrekking a0 = 0! = 1 en an = n · an−1 voor n > 1. (2) Is bn een rij, dan kan de rij van partiële sommen eerd door 0 X i=0

bi = b0 en

n X

bi = b n +

i=0

n−1 X

Pn

i=0 bi

worden gedefini-

bi voor n > 1.

i=0

(3) Is a 6= 0 een reëel getal, dan kan de rij an = an worden gedefinieerd door a0 = 1 en an = a · an−1 voor n > 1. ♥ Voorbeeld 7.2 De getallen van Fibonacci an zijn gedefinieerd door an+2 = an+1 + an . Fibonacci, een andere naam voor Leonardo van Pisa, schreef in 1202 zijn boek ‘Liber Abaci’, waarin onder andere het probleem voorkomt over het aantal paren konijnen dat in e´ e´ n jaar uit 1 paar ontstaat als er geen konijnen sterven, en uit elk paar iedere maand een nieuw paar geboren wordt dat zelf vanaf de tweede maand deelneemt aan de voortplanting. Dan is an het aantal paren konijnen na n maanden. Als a0 = 0 en a1 = 1, dan zijn de getallen van Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, . . . ♥

87

Hoofdstuk 7 R ECURRENTE BETREKKINGEN

Kader 7.1: C ODERINGSTHEORIE

EN VERBODEN DEELRIJEN .

Wanneer informatie door computers wordt verstuurd, wordt een vast bitpatroon, zoals 01111110, gebruikt om het einde van een bericht te markeren. Het bericht zelf moet dan zo worden gecodeerd, dat dit patroon er niet in voorkomt, anders stopt de ontvangende machine te snel met luisteren. Om te weten hoeveel bits nodig zijn om een bepaalde boodschap te coderen, onderzoeken we eerst hoeveel bitrijen van een bepaalde lengte er bestaan waarin het speciale patroon niet voorkomt. Er bestaan 2n bitrijen van lengte n; hoeveel daarvan bevatten het patroon 000 niet? Noem dit aantal An en bedenk dat A0 = 1, A1 = 2, A2 = 4 (dus An = 2n voor n < 3) omdat een rij korter dan 3 nooit het patroon 000 kan bevatten. Een toegestane bitrij van lengte n kan bestaan uit: 1. 1 gevolgd door een willekeurig toegestaan patroon van lengte n−1; dit kan op An−1 manieren; of 2. 01 gevolgd door een willekeurig toegestaan patroon van lengte n− 2; dit kan op An−2 manieren; of 3. 001 gevolgd door een willekeurig toegestaan patroon van lengte n − 3; dit kan op An−3 manieren.

Het aantal rijen wordt dus gegeven door de recurrente betrekking A n = An−1 +An−2 +An−3 . De eerste 11 waarden van An (met ter vergelijking 2n ) zijn: n An 2n

0 1 1

1 2 2

2 4 4

3 7 8

4 13 16

5 24 32

6 44 64

7 81 128

8 149 256

9 274 512

10 504 1024

Kun je voorspellen hoe de rij verder gaat, of wat A1000 en A2000 zijn? Een rij an die voldoet aan de recurrente betrekking wordt ook een oplossing van deze betrekking genoemd. Een functie a(n) (met k willekeurige constanten), die alle oplossingen van de recurrente betrekking geeft, heet de algemene oplossing. Een oplossing die gegeven startwaarden a0 , a1 , . . . , ak−1 heeft, heet een specifieke oplossing.

7.2

De vergelijking an = Aan−1 + Ban−2

Na deze concrete voorbeelden bestuderen we de recurrente betrekking van het type (*)

an = Aan−1 + Ban−2 (n > 2)

waarbij a0 en a1 gegeven zijn en A en B constanten zijn. Verder nemen we B 6= 0.

Stelling 7.2 Zijn (an ) een oplossing van de recurrente betrekking (∗) en µ een (reëel of complex) getal, dan is de rij (µan ) ook een oplossing van (∗). Zijn (an ) en (a0n ) twee oplossingen van de recurrente betrekking (∗), dan is de rij (an + a0n ) ook een oplossing van (∗).

88

Bewijs 1. µan = µ(Aan−1 + Ban−2 ) = A(µan−1 ) + B(µan−2 ). 2. an + a0n = Aan−1 + Ban−2 + Aa0n−1 + Ba0n−2 = A(an−1 + a0n−1 ) +

B(an−2 + a0n−2 ). Zoek naar een oplossing van (*) in de vorm an = ω n , met een constante ω 6= 0. Substitutie in (*) levert ω n = Aω n−1 + Bω n−2 , ofwel (**)

Sectie 7.2 D E VERGELIJKING an = Aan−1 + Ban−2

ω 2 − Aω − B = 0.

Dus voldoet an = ω n aan (*) dan en slechts dan als ω een oplossing is van de vierkantsvergelijking (**). De oplossingen ω1 en ω2 van (**) zijn gegeven door de formules A 1p 2 ω1,2 = ± A + 4B. 2 2 Er geldt

ω 2 − Aω − B = (ω − ω1 )(ω − ω2 ).

Er zijn nu drie mogelijkheden:

Geval 1: A2 +4B > 0. De vergelijking (**) heeft twee reële wortels ω1 6= ω2 . De recurrente betrekking (*) heeft dus twee onafhankelijke oplossingen: ω 1n en ω2n . Met stelling 7.2 zien we dat an = Cω1n + Dω2n een oplossing is van (*) voor alle C, D ∈ R. Dit is de algemene oplossing van de recurrente betrekking (*) in dit geval. Als de startwaarden a 0 en a1 zijn gegeven, dan kunnen we C en D op eenduidige manier bepalen uit het stelsel Cω10 + Dω20 = a0 C + D = a0 of Cω11 + Dω21 = a1 ω1 C + ω 2 D = a 1 Dit geeft C=

ω1 a 0 − a 1 a1 − ω2 a0 , D= . ω1 − ω 2 ω1 − ω 2

Voorbeeld 7.3 Bij de recurrente betrekking an = 3an−1 − 2an−2

voor (n > 2)

hoort de vierkantsvergelijking ω 2 − 3ω + 2 = 0. De wortels van deze vergelijking zijn ω1 = 1 en ω2 = 2. De algemene oplossing is dus an = Cω1n + Dω2n = C + D2n . Is ook nog gegeven dat a0 = 1 en a1 = 2 dan kunnen we C en D bepalen door substitutie van 0 en 1 voor n in de algemene oplossing: a0 = 1 = C + D C = 0 dus a1 = 2 = C + 2D D = 1. dus de specifieke oplossing is an = 2 n . ♥

89


Voorbeeld 7.4 Bij de recurrente betrekking van Fibonacci (zie voorbeeld 7.2) voor (n > 2)

an = an−1 + an−2 hoort de vierkantsvergelijking ω 2 − ω − 1 = 0.

De wortels van deze vergelijking zijn √ √ 1+ 5 1− 5 ω1 = en ω2 = . 2 2 De algemene oplossing is dus an = Cω1n + Dω2n = C

√ !n 1+ 5 +D 2

√ !n 1− 5 . 2

Als a0 = 0 en a1 = 1 dan kunnen we C en D bepalen door substitutie van 0 en 1 voor n in de algemene oplossing: ( D = 0 C +D = 0 C + √ √ dus C − D = √25 = 1 C 1+2 5 + D 1−2 5 Hieruit volgt dat

1 1 C = √ , D = −√ . 5 5 Dus zijn de getallen van Fibonacci gegeven door " √ !n √ !n # 1+ 5 1− 5 1 . − an = √ 2 2 5 √ φn met φ = Omdat 1−2 5 < 1, geldt voor n → ∞ dat an ≈ √ 5

√ 1+ 5 2 .

♥

Geval 2: A2 + 4B = 0. De vergelijking (**) heeft e´ e´ n reële wortel ω1 = ω 2 = ω =

A 2

met multipliciteit m = 2. De recurrente betrekking (*) heeft dus een oplossing: ω n . Met stelling 7.2 zien we dat an = Cω n ook een oplossing is van (*) voor iedere C ∈ R. Dit is geen algemene oplossing want die moet van twee constanten afhangen. Dus moeten we nog een onafhankelijke oplossing vinden. We beginnen met de volgende observatie. Stel voor dat A2 + 4B = 4ε2 > 0 met een kleine ε > 0. Dan heeft (**) twee verschillende oplossingen: ω1 = ω + ε en ω2 = ω − ε.

Dan is

ω n (ω − ω2n ) 2ε 1 ook een oplossing van (*) (wegens stelling 7.2). Maar ω n (ω − ω2n ) 2ε 1

90

ω [(ω + ε)n − (ω − ε)n ] 2ε ω [(ω n + nω n−1 ε + . . .) − (ω n − nω n−1 ε + . . .)] = 2ε ω = [2nω n−1 ε + . . .] 2ε = nω n + . . . → nω n als ε → 0.

=

Kader 7.2: M AXIMAAL RITME .

AANTAL DELINGEN BIJ

E UCLIDES ’

ALGO -

Sectie 7.2 D E VERGELIJKING an = Aan−1 + Ban−2

De historisch gezien eerste serieuze toepassing van Fibonacci’s getallen was de analyse van Euclides’ algoritme door T.F. de Lagny in 1733. Het algoritme (zie kader 1.2) vindt de grootste gemene deler van twee getallen door herhaalde deling met rest. Lagny zocht een antwoord op de vraag hoe vaak je maximaal zou moeten delen wanneer het grootste getal, A, gegeven is. We draaien deze vraag eerst om: hoe groot moet A minstens zijn om een zeker aantal malen, zeg k keer, te delen? Nummer de achtereenvolgende getallen vanaf het laatste, dus zo (voor de berekening van ggd(615, 252)): 615 b7

252 b6

111 b5

30 b4

21 b3

9 b2

3 b1

0 b0

Nu geldt b0 = 0 en b1 > 1 (omdat het laatste getal de eerst optredende 0 is). Verder is bi de rest bij deling van bi+2 door bi+1 , die minstens e´ e´ n keer gaat, waaruit volgt dat bi+2 > bi+1 + bi . Hieruit volgt dat bi > ai (het ie Fibonaccigetal),√dus in het bijzonder geldt dat A = bk > ak ≈ φk √ . (Hierin is φ = 1+2 5 .) Terugrekenend kan men hieruit afleiden dat 5 √ k 6 φ log( 5A) ≈ 1.67 + 1.44 · 2 log A. Nu gaan we onderzoeken of nω n inderdaad een oplossing van (*) is voor ε = 0. Substitutie in (*) levert dat dan moet gelden

of

nω n = A(n − 1)ω n−1 + B(n − 2)ω n−2 nω 2 = n(Aω + B) − Aω − 2B.

Uit deze vergelijking volgt dat

n(ω 2 − Aω − B) = −(Aω + 2B). Zet ω =

A in de laatste vergelijking. Dit geeft: 2 2 2 A A −n +B =− + 2B . 4 2

Aangezien A2 + 4B = 0 is deze vergelijking equivalent met 0 = 0. Dus is nω n een andere oplossing van (*) die onafhankelijk van ω n is. De algemene oplossing is an = Cω n + Dnω n met constanten C, D ∈ R.

Als de startwaarden a0 en a1 bekend zijn, dan kunnen we C en D bepalen uit het stelsel Cω 0 + D · 0 · ω 0 = a0 C = a0 of Cω 1 + Dω 1 = a1 ωC + ωD = a1 Dit geeft

C = a0 , D =

a1 − a0 . ω

Geval 3: A2 + 4B < 0. De vergelijking (**) heeft nu twee complexe wortels ω1 6= ω2 : A ip −(A2 + 4B). ω1,2 = ± 2 2

91


Verder gaan we net zo te werken als in Geval 1. De recurrente betrekking (*) heeft dus twee onafhankelijke complexe oplossingen: ω1n en ω2n . Met stelling 7.2 zien we dat an = Cω1n + Dω2n een oplossing is van (*) voor alle C, D ∈ C. Dit is de algemene complexe oplossing van de recurrente betrekking (*). Als de startwaarden a 0 en a1 zijn gegeven, dan krijgen we als in Geval 1: C=

a1 − ω2 a0 ω1 a 0 − a 1 , D= , ω1 − ω 2 ω1 − ω 2

waarin ω1,2 complexe getallen zijn. Natuurlijk moet an reëel zijn voor reële ¯ = B, a A, B en a0 , a1 (A¯ = A, B ¯ 0 = a0 , a ¯1 = a1 ). Immers dan geldt ω2 = ω 1 en a1 − ω1 a0 a1 − ω 2 a0 = = D. C= ω 1 − ω2 ω2 − ω 1

Dus

an = Cω1n + Dω2n = Cω1n + C ωn1 = a ¯n zo dat an reëel is. In meer detail: ω1 = reiϕ , C = seiψ (zie hoofdstuk 6). Dan krijgen we Cω1n = srn ei(nϕ+ψ) , Cω n1 = srn e−i(nϕ+ψ) en an = 2srn cos(nϕ + ψ). Voorbeeld 7.5 Bij de recurrente betrekking an = an−1 − an−2

(n > 2).

hoort de vergelijking ω 2 − ω + 1 = (ω − ω1 )(ω − ω2 ) = 0 met ω1 =

√ √ 1 1 (1 + i 3) = eiπ/3 en ω2 = (1 − i 3) = e−iπ/3 . 2 2

De algemene oplossing is an = Aeinπ/3 + Be−inπ/3 . Met a0 = 2 en a1 = 1 komt er bij invullen van n = 0 en n = 1 A+B = 2 Aeiπ/3 + Be−iπ/3 = 1, hetgeen we kunnen herschrijven tot A+B √ 1 1 2 (A + B) + i 2 3(A − B)

an 2 1

frag replacements

3 -1

6

9

12

15

18

n

= 2 = 1.

Hieruit volgt dat A = B = 1. Zo vinden we de oplossing: nπ an = einπ/3 + e−inπ/3 = 2 cos . 3

Merk op dat hier geldt an = an+6 , dus (an ) is periodiek met periode 6.

-2

92

We vatten deze resultaten samen in de volgende stelling:

♥

Stelling 7.3 Laten A, B 6= 0, ω1,2 (complexe) constanten zijn zo dat ω 2 − Aω − B = (ω − ω1 )(ω − ω2 ) voor alle ω .

Sectie 7.3 DATAOPSLAG IN BINAIRE AVL- BOMEN

Dan zijn er (complexe) constanten C en D zo dat een oplossing van de recurrente betrekking an = Aan−1 + Ban−2 (n > 2)

wordt gegeven door Cω1n + Dω2n an = Cω n + Dnω n

7.3

als ω1 = 6 ω2 , als ω1 = ω2 = ω .

Dataopslag in binaire AVL-bomen

Een collectie data in een computer wordt vaak opgeslagen in de vorm van een binaire boom. Hierbij wordt e´ e´ n element van de collectie, de wortel, uitgekozen om bovenin de datastructuur te zitten, en de rest van de data wordt verdeeld in een linker- en een rechter deelcollectie. Links komen de elementen kleiner dan de wortel, en rechts de elementen groter dan de wortel, en de linker- en rechterdeelcollectie worden elk weer als een binaire boom georganiseerd. Het voorbeeld laat zien hoe de structuur er uit zou kunnen zien voor de collectie {2, 5, 7, 9, 10, 13, 17, 19}; eerst was 13 als wortel gekozen, daarna 9 in de linkercollectie en 17 in de rechtercollectie, etcetera. Een element kan gemakkelijk teruggevonden worden vanuit de wortel: steeds als je een element tegenkomt dat groter is dan wat je zoekt, ga je naar links, en als je een te klein element tegenkomt ga je naar rechts. Zo wordt 10 teruggevonden langs het pad 13–9–10. Als je moet zoeken langs langere paden kost het terugvinden van data natuurlijk meer tijd; daarom is het van belang de diepte van de boom te kennen, dat is de lengte van het langste pad in de boom. De voorbeeldboom heeft diepte 4 omdat het pad naar getal 7 lengte 4 heeft. De binaire boom lijkt een ingewikkeld idee, maar hij kan heel efficiënt zijn: je kunt een collectie van een miljoen elementen opslaan in een binaire boom met diepte 20! Hoe efficiënt de boom is, hangt echter sterk af van welke elementen steeds als wortel worden gekozen. Wie bijvoorbeeld steeds het kleinste getal kiest, krijgt een heel scheve boom zoals hiernaast en een boom met een miljoen elementen heeft dan diepte een miljoen! Dat lijkt een onverstandige keuze, maar door het toevoegen of verwijderen van elementen kan een boom in de loop van de tijd ”scheefgroeien”. Een mooie oplossing voor het probleem van de scheefgroei werd gevonden door twee Russen, Adelson-Velskii en Landis; we spreken dan van AVL-bomen. Een boom heeft de AVL-eigenschap, wanneer de diepte van de linkerdeelboom en de diepte van de rechterdeelboom ten hoogste 1 verschillen. Niet alleen moet dit gelden voor de twee deelbomen van de wortel van de hele boom, maar ook binnen elke deelcollectie. De eerstgegeven boom is bijvoorbeeld een AVL-boom. De wortel (13) heeft een linkerdeelboom van diepte 3 en een rechterdeelboom van diepte 2, het verschil is dus 1. Het element 9 heeft een linkerdeelboom van diepte 2 en een rechterdeelboom van diepte 1, het verschil is dus 1. Het element 17 heeft een linkerdeelboom van diepte 0 (hier zit helemaal geen data) en een rechterdeelboom van diepte 1, het verschil is dus 1. Het element 5 heeft een linkerdeelboom van diepte 1 (hier zit helemaal geen data) en een rechterdeelboom van diepte 1, het verschil is dus 0.

13 Ingang 9 5 2

17 10

19

7

19

Ingang

23 29 31 37

93


6

x

i lagen AV Li−2 AV Li−1

?

De scheefgegroeide boom is geen AVL-boom: de elementen 37 en 31 zijn nog in orde, maar 29 heeft een linkerdeelboom van diepte 0 en een rechterdeelboom van diepte 2, het verschil is dus te groot. Adelson-Velskii en Landis beweerden, dat wanneer hun idee wordt ingevoerd, de diepte van een boom maximaal evenredig is met de logaritme van het aantal elementen. Om dit in te zien stellen we ons de vraag: wat is de maximale diepte van een AVL-boom met n elementen? Net als bij de analyse van Euclides’ algoritme (kader 7.2) draaien we de vraag eerst om: wat is het minimale aantal elementen in een AVL-boom van diepte i? Noem dit aantal Mi en bedenk dat M1 = 1 en M2 = 2. Voor i > 2 moet de boom tenminste een wortel hebben en e´ e´ n van de deelbomen moet diepte i − 1 hebben: we geven de wortel als deelboom de lichtse AVL-boom van diepte i − 1. Omdat het verschil tussen de dieptes van de deelbomen niet meer dan 1 mag zijn, moet de andere deelboom tenminste diepte i−2 hebben, en we geven de wortel daarom als andere deelboom de lichtste (qua aantal elementen) AVLboom van diepte i − 2 (plaatje). De lichtste AVL-boom met diepte i bestaat dus uit een wortel en de twee vorige AVL-bomen, en voor het aantal elementen vinden we de recurrente betrekking Mi = Mi−1 + Mi−2 + 1. Door de laatste term, +1, is deze recurrente betrekking niet van het bekende type. We kunnen die term gelukkig wegwerken door een andere rij (L i ) te definiëren, waarbij Li = Mi + 1; de betrekking voor Mi geeft ons nu een bekende betrekking voor Li , als volgt: Li

= = = =

Mi + 1 definitie L Mi−1 + Mi−2 + 1 + 1 betrekking voor M (Mi−1 + 1) + (Mi−2 + 1) omschrijven Li−1 + Li−2

De beginwaarden van L zijn L1 = 2 en L2 = 3. Nu zijn 2 en 3 het derde, respectievelijk vierde Fibonaccigetal, en de betrekking voor L i kan nu opgelost i+2 φ2 ·φi . worden tot Li = ai+2 ≈ φ√5 . De oplossing voor de rij M is nu: Mi ≈ √ 5 Hieruit volgt dat als n elementen zijn opgeslagen in een AVL-boom van diepte φ2 · φk , oftewel k, dan geldt n > √ 5 k6

φ

√ ! 5 log n · 2 ≈ 1.44 · φ

2

log n − 0.33

De twee Russen hebben dus gelijk met hun bewering over de diepte van AVLbomen.

7.4

Homogene lineaire recurrente betrekkingen

Gesterkt door het succes bij het oplossen van het probleem in sectie 7.2 proberen we de algemene k-de orde lineaire homogene recurrente betrekkingen met constante coëfficiënten op te lossen, dat wil zeggen recurrente betrekkingen van het type (?) 94

an = c1 an−1 + c2 an−2 + . . . + ck an−k

(n > k)

waarbij c1 , c2 , . . ., ck gegeven constanten, en de startwaarden a0 , a1 , . . . , ak−1 bekend zijn.

Als we de startwaarden a0 , a1 , . . ., ak−1 vrijlaten, dan gelden de volgende eigenschappen (1)

als (an ) een oplossing is van vergelijking (?), dan ook (µan ) voor elke µ ∈ C, (2) als (an ) en (a0n ) oplossingen zijn van vergelijking (?), dan ook (an +a0n ).

Sectie 7.4 H OMOGENE LINEAIRE RECURRENTE BETREKKINGEN

Deze eigenschappen kunnen we net als stelling 7.2 bewijzen. Als men dus op een of andere wijze oplossingen (2) (k) (a(1) n ), (an ), . . . , (an )

van vergelijking (?) heeft gevonden, dan is ook (2) (k) (µ1 a(1) n + µ2 an + . . . + µ l an )

een oplossing van vergelijking (?), voor iedere keuze van constanten µ 1 , µ2 , . . . , µk . In het bijzonder worden oplossingen van vergelijking (?) gegeven door an(j) = ωjn , waarbij ω1 , ω2 , . . . , ω k de oplossingen zijn van de vergelijking xk − c1 xk−1 − . . . − ck−1 x − ck = 0. Als een oplossing ωj van deze vergelijking de multipliciteit mj > 1 heeft, dan zijn ook an = nωjn , an = n2 ωjn , . . . , an = nmj −1 ωjn oplossingen van vergelijking (?) (dit volgt uit corollarium 6.7). Zo vinden we k onafhankelijke oplossingen van vergelijking (?), die kunnen worden gecombineerd tot een algemene oplossing. De onbekende µ’s worden vastgelegd door de startwaarden a0 , a1 , . . ., ak−1 . Voorbeeld 7.6 Bij de recurrente betrekking an = 16an−1 − 97an−2 + 278an−3 − 380an−4 + 200an−5 met n > 5, hoort het polynoom (x − 2)3 (x − 5)2 = x5 − 16x4 + 97x3 − 278x2 + 380x − 200 met gegeven startwaarden a0 , a1 , a2 , a3 , a4 . De nulpunten van dit polynoom zijn 2 (3 maal) en 5 (2 maal), dus wordt de oplossing gegeven door an = A2n + Bn2n + Cn2 2n + D5n + En5n . Door nu voor n achtereenvolgens de waarden 0 tot en met 4 in te vullen, kan men de constanten A, B, C, D, E berekenen uit een stelsel van 5 vergelijkingen. Voor a0 = 1, a1 = 3, a2 = 9, a3 = 53, a4 = 369 vinden we zo A = B = 0, C = −1, D = 1, E = 0, dus an = −n2 2n + 5n . ♥

95


7.5

Niet-homogene lineaire recurrente betrekkingen

De volgende stap is het toevoegen van een dwangterm f (n) aan de recurrente betrekking in vergelijking (?). Dan komt er (*)

an = c1 an−1 + c2 an−2 + . . . + ck an−k + f (n)

(n > k)

waarbij c1 , c2 , . . ., ck gegeven constanten, en de startwaarden a0 , a1 , . . . , ak−1 bekend zijn. Tot nu toe hebben we alleen de zogenaamde homogene betrekking (met f (n) = 0) behandeld. In dit nieuwe niet-homogene probleem kan de oplossing van het homogene probleem goed gebruikt worden. Een mogelijkheid om hier tot tot een oplossing te komen, is het splitsen van het probleem in twee deelproblemen. Eerst proberen we een liefst zo eenvoudig mogelijke oplossing van (*) te vinden, zonder op de startwaarden te letten. Als we er in slagen om (pn ) te vinden, zo dat pn = c1 pn−1 + c2 pn−2 + . . . + ck pn−k + f (n)

(n > k),

dan lossen we vervolgens de homogene recurrente betrekking (de oorspronkelijke vergelijking (*) met weglating van de dwangterm) hn = c1 hn−1 + c2 hn−2 + . . . + ck hn−k met nieuwe startwaarden hj = aj − pj (j = 0, 1, . . . , k − 1) op. De oplossing van (*) wordt dan gegeven door an = pn + hn voor alle n. In het bovenstaande wordt (pn ) vaak een particuliere oplossing genoemd, terwijl men (hn ) de oplossing van het homogene deel noemt. Samengevat: Voor het oplossen van an = c1 an−1 + c2 an−2 + . . . + ck an−k + f (n) met n > k is het volgende een goede strategie: 1. Vind een particuliere oplossing pn voor an . 2. Vind de oplossing hn van het homogene probleem (f (n) = 0) met aangepaste startwaarden. 3. De oplossing is dan an = hn + pn . Punt 2 van deze methode is in sectie 7.3 behandeld. Het vinden van een particuliere oplossing pn bij punt 1 kan vaak met de zogenaamde methode van onbepaalde coëfficiënten. Hierbij vindt men een particuliere oplossing door pn te zoeken in de vorm van de dwangterm f (n). Bijvoorbeeld: is f (n) een polynoom, probeer dan voor pn ook een polynoom van dezelfde graad. Andere vormen zijn bijvoorbeeld (waarbij we voor de leesbaarheid polynomen alleen in de eerste regel hebben uitgeschreven):

96

type dwangterm f (n) polynoom: d0 + d1 n + . . . + dm nm (polynoom)·cn (polynoom)·cn sin(dn)

probeer voor pn ns (b0 + b1 n + . . . + bm nm ) ns ·(polynoom)·cn ns · ((polynoom)·cn cos(dn)+(polynoom)·cn sin(dn))

waarbij s het kleinste natuurlijke getal is dat zorgt dat geen term van p n een oplossing is van de homogene vergelijking. In de praktijk beginnen we met s = 0 te stellen. Lukt het daarmee niet, dan hogen we s met 1 op en proberen het opnieuw. Dit ophogen van s herhalen we tot succes volgt. Voor meer theorie hierover verwijzen we ge¨ınteresseerden naar de vraagstukken 7.25 t/m 7.29.

Sectie 7.5 N IET- HOMOGENE LINEAIRE RECURRENTE BETREKKINGEN

Voorbeeld 7.7 Vind een particuliere oplossing pn voor de recurrente betrekking an = 2an−2 + 3n. De dwangterm 3n heeft de vorm van een eerstegraads polynoom. Diezelfde vorm proberen we voor pn : pn = an + b, met a en b te bepalen constanten (”onbepaalde coëfficiënten”). Invullen van pn in de betrekking geeft: an + b = 2(a(n − 2) + b) + 3n an + b = 2an − 4a + 2b + 3n sorteren op de macht van n van iedere term geeft n(a − 2a − 3) + (b + 4a − 2b) = 0 n(−a − 3) + (4a − b) = 0 links en rechts gelijkstellen van de coëfficiënten van n1 en n0 geeft −a − 3 = 0 a = −3 dus 4a − b = 0 b = −12.

We vinden voor pn dus pn = −3n − 12. Narekenen door substitutie van pn voor an levert dat dit inderdaad een juiste oplossing is van de gegeven recurrente betrekking. ♥

Voorbeeld 7.8 Vind een particuliere oplossing pn voor de recurrente betrekking an = 3an−1 − 2an−2 + n. De dwangterm is een een eerstegraads polynoom, dus we proberen p n = an + b. Invullen levert an + b = 3(a(n − 1) + b) − 2(a(n − 2) + b) + n an + b = 3an − 3a + 3b − 2an + 4a − 2b + n sorteren op machten van n : n(a − 3a + 2a − 1) + (b + 3a − 3b − 4a + 2b) = 0 n(−1) + (−a) = 0. Dit levert dus een strijdigheid op, aangezien de coëfficiënt van n niet links en rechts gelijk kan worden gemaakt! In dit geval hogen we het getal s uit de tabel op van 0 naar 1 en proberen we nu pn = n(an + b) = an2 + bn. Invullen levert nu an2 + bn = 3(a(n − 1)2 + b(n − 1)) − 2(a(n − 2)2 + b(n − 2)) + n uitwerken en sorteren op machten van n levert tenslotte: n2 (a − 3a + 2a) + n(b + 6a − 3b − 8a + 2b − 1)+ +(−3a + 3b + 8a − 4b) = 0 n(−2a − 1) + (5a − b) = 0 gelijkstellen van de coëffici¨ dan: enten levert −2a − 1 = 0 a = − 21 dus 5a − b = 0 b = − 25 .

Dus pn = − 21 n2 − 25 n.

♥

Voorbeeld 7.9 Vind een particuliere oplossing van an = an−1 −an−2 +n 3 . 2 n

Volgens de tabel proberen we pn = 3n (an2 + bn + c). Invullen, uitwerken 2 1 0 en gelijkstellen van de coëffici¨ enten van n , n en n levert uiteindelijk op: 18 45 n 9 2 ♥ pn = 3 7 n − 49 n − 343 .

97


7.6

Voortbrengende functies

In hoofdstuk 2 zochten we bij een gegeven functie naar de coëfficiënten van de bijbehorende machtreeks (Taylorreeks) in de hoop de functie beter te kunnen begrijpen. Nu gaan we het omgekeerde doen, namelijk, bij een reeks getallen (bijvoorbeeld door een recurrente betrekking gedefinieerd) de functie bekijken met die rij als coëfficiënten in de machtreeks. Die functie heet de voortbrengende functie van de rij en kan een hulpmiddel zijn om het gedrag van de reeks beter te begrijpen. Definitie 7.4 Is (an ) een rij getallen, dan heet a(x) = gende functie van (an ).

∞ X

an xn de voortbren-

n=0

Voorbeeld 7.10 De voortbrengende functie van de eindige rij 1, 2, 1 (dus a 0 = 1, a1 = 2, a2 = 1) is 1 + 2x + x2 = (1 + x)2 . ♥ Voorbeeld 7.11 De voortbrengende functie van de rij (an ) met an = 1 voor alle n, is ∞ X

n=0

xn =

1 . 1−x

Zie hiervoor voorbeeld 2.4. Voorbeeld 7.12 De voortbrengende functie van de rij (an ) met an =

♥ 1 n!

is

∞ X 1 n x = ex . n! n=0

Zie hiervoor voorbeeld 2.5.

♥

Voorbeeld 7.13 De voortbrengende functie van de rij (an ) met an = n2 is ∞ X

n=0

n 2 xn =

x + x2 . (1 − x)3

Om dit te bewijzen merken we eerst op dat n2 xn voorkomt in de tweede afgeleide van xn . We Pkunnen dus proberen het bewijs te leveren door te kijken naar afgeleiden van xn : P n x = 1 P n−11−x 1 P n x eerste afgeleide: nx = (1−x)2 dus nx = (1−x) 2 P 2 n−2 tweede afgeleide: n(n − 1)x = (1−x)3 P 2 n−2 P n−2 2 n x − nx = (1−x) 3 P 2 n P n 2 2x n x − nx = (1−x)3 P 2 n x 2x2 +x−x2 x2 +x 2x2 = (1−x) resultaat: n x = (1−x) 3 + (1−x)2 = 3. (1−x)3

98

Voor een alternatief bewijs, zie het bewijs van corollarium 6.7. Wat daar gedaan is voor een polynoom, geldt wegens stelling 2.7 ook voor machtreeksen. De 1 inderdaad uitkomst is hier dus xf (1) (x) + x2 f (2) (x), hetgeen met f (x) = 1−x de gewenste formule levert.

Nog een andere techniek die tot dit resultaat leidt, gebruikt voorbeeld 2.4. Eerst merken we op dat n+k = n+k n k . Daarmee krijgen we

Sectie 7.6 VOORTBRENGENDE FUNCTIES

∞ ∞ X X 1 xk n+k n n n = = x , dus x . k+1 (1 − x)k+1 (1 − x) k k n=0 n=0

De sommatie inhet rechterlid van de laatste gelijkheid zou moeten lopen vanaf n = k, maar nk = 0 als n ∈ N en n < k. Verder gaat men na dat n n 2 n =2 + , 2 1 waaruit met bovenstaande volgt dat ∞ X

2 n

n x =2

n=0

∞ X n

n=0

2

n

x +

∞ X n

n=0

1

xn =

x 2x2 + 3 (1 − x) (1 − x)2

hetgeen na uitwerking ook de gewenste formule levert.

♥

Voorbeeld 7.14 De voortbrengende functie van de rij (an )n>1 met an = 1/n is ∞ X xn = − ln(1 − x). n n=1

Met stelling 2.5 volgt dat deze machtreeks convergentiestraal ρ = 1 heeft. Stel dus dat de uitkomst binnen de convergentiestraal de functie g(x) is. Toepassen van stelling 2.7 geeft dan g 0 (x) =

∞ X

xn =

n=0

1 . 1−x

Dit houdt in (zie vraagstuk vr.2.15) dat g(x) = − ln(1 − x) + C, waarin C een integratieconstante is. Invullen van x = 0 leert echter dat C = 0, waarmee de bewering is aangetoond. ♥

7.6.1 Voortbrengende functies en recurrente betrekkingen We geven een paar voorbeelden van het gebruik van voortbrengende functies bij het oplossen van recurrente betrekkingen. Voorbeeld 7.15 an = an−1 + an−2 (n > 2). Stel a(x) de voortbrengende functie van de (nog te vinden) rij (an ). Dan geldt a(x) =

∞ X

a n xn = a 0 + a 1 x +

n=0

= a0 + a1 x +

∞ X

∞ X

a n xn

n=2

(an−1 + an−2 )xn

n=2 ∞ X

= a0 + a1 x + x

n=1

a n xn + x 2

∞ X

n=0

a n xn

= a0 + a1 x + x(a(x) − a0 ) + x2 a(x),

99


dus (1 − x − x2 )a(x) = a0 + (a1 − a0 )x. We krijgen dan a(x) =

a0 + (a1 − a0 )x A B = + , 1 − x − x2 x − τ1 x − τ2

waarin τ1 en τ2 de oplossingen zijn van 1 − x − x2 = 0 en de constanten A en B worden berekend volgens de methode van breuksplitsing (doe dit zelf, zie sectie 6.8.) Wanneer we alvast aannemen dat A, B, τ1 , τ2 berekend zijn, dan komt er a(x)

B/τ2 A/τ1 − 1−(x/τ = − 1−(x/τ 1) 2) ∞ ∞ X B X (τ1 )−n xn − (τ2 )−n xn = − τA1 τ 2 n=0 n=0 ∞ X A B −n = (− (τ1 ) − (τ2 )−n )xn . τ1 τ2 n=0

Het resultaat is dus dat de oplossing van de recurrente betrekking wordt gegeven door an = −

A B (τ1 )−n − (τ2 )−n voor alle n > 0. τ1 τ2 ♥

Voorbeeld 7.16 an = an−1 + an−2 + n (n > 2). Gaan we te werk als in voorbeeld 7.15, dan vinden we (1 − x − x2 )a(x)

= a0 + (a1 − a0 )x +

∞ X

n=2

= a0 + (a1 − a0 )x − x + = a0 + (a1 − a0 − 1)x +

nxn ∞ X n

1

xn

n=0 x (1−x)2

(zie het laatste gedeelte van voorbeeld 7.13). Er komt dus a(x)

=

x a0 + (a1 − a0 − 1)x + (1 − x − x2 ) (1 − x)2 (1 − x − x2 )

=

C D E F + + + , x − τ1 x − τ2 (1 − x)2 1−x

waarin τ1 en τ2 zijn als in voorbeeld 7.15 en C, D, E, F constanten zijn die weer met breuksplitsing worden berekend. Met voorbeelden 7.15 en 2.4 vinden we tenslotte an = −

C D (τ1 )−n − (τ2 )−n + E(n + 1) + F τ1 τ2 ♥

Na deze concrete voorbeelden geven we het algemene idee van de toepassing van voortbrengende functies bij het oplossen van de lineaire recurrente betrekkingen van orde k met constante coëfficiënten en een dwangterm an = c1 an−1 + c2 an−2 + . . . + ck an−k + f (n) We stellen 100

a(x) =

∞ X

n=0

a n xn ,

(n > k).

p(x) = 1 − c1 x − c2 x2 − . . . − ck xk .

Vermenigvuldigen van p(x) met a(x) geeft wegens de recurrente betrekking het resultaat p(x)a(x) = q(x) +

∞ X

Sectie 7.6 VOORTBRENGENDE FUNCTIES

f (n)xn ,

n=k

waarin q(x) een polynoom is van graad 6 k − 1, namelijk   k−1 n X X a n − q(x) = a0 + cj an−j  xn . n=1

j=1

Heeft men nu het geluk dat de nulpunten van p(x) kunnen worden berekend en dat P∞ n n=k f (n)x een bekende functie r(x) voorstelt, dan kan wellicht met breuksplitsing de voortbrengende functie a(x) =

q(x) + r(x) p(x)

expliciet als een machtreeks worden geschreven, waaruit an volgt als de coëfficiënt van xn . Zoals de voorgaande voorbeelden laten zien, kan dit zeker als k 6 2 en f (n) een niet-negatieve gehele macht van n is. Immers dan kan men de oplossingen van P p(x) = 0 berekenen en gebruik maken van de voorbeelden 7.11 en 7.13 om f (n)xn te schrijven als een quotiënt van hanteerbare polynomen.

7.6.2 Verbanden tussen oplosmethoden Er zijn sterke verbanden tussen de oplosmethode met voortbrengende functies (zie sectie 7.6.1) en de eerder gebruikte methoden (zie sectie 7.4). In 7.4 spelen de nulpunten van het polynoom P (x) = xk − c1 xk−1 − . . . − ck−1 x − ck

een rol en in sectie 7.6.1 zijn het de nulpunten van p(x) = 1 − c1 x − c2 x2 − . . . − ck xk

die ons interesseren. Een belangrijke opmerking is hier

Lemma 7.5 Zij ck 6= 0. Dan geldt P (y) = 0 dan en slechts dan als p

1 y

= 0.

Bewijs Men rekent na dat xk p(1/x) = P (x), waaruit de bewering volgt, omdat x = 0 wegens het gegeven geen nulpunt van P (x) kan zijn. De nulpunten van p(x) zijn dus precies de inversen van de nulpunten van P (x). Dat wordt weer goed gemaakt bij de breuksplitsing, immers in de voorbeelden 7.15 en 7.16 zien we in de oplossingen negatieve machten van τ 1 en τ2 optreden! Het grote voordeel van het gebruik van voortbrengende functies is, dat corollarium 6.7 op een veel natuurlijker manier weerspiegeld wordt door de machtreeksen van (x − ω −1 )−k in de breuksplitsing.

101


7.6.3 Opmerking over formele machtreeksen Bij het werken met voortbrengende functies interesseren ons zulke dingen als de convergentiestraal van een machtreeks niet. We willen uitsluitend formeel kunnen rekenen met machtreeksen, omdat we ons voor de coëfficiënten ervan interesseren. In de wiskunde is de theorie van deze zogenaamde formele machtreeksen een heel apart vak. Een formele machtreeks ziet er in veel gevallen uit als de Taylorreeks van een concrete functie, en omgekeerd is elke Taylorreeks tevens te interpreteren als een formele machtreeks. Het voert voor dit college te ver om het verschil tussen een en een formele machtreeks uit te leggen. In een Taylorreeks P∞Taylorreeks n a x moet men x opvatten als een variabele, waarvoor reëel n n=0 P men een n of complex getal kan invullen. In een formele machtreeks ∞ a x moet n n=0 men x echter opvatten als een symbool, waarmee gerekend kan worden.

7.6.4 Een geavanceerd voorbeeld Uit het voorgaande lijkt het alsof de voortbrengende functies eigenlijk niets bijdragen aan het oplossen van recurrente betrekkingen. Toch is dat niet waar. Weliswaar helpen ze nauwelijks bij lineaire recurrente betrekkingen van orde k met constante coëfficiënten, maar er zijn recurrente betrekkingen waarvoor voortbrengende functies precies het goede gereedschap vormen. Een dergelijk voorbeeld is het tellen van het aantal binaire bomen met n inwendige knopen. Daarbij hoort de recurrente betrekking an = a0 an−1 + a1 an−2 + . . . + an−1 a0 (n > 1), met a0 = 1. Hier zien we in het rechterlid de coëfficiënt staan van xn−1 in a(x)2 . Er komt dus a(x) = 1 + xa(x)2 , met oplossing √ 2xa(x) = 1 − 1 − 4x. We gaan hier niet verder op in, maar geven een ander voorbeeld dat we wel zullen uitwerken. Voorbeeld 7.17 an = na0 + (n − 1)a1 + (n − 2)a2 + . . . + an−1 (n > 1), met a0 = 1. In het rechterlid staat de coëfficiënt van xn in het produkt ! ∞ ! ∞ X X xa(x) n n nx . an x = (1 − x)2 n=1 n=0 We krijgen dus de vergelijking a(x) − 1 =

xa(x) , (1 − x)2

die na uitwerking het volgende resultaat oplevert 1 − 2x + x2 x =1+ . 2 1 − 3x + x (σ1 − x)(σ2 − x) √ √ Hierin is σ1 = (3 + 5)/2 en σ2 = (3 − 5)/2. Breuksplitsing leidt tot a(x) =

102

A B x = + , (σ1 − x)(σ2 − x) σ1 − x σ2 − x

met A = σ1 /(σ2 − σ1 ) en B = σ2 /(σ1 − σ2 ). Werken we dit uit zoals in voorbeeld 7.15, dat komt er

Sectie 7.7 V RAAGSTUKKEN

∞ X 1 1 1 a(x) = 1 + − n xn . σ2 − σ1 n=1 σ1n σ2 Fatsoeneren brengt ons tenslotte tot √ √ (3 + 5)n − (3 − 5)n √ an = (n > 1). 2n 5 ♥

7.7

Vraagstukken

vr.7.1. Om het spaargedrag te bevorderen geeft een bank jaarlijks 8% rente op spaartegoeden die tussen 1 en 2 jaar oud zijn en 10% rente op spaartegoeden die minstens 2 jaar oud zijn. Stel een recurrente betrekking op voor het kapitaal na n jaar, aannemend dat het beginkapitaal 100 euro is en dat geen stortingen of opnamen plaatsvinden. Los de gevonden recurrente betrekking op. vr.7.2. De waarde van een bepaald tweedehands artikel wordt als volgt bepaald: na 1 jaar 80% van de nieuwwaarde, daarna vermindert de waarde elk jaar met de helft van de vermindering in het vorige jaar. Stel een recurrente betrekking op voor de waarde van een artikel dat n jaar oud is, uitgaande van een nieuwwaarde van 200 euro. Los de gevonden recurrente betrekking op en bereken de limietwaarde. vr.7.3. Van een rij (an ) is gegeven dat an het gemiddelde is van an−1 en an−2 als n > 2. Stel een recurrente betrekking op voor an en los die op voor de volgende gevallen a. a0 = 1, a1 = 1 b. a0 = 1, a1 = 3 vr.7.4. Van een rij (an ) is gegeven dat an het gemiddelde is van an−1 , an−2 en an−3 als n > 3. Bereken an als a0 = 1, a1 = 1, a2 = 1. Kunt u an ook berekenen als a0 = 1, a1 = 2, a2 = 3 ? vr.7.5. In het platte vlak, voorzien van een orthogonaal (loodrecht) assenstelsel, definiëren we een rij punten ((xn , yn )) door yn−1 − yn−2 xn−1 − xn−2 als n > 2 (xn , yn ) = xn−1 + , yn−1 − 2 2 Teken de eerste 6 punten als (x0 , y0 ) = (0, 0) en (x1 , y1 ) = (10, 0). Stel voor xn en yn aparte recurrente betrekkingen op door uit bovenstaande betrekking de ongewenste variabele te elimineren. Los de recurrente betrekkingen op en vind het “limietpunt” van de rij ((xn , yn )). vr.7.6. Stel een recurrente betrekking op voor het aantal manieren a n om n te schrijven als een som van getallen die elk 1 of 2 zijn. Bijvoorbeeld: a4 = 5: 2 + 2, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 1 + 1 + 1 + 1. Bereken an .

103

7 Recurrente betrekkingen

Recommend Documents