Eksplicit løsning af rekursive formler
Når en følge er defineret ved en rekursiv formel, kan det være besværligt at beregne et vilkårligt led, fordi man hele tiden skal kende de forrige. Derfor leder man ofte efter en eksplicit løsning, hvor hvert led kan beregnes direkte ud fra \( \large n \).
Fra rekursiv til eksplicit
En almindelig metode er at skrive de første led ud og prøve at finde et mønster. Ofte afslører de første beregninger en sammenhæng, som kan generaliseres.
Eksempel 1
Vi ser på følgen
$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$
De første værdier er
$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16 $$
Mønstret er klart: hvert led er en potens af 2. Den eksplicitte formel er
$$ \large a_{n} = 2^n $$
Eksempel 2
Vi ser på følgen
$$ \large a_{n} = 2 \cdot a_{n-1} + 1, \quad a_{0} = 1 $$
De første værdier bliver
$$ \large a_{1} = 3, \quad a_{2} = 7, \quad a_{3} = 15, \quad a_{4} = 31 $$
Her ser vi mønstret: \( \large a_{n} = 2^{\,n+1} - 1 \). Dette kan bevises ved induktion eller ved at “pakke rekursionen ud” trin for trin.
Pakke rekursionen ud
I stedet for kun at gætte mønstret kan man forsøge at erstatte flere gange i formlen. For eksempel gælder
$$ \large a_{n} = 2 \cdot a_{n-1} + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2 \cdot (2 \cdot a_{n-2} + 1) + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2^2 \cdot a_{n-2} + 2 + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2^3 \cdot a_{n-3} + 2^2 + 2 + 1 $$
Fortsætter vi dette mønster helt tilbage til \( \large a_{0} = 1 \), får vi
$$ \large a_{n} = 2^n \cdot a_{0} + (2^n - 1) $$
Da \( \large a_{0} = 1 \), bliver resultatet
$$ \large a_{n} = 2^n + 2^n - 1 \quad \Leftrightarrow $$
$$ \large a_{n} = 2^{\,n+1} - 1 $$
Eksempel på en 2. ordens rekursion
Vi ser nu på en følge, der afhænger af de to foregående led:
$$ \large a_{n} = a_{n-1} + a_{n-2}, \quad a_{0} = 2, \quad a_{1} = 3 $$
De første led bliver:
$$ \large a_{2} = 5, \quad a_{3} = 8, \quad a_{4} = 13, \quad a_{5} = 21, \ldots $$
For at finde en eksplicit formel bruger vi metoden med karakteristiske rødder. Vi gætter på en løsning af formen:
$$ \large a_{n} = r^n $$
Hvorfor netop dette gæt?
Rekursionen er lineær og har konstante koefficienter.
Når et led altid er en linearkombination af et fast antal tidligere led, er det naturligt at prøve en eksponentiel form \( \large r^n \). Hvis vi indsætter dette gæt, reduceres hele rekursionen til en ligning i \( \large r \), der ikke afhænger af \( \large n \).
Det betyder, at hele rekursionen kan opfyldes af en geometrisk følge, hvor forholdet mellem to på hinanden følgende led er konstant.
Andre gæt, som for eksempel \( \large n^\alpha \), ville ikke kunne opfylde rekursionen for alle \( \large n \).
Indsat i rekursionen giver dette:
$$ \large r^n = r^{n-1} + r^{n-2} $$
Dividerer vi med \( \large r^{\,n-2} \) (for \( \large r \neq 0 \)), får vi
$$ \large r^2 = r + 1 $$
Dette kaldes den karakteristiske ligning. Den kan omskrives til:
$$ \large r^2 - r - 1 = 0 $$
Med den kvadratiske formel finder vi diskriminanten:
$$ \large \Delta = (-1)^2 - 4 \cdot 1 \cdot (-1) \quad \Leftrightarrow $$
$$ \large \Delta = 1 + 4 \quad \Leftrightarrow $$
$$ \large \Delta = 5 $$
Heraf kommer kvadratroden af 5. Løsningerne bliver:
$$ \large r_1 = \frac{1 + \sqrt{5}}{2}, \quad r_2 = \frac{1 - \sqrt{5}}{2} $$
Dermed er den generelle løsning
$$ \large a_{n} = C_1 \cdot r_1^n + C_2 \cdot r_2^n $$
Vi bestemmer konstanterne ud fra startbetingelserne:
$$ \large a_{0} = 2 = C_1 + C_2 $$
$$ \large a_{1} = 3 = C_1 \cdot r_1 + C_2 \cdot r_2 $$
Heraf fås:
$$ \large C_1 = \frac{1 + \sqrt{5}}{\sqrt{5}}, \quad C_2 = \frac{\sqrt{5} - 1}{\sqrt{5}} $$
Den eksplicitte formel bliver derfor:
$$ \large a_{n} = \frac{1 + \sqrt{5}}{\sqrt{5}} \cdot \left(\frac{1 + \sqrt{5}}{2}\right)^n \;+\; \frac{\sqrt{5} - 1}{\sqrt{5}} \cdot \left(\frac{1 - \sqrt{5}}{2}\right)^n $$
Med denne formel kan man beregne ethvert led direkte. For eksempel giver \( \large n = 5 \):
$$ \large a_{5} = 21 $$
Opsummering
En eksplicit løsning gør det muligt at springe direkte til led nummer \( \large n \) uden at beregne alle de tidligere. Man finder ofte formlen ved at observere et mønster eller ved at pakke rekursionen ud. I mere avancerede tilfælde, som ved 2. ordens rekursioner, kan man bruge metoden med karakteristiske rødder. Mange rekursive formler kan på den måde omskrives til en enkel eksplicit form, som både giver indsigt i strukturen og gør beregningen lettere.