Joachim Mohr   Mathematik Musik Delphi
      Die Binet'sche Formel

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

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
Formel
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).

Homogene lineare rekursive Folgen 2. Grades ...

. . . sind von der Form an = p·an-1 + q·an-2.

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 ∎

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

Die Binetsche 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