Følger og rekursive formler

En følge er en ordnet liste af tal, hvor hvert element har en bestemt plads. Man kan beskrive en følge enten ved en eksplicit formel eller ved en rekursiv formel.

Når en følge defineres rekursivt, afhænger det næste led af et eller flere af de foregående led.

 

Eksempel på en simpel rekursiv følge

Vi kan definere en følge, hvor hvert led er dobbelt så stort som det forrige:

 

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

 

Her er \( \large a_{0} = 1 \) startpunktet. Ud fra formlen får vi

 

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

 

 

Rekursiv formel

I en rekursiv formel beskrives et led ud fra tidligere led. For at komme i gang må man kende et eller flere startværdier, kaldet initialbetingelser.

 

1. ordens rekursion

En 1. ordens rekursion betyder, at hvert led kun afhænger af det forrige led. Et eksempel er

 

$$ \large a_{n} = 3 \cdot a_{n-1}, \quad a_{0} = 2 $$

 

Her ganges hvert led med 3 i forhold til det forrige. Følgen bliver

 

$$ \large 2, \; 6, \; 18, \; 54, \ldots $$

 

2. ordens rekursion

En 2. ordens rekursion betyder, at hvert led afhænger af de to foregående led. Det mest kendte eksempel er Fibonacci-følgen:

 

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

 

Her er hvert led summen af de to foregående. Følgen begynder som

 

$$ \large 0, \; 1, \; 1, \; 2, \; 3, \; 5, \; 8, \; 13, \ldots $$

 

Der findes mange andre eksempler på 2. ordens rekursioner. Her er et, hvor hvert led findes ved at gange det forrige med 2 og trække det næstforrige fra:

 

$$ \large a_{n} = 2 \cdot a_{n-1} - a_{n-2}, \quad a_{0} = 1, \quad a_{1} = 2 $$

 

Hvis vi indsætter de første værdier, får vi

 

$$ \large a_{2} = 3, \quad a_{3} = 4, \quad a_{4} = 5, \quad a_{5} = 6, \ldots $$

 

I dette tilfælde giver rekursionen en simpel aritmetisk udvikling, selv om den oprindelige formel ser mere kompliceret ud.

 

Eksplicit formel

Her kan man faktisk finde en eksplicit formel, der beskriver hele følgen direkte:

 

$$ \large a_{n} = n + 1 $$

 

Dette viser, at rekursive og eksplicitte former ofte hænger tæt sammen. En tilsyneladende kompleks rekursiv definition kan gemme på en meget enkel eksplicit formel.

 

 

Terminologi

I arbejdet med rekursive formler bruges nogle faste begreber:

 

• Initialbetingelser: de første værdier, der sætter følgen i gang.
• Rekursionsgrad: hvor mange tidligere led der bruges til at bestemme det næste (fx 1. ordens eller 2. ordens).
• Basis: de første trin i definitionen, som resten bygges på.

 

Disse begreber går igen i alle typer af rekursive definitioner og gør det lettere at arbejde systematisk med dem.

 

 

Opsummering

Rekursive formler er nyttige til at beskrive strukturer, hvor hvert nyt led vokser ud af de foregående. De giver et klart billede af sammenhængen mellem tallene, men kræver at man kender de tidligere led for at kunne fortsætte. Ofte kan man senere finde en eksplicit formel, som giver en hurtigere måde at beregne direkte på.

Forståelsen af forskellen mellem 1. og 2. ordens rekursioner, og deres forhold til eksplicitte løsninger, er et vigtigt første skridt i arbejdet med rekursive metoder.