WisFaq!

Omzetten in directe formule

Hoe zet je de volgende recursieve formule om in een directe formule?

T(n+1)=(Tn·g)-a·n

cindy
18-1-2004

Antwoord

Het is de term "-an" waar je waarschijnlijk even de wenkbrouwen bij fronst. Het zou dus leuk zijn moesten we die term kunnen laten verdwijnen, want dan zou er een veel eenvoudigere vergelijking komen te staan.

Laten we eens niet onmiddellijk op zoek gaan naar een formule voor T(n) maar eerst voor een nieuwe rij, U(n), die aan T(n) is gekoppeld door

T(n) = U(n) + (rn+s)

met r en s getallen die we nu gaan proberen vastleggen. Vervang eerst eens de T's in U's in de recursieve betrekking:

U(n+1) + (r(n+1)+s) = g [U(n) + (rn+s)] - an
U(n+1) = gU(n) + [ n(gr-r-a) + (gs-r-s) ]

Wat tussen vierkante haken staat zijn we liever kwijt dan rijk. Kunnen we dat door een gepaste keuze van r en s bekomen? Die r en s moeten dan voldoen aan

gr-r-a=0 ® r=a/(g-1)
gs-r-s=0 ® s=a/(g-1)²

Merk op dat dat alleen lukt als g¹1. De vergelijking die in dat geval overblijft is U(n+1)=gU(n), met als oplossing U(n)=gⁿU(0). Voor T(n) komt er dan

T(n) = gⁿU(0) + an/(g-1) + a/(g-1)²

Uit de transformatieformule volgt ook nog dat T(0)=U(0)+s, zodat we uiteindelijk bekomen dat

T(n) = gⁿ[T(0)-a/(g-1)²] + an/(g-1) + a/(g-1)²

Rest ons nog het geval waarin g *wel* gelijk is aan 1. Probeer dat zelf eens op een gelijkaardige manier, alleen zal je nu een extra term in de transformatie moeten opnemen

T(n) = U(n) + [rn²+sn+v]

Door nu weer de opgave in T(n) om te zetten naar een in U(n) en de getallen r, s en v zo te kiezen dat al wat lastig is wegvalt, bekom je de oplossing voor het geval g=1. Lukt het zo?

cl
19-1-2004