WisFaq!

Recursieve betrekking

Hallo,
Ik heb een vraag over de volgende recursierelatie:

x_n = Ax_n + B

met algemene oplossing:

x_n = Aⁿ(x₀-^B/_1-A) + ^B/_1-A als A¹1

(Als A = 1 dan triviaal: x_n = x₀ + nB)

1) Nu is mijn vraag: Hoe kan men deze algemene oplossing vinden? Heb al wat geprobeerd met inductie en limieten maar kom niet echt verder.

2) Is er een algemene strategie om een oplossing van een recursierelatie te vinden in termen van x₀ en n (als deze bestaat)?

Groeten,
Thomas

Thomas
10-11-2011

Antwoord

De recursierelatie luidt anders dan u hebt opgeschreven, namelijk:

x_n+1 = Ax_n + B.

Dus x₁ = Ax₀ + B en

x₂ = Ax₁ + B = A(Ax₀ + B)+B =
A²x₀ + AB + B = A²x₀ +(A+1)B, en

x₃ = Ax₂ + B = A(A²x₀ +(A+1)B)+B = A³x₀ + A(A+1)B + B = A³x₀ + (A²+A+1)B

Bereken nu zelf x₄ en daarna eventueel nog x₅.

U ziet weldra (en kunt met inductie bewijzen) dat

x_n = Aⁿx₀ + (A^n-1+A^n-2+..+A+1)B = Aⁿx₀ + B(Aⁿ-1)/(A-1), en dat kan men eenvoudig herleiden tot de oplossing die u geeft.

Een algemene strategie voor het oplossen van een recursierelatie kan ik u niet geven, maar het loont altijd de moeite om eerst de eerste termen uit te rekenen.

hr
11-11-2011