Start Mathematik
FAQ Mathematik
Lineare Rekursionen
Gebrochen Lineare Rekursionen
Die Binet'sche Formel I
Die Binet'sche Formel II
Homogene lineare rekursive Folgen 1. Grades ...
. . . sind von der Form an = p·an-1.
Ein geschlossener Ausdruck für an ist schnell gefunden und mit Hilfe der
vollständigen Induktion bewiesen.
an = pn·a0
Beispiel:
a =3 a = 2·a (n>0)
0 n n-1
n
Also: a =3, a =6, a = 12, a = 24 ... a =2 ·3
0 1 2 3 n
Lineare rekursive Folgen 1. Grades ...
. . . sind von der Form an = p·an-1 + c.
a0 = a (Anfangswert)
a1 = p·a + c
a2 = p·(p·a + c) + c = p2·a + c·(p+1)
a3 = p·(p2·a + c·(p+1)) + c = p3·a + c(p2 + p + 1)
. . . (man ahnt schon wie es weitergeht)
an = pn·a + c(1 + p + p2 + ... + pn-1)
Die geometrische Reihe kann durch einen geschlossenen Ausdruck dargestellt werden.
Somit ist
Kopierbar dargestellt:
an = p^n*a + c*((1-p^n)/(1-p)) (p≠1)
Beweisen kann man die Formel leicht mit Hilfe der vollständigen Induktion.
(Für p=1 ist an = a + n·c).
Beispiel: Zum Anfangskapital 1000 kommt jedes Jahr eine weiter Einzahlung von 100 hinzu (Zins 5%).
a =1000 a =1,05·a + 100 (n > 1)
0 n n-1
Also: a = 1000, a = 1150, a = 1308, a = 1473, ... ,
0 1 2 3
n
n 1,05 - 1
a = 1,05 ·1000 + 100·————————
n 0,05
Gebrochen lineare rekursive Folgen
Idee: Ken Pledger in de.sci.mathematik (Mai 2009)
k1*b +k2
n-1
Wir können die Rekursion b = k0, b = ——————————
0 n b + k3
n-1
n
zurückführen auf die Folge a =p·a mit a = p ·a (siehe oben).
n n-1 n 0
r·a +s
n
Dazu verwenden wir die Substitution b = ———————
n a +1
n
Dies führt auf die Gleichung
b ·(-rp+s) + r(ps-s)
n-1
b = ——————————————————————
n b ·(1-p)+(ps-r)
n-1
Wir müssen also folgendes Gleichungssystem lösen
k1=(s-r*p)/(1-p)
k2=-r*s
k3=(p*s-r)/(1-p)
Lösung:
s=(k1-k3)/2+1/2*sqrt((k1-k3)^2+4*k2)
r=-k2/s
p=(-k2+s*k3)/(s*(k3+s))
r·a + s s-k0
Aus b = ——————— mit a = a und b = k0 folgt a = ————
0 a + 1 0 0 k0-r
n
r·a·p +s
und b = —————————
n n
a·p + 1
Rechenschema:
k0= ...
k1= ...
k2= ...
k3= ...
s=(k1-k3)/2+1/2*sqrt((k1-k3)^2+4*k2)
r=-k2/s
p=(-k2+s*k3)/(s*(k3+s))
a=(s-k0)/(k0-r)
bn=(r*a*p^n+s)/(a*p^n+1)
Beispiel a)
3b + 2
n-1
b = 1/2, b = ———————— (n>0)
0 n b + 2
n-1
7 31 127 511
b =1/2, b = -, b = ——, b = ———, b = ———, ...
0 1 5 2 17 3 65 4 257
Hier ist k0=1/2, k1=3, k2=2 und k3=2.
Dann berechnet sich:
s=(k1-k3)/2+1/2*sqrt((k1-k3)^2+4*k2)=2
r=-k2/s=-1
p=(-k2+s*k3)/(s*(k3+s))=1/4
a=(s-k0)/(k0-r)=1
und somit
n
2·4 - 1
b = ———————— (n≥0)
n n
4 + 1
Beispiel b):
1
b = 1; b = ——————— (n>0)
0 n b + 1
n-1
Aus k0=1, k1=0, k2=1 und k3=1 folgt
s=1/2*sqrt(5)-1/2
r=-1/2-1/2*sqrt(5)
p=-3/2+1/2*sqrt(5)
a=-7/2+3/2*sqrt(5)
Kopierbar:
bn= (-3*(-3+sqrt(5))^n+sqrt(5)*(-3+sqrt(5))^n-2^(1+n))/(-4*(-3+sqrt(5))^n+2*sqrt(5)*(-3+sqrt(5))^n-2^n*(1+sqrt(5)))
(n≥0)
Beispiel c):
b + 2 1/3·b + 2/3
n-1 n-1
b =5, b = ————————— = ————————————— (n>0)
0 n 3·b + 7 b + 7/3
n-1 n-1
7 51 401
b = 5, b = ——, b = ———, b = ————, ...
0 1 22 2 175 3 1378
n
a·r·p +s
b = ———————— (n≥0) mit
n n
a·p + 1
a=1/3*(-18+sqrt(15))*(-3+sqrt(15))/(-13+5*sqrt(15)),
r=-1-1/3*sqrt(15),
s=1/3*sqrt(15)-1 und
p=(-27+7*sqrt(15))/(-3+sqrt(15))/(4+sqrt(15))
Kopierbar dargestellt:
bn = 2/3*(-18*(-27+7*sqrt(15))^n+(-27+7*sqrt(15))^n*sqrt(15)-57*(3+sqrt(15))^n+14*sqrt(15)*(3+sqrt(15))^n)/(-23*(-27+7*sqrt(15))^n+7*(-27+7*sqrt(15))^n*sqrt(15)+13*(3+sqrt(15))^n-5*sqrt(15)*(3+sqrt(15))^n);
(n≥0)
Beispiel d):
b + c 1/c·b +1
n-1 n-1
b = c, b = ————————— = —————————— (n>0)
0 n c·b + 1 b + 1/c
n-1 n-1
Mit k0=c, k1=1/c, k2=1 und k3=1/c ergibt sich
n+1 n+1
1-c 1-c (1+c) - (1-c)
s=1, r=-1, p=——— und a= ——— und damit b =—————————————————— (n≥0)
1+c 1+c n n+1 n+1
(1+c) + (1-c)
Homogene lineare rekursive Folgen 2. Grades ...
... sind von der Form
an = p·an-1 + q·an-2.
und eine Verallgemeinerung der "Binet'sche Formel" (siehe unten).
Man findet folgendermaßen für an einen geschlossenen Ausdruck:
Bestimme die beiden Lösungen x1 und x2der charakteristischen Gleichung
x2 - p·x - q = 0
Dann ist an = c1x1n + c2·x2n
,
wobei sich die Koeffizienten c1 und c2 aus den Anfangsgleichungen
a0 = c1 + c2 und
a1 = c1·x1 + c2·x2
ergeben.
Beweis über die starke vollständige Induktion:
I. Induktionsanfang: ist nach Voraussetzung erfüllt.
(Koeffizienten c1 und c2 werden ja gerade so bestimmt, dass
die Formel für a0 und a1 erfüllt ist.)
II. Induktionsschritt. Sei für n > 1 gültig:
an = c1x1n + c2·x2n
und
an-1 = c1x1n-1 + c2·x2n-2.
Zu zeigen ist: an+1 - c1x1n+1 - c2·x2n+1 = 0
Nachweis:
an+1 - c1x1n+1 - c2·x2n+1
=p·an-1 + q·an-2 - c1x1n+1 - c2·x2n+1
=p·(c1x1n-1 + c2·x2n-1)
+q·(c1x1n-2 + c2·x2n-2)
- c1x1n+1 - c2·x2n+1
= -x1n-2·c1·(x12-p·x1-q)
-x2n-2·c2·(x22-p·x2-q)
= -x1n-2·c1·0 - x2n-2·c2·0 = 0 q.e.d.
a) Beispiel: Fibonaccizahlen
Die Fibonaccizahlen f(n) sind definiert durch
f(0) = 0
f(1) = 1
f(n)= f(n-1) + f(n-2) für n > 1
Die charakteristische Gleichung x2 - x - 1 = 0 hat die Lösungen
- -
1 + √5 1 - √5
x = —————— und x = ——————
1 2 2 2
Mit 0 = c + c und 1 = c ·x + c ·x
1 2 1 1 2 2
1 - 1 -
ergibt sich c = -·√5 und c = - -·√5
1 5 2 5
und somit die
Die Binet'sche Formel
Kopierbar dargestellt:
f(n) = 1/5*((1/2+1/2*sqrt(5))^n-(1/2-1/2*sqrt(5))^n)*sqrt(5)
b) Zweites Beispiel
Die Folge sei definiert durch
a0 = 1, a1 = 0 und an = 1/2·(an-1 + an-2) für n > 1
Die charakteristische Gleichung 2x2 - x - 1 = 0 hat die Lösungen
x1 = 1 une x2 = - 1/2.
Mit den Anfangswerten errechnit sich
1 2 1 n
a = - + -·(- -) für n = 0,1,2 ...
n 3 3 2
1 1 3 5 11 21 43 1
Es ergibt sich die Folge 1, 0, -, -, -, ——, ——, ——, ——— mit dem Grenzwert -
2 4 8 16 32 64 128 3
