WisFaq!

Recursieve formule van een rij met als directe formule een breuk

Bestaan er voor directe formules in de vorm van breuken recursieve formules? Bijv. u(n)=10/(u(n-1)=2)

Piet
1-6-2006

Antwoord

Uit je bijkomende uitleg haal ik dat je je afvraagt of je van recursievergelijkingen 'met breuken' de directe formules kan vinden. Helaas, er bestaat zeker geen algemene methode om recursievergelijkingen op te lossen. Voor bepaalde speciale vormen zijn die methoden er wel. Bijvoorbeeld voor lineaire recursievergelijkingen met constante coefficienten, zoals

u(n) = 3 u(n-1) + 4 u(n-2) + 7 u(n-3)

De rij van Fibonacci is daar een voorbeeld van. De oplossingsmethode vind je onder andere hier.

Trouwens, Maple, een bekend wiskundepakket, lijkt ook niet in staat iets van jouw vergelijking te maken. Mij is het wel gelukt vergelijkingen van de vorm die je opgeeft op te lossen, al gaat het misschien een beetje boven je petje.

u(n) = a / [b + c u(n-1)], voor n$\geq$1, met u(0) gegeven.

Eigenlijk een beetje met jouw hulp, omdat ik eerst je vraag verkeerd had begrepen. Ik dacht dat je vraag iets te zien het met de vraag of (en wanneer) de oplossingen voor u(n) rationale getallen, dus breuken, zijn. Ik ging aantonen dat als je een rationaal getal in de vergelijking stopt, er zeker weer een rationaal getal uit komt. Zo kwam ik dus op het idee u(n) = T(n)/N(n) (T staat voor teller, N voor noemer) te stellen, zonder evenwel te eisen dat T(n) en/of N(n) gehele getallen moeten zijn. De vergelijking wordt dan

T(n)/N(n) = a / [b + c T(n-1)/N(n-1)], voor n$\geq$1

Voor de beginwaarde van het oorspronkelijke probleem geldt

u(0) = T(0)/N(0)

Hieruit zijn T(0) en N(0) niet eenduidig te bepalen (bvb. 2 = 6/3 = 8/4 = 14/7 = ...), dus laat ik een van beide zelf kiezen: ik stel N(0)=1, zodat T(0)=u(0). Herwerken van de vergelijking geeft

T(n)/N(n) = a N(n-1) / [b N(n-1) + c T(n-1)], voor n[$>$=1]

Aan de vergelijking zal zeker voldaan zijn als de tellers aan elkaar gelijk zijn en de noemers ook (hoewel het omgekeerde niet waar is). Dus als ik T(n) en N(n) kan vinden die voldoen aan

vgl₁: T(n) = a N(n-1), n[$>$=1]
vgl₂: N(n) = b N(n-1) + c T(n-1), n[$>$=1]

dan zullen de waarden voor T(n)/N(n) oplossingen zijn voor het oorspronkelijke probleem. Twee vergelijkingen die lineair zijn met constante coefficienten, joepie, maar ze zijn jammer genoeg gekoppeld: T(n) en N(n) komen in beide vergelijkingen voor, terwijl ik ze liever gescheiden heb. Door vgl₁ in vgl₂ te stoppen en die laatste te vermenigvuldigen met a, komt er

vgl₁: T(n) = a N(n-1), n[$>$=1]
vgl₂: T(n+1) = b T(n) + ac T(n-1), n[$>$=1]

Vgl₂ bevat nu nog enkel waarvan van T(n) en kan worden opgelost. De vergelijking is van tweede orde (er wordt twee stappen teruggegaan in de tijd, zoals bij Fibonacci), dus er zijn twee waarden nodig om de boel in gang te zetten. T(0)=u(0) hadden we al gevonden, en volgens vgl₁ moet T(1)=aN(0)=a, want N(0) hadden we 1 gekozen.

Voor een concrete opgave (de getallen zijn iets 'mooier' als ik deze opgave neem ipv de jouwe) met a=2, b=5, c=-3 en u(0)=2, dus

u(n) = 2 / [5 - 3 u(n-1)] met u(0) = 2

bekom je met de methode uit de link:

T(n) = 4.2ⁿ - 2.3ⁿ = 2ⁿ⁺² - 2.3ⁿ

Uit vgl₁ volgt dan ook wat N(n) moet zijn

N(n) = (1/a)T(n+1) = ¹/₂(4.2ⁿ⁺¹ - 2.3ⁿ⁺¹) = 2ⁿ⁺² - 3ⁿ⁺¹

De oplossing van het oorspronkelijke probleem is dus

u(n) = T(n)/N(n) = (2ⁿ⁺² - 2.3ⁿ) / (2ⁿ⁺² - 3ⁿ⁺¹)

De eerste waarden zijn 2, -2, 2/11, 22/49, 98/179, ... en dat lijkt te kloppen met de recursievergelijking.

PS: Naar welke waarde streeft deze rij? Hoe had je die waarde uit de opgave kunnen halen, zonder de directe formule voor u(n) te moeten bepalen?

cl
4-6-2006