Rekurensrelasjon

[Gjest]

Hvordan regner jeg dette:

a0 = 3, a1 = 2, an = 3an-1 - 2an-2 for n >2

[Solar Plexsus]

Vi har gitt den rekursive likningen

(1) a[sub]n[/sub] = 3a[sub]n-1[/sub] - 2a[sub]n-2[/sub]

med initialbetingelsene

(2) a[sub]0[/sub] = 3, a[sub]1[/sub] = 2.

Dersom a[sub]n[/sub] = c*r[sup]n[/sup] der c og r er konstanter forskjellig fra 0, får vi ved å sette dette inn i (1) at

c*r[sup]n[/sup] = 3cr[sup]n-1[/sup] - 2cr[sup]n-2[/sup]

c*r[sup]n-2[/sup](r[sup]2[/sup] - 3r + 2) = 0

(r - 1)(r - 2) = 0

r = 1 eller r = 2.

Altså er a[sub]n[/sub] = c*1[sup]n[/sup] = c og a[sub]n[/sub] = c*2[sup]n[/sup] to løsninger av (1). Dermed blir også a[sub]n[/sub] = c[sub]1[/sub] + c[sub]2[/sub]*2[sup]n[/sup] en løsning av (1). Vha. av initialbetingeksene (2) får vi at

3 = a[sub]0[/sub] = c[sub]1[/sub] + c[sub]2[/sub],
2 = a[sub]1[/sub] = c[sub]1[/sub] + 2c[sub]2[/sub],

som gir c[sub]1[/sub]= 4 og c[sub]2[/sub] = -1. Så løsningen av rekursive likningen (1) med initialbetingelsene (2) blir

a[sub]n[/sub] = 4 - 2[sup]n[/sup].