PDF herunterladen
PDF herunterladen
Bei dem Versuch, eine Formel für bestimmtee mathematische Folgen zu finden, ist ein üblicher Zwischenschritt, den n-ten Term nicht als Funktion von n, sondern als Funktion von früheren Folgegliedern zu bestimmen. Zum Beispiel wäre es schön, eine Formel in geschlossener Form für den n-ten Term der Fibonacci-Folge zu haben, aber manchmal hat man nur eine Rekurrenzgleichung, nämlich, dass jeder Term der Fibonacci-Folge die Summe der beiden vorhergehenden Terme ist. In diesem Artikel werden verschiedene Methoden zur Ableitung einer Formel in geschlossener Form aus einer Rekurrenzgleichung gezeigt.
Vorgehensweise
-
Lass uns eine arithmetische Folge wie 5, 8, 11, 14, 17, 20, .... betrachten.
-
Da jeder Term um 3 größer als der vorhergehende ist, kann es als Rekurrenz wie folgt geschrieben werden.
-
Jede Rekurrenzgleichung der Form a n = a n-1 + d ist eine arithmetische Folge.
-
Schreibe die geschlossene Form der Formel für eine arithmetische Folge, möglicherweise mit Unbekannten, wie gezeigt.
-
Bestimme die Unbekannten mit Hilfe der Anfangswerte. In diesem Fall, da 5 der 0-te Term ist, ist die Formel a n = 5 + 3n. Wenn wir stattdessen 5 als ersten Term hätten, dann wäre unsere Formel a n = 2 + 3n.Werbeanzeige
-
Lass uns eine arithmetische Folge wie 3, 6, 12, 24, 48, .... betrachten.
-
Da jeder Term das Doppelte des vorhergehenden ist, kann es als Rekurrenz wie folgt geschrieben werden.
-
Jede Rekurrenzgleichung der Form a n = r * a n-1 ist eine geometrische Folge.
-
Schreibe die geschlossene Form der Formel für eine geometrische Folge, möglicherweise mit Unbekannten, wie gezeigt.
-
Bestimme die Unbekannten mit Hilfe der Anfangswerte. In diesem Fall, da 3 der 0-te Term ist, ist die Formel a n = 3*2 n . Wenn wir stattdessen 3 als ersten Term hätten, dann wäre unsere Formel a n = 3*2 (n-1) .Werbeanzeige
-
Lass uns die Folge 5, 0, -8, -17, -25, -30, ... , gegeben durch die Rekursion a n = a n-1 + n 2 - 6n betrachten.
-
Jede Rekursion, die die gezeigte Form hat, bei der p(n) ein Polynom in n ist, hat eine polynomiale Formel in geschlossener Form mit einem Grad, der um eins größer ist als der Grad von p.
-
Schreibe die allgemeine Form eines Polynoms des gewünschten Grades. In diesem Beispiel ist p quadratisch, deshalb brauchen wir ein kubisches Polynom, um die Folgenglieder der Folge a n darzustellen.
-
Da ein allgemeines kubisches Polynom vier unbekannte Koeffizienten hat, brauchen wir vier Werte, um das resultierende Gleichungssystem zu lösen. Es ist egal, welche vier, also lass uns die Terme 0, 1, 2 und 3 nehmen. Wenn wir die Rekursion rückwärts laufen lassen, um den -1-ten Term zu bestimmen, dann werden damit vielleicht einige Berechnungen leichter, aber es ist nicht nötig.
-
Löse entweder das resultierende Gleichungssystem mit deg(p)+2 Gleichungen und deg(p)=2 Unbekannten oder passe ein Lagrange-Polynom an die deg(p)+2 bekannten Punkte an.
- Wenn der 0-te Term einer der Terme ist, die wir genommen haben, um die Koeffizienten zu bestimmen, dann haben wir damit den konstanten Term des Polynoms und können das System sofort auf deg(p)+1 Gleichungen mit deg(p)+1 Unbekannten reduzieren, wie gezeigt.
-
Schreibe die geschlossene Formel für a n als Polynom mit bekannten Koeffizienten.Werbeanzeige
-
Dies Ist die erste Methode, die die Fibonacci-Folge in der Einführung lösen kann, aber die Methode löst jede Rekurrenzgleichung, bei der der n-te Term eine Linearkombination der vorhergehenden k Terme ist. Lass es uns an dem anderen gezeigten Beispiel, dessen erste Terme 1, 4, 13, 46, 157, .... sind, probieren.
-
Schreibe das charakteristische Polynom der Rekurrenz hin. Wir bekommen es, indem wir jedes a n in der Rekurrenz durch x n ersetzen und durch x (n-k) teilen, wobei wir ein Polynom vom Grad k mit einem nicht verschwindenden konstanten Term erhalten.
-
Löse das charakteristische Polynom. In diesem Fall hat das charakteristische Polynom den Grad 2, und wir können die quadratische Formel anwenden, um die Nullstellen zu bestimmen.
-
Jeder Ausdruck, der die gezeigte Form hat, löst die Rekurrenzgleichung. Die c i sind Konstanten und die Basen der Exponential-Terme sind die Lösungen von obigem charakteristischem Polynom. Dies kann durch Induktion bewiesen werden.
- Wenn das charakteristische Polynom eine mehrfache Nullstelle hat, kann dieser Schritt etwas modifiziert werden. Wenn r eine Nullstelle der Vielfachheit m ist, nimm (c 1 r n + c 2 nr n + c 3 n 2 r n + ... + c m n m-1 r n ) anstelle von (c 1 r n ). Zum Beispiel genügt die Folge, die mit 5, 0, -4, 16, 144, 640, 2240, ... anfängt, der Rekurrenzgleichung a n = 6a n-1 - 12a n-2 + 8a n-3 . Das charakteristische Polynom hat eine dreifache Nullstelle bei 2 und die Formel in geschlossener Form ist a n = 5*2 n - 7*n*2 n + 2*n 2 *2 n .
-
Bestimme die c i , die den gegebenen Anfangsbedingungen genügen. Genau wie bei dem Polynom-Beispiel machen wir es, indem wir ein lineares Gleichungssystem mit den Anfangstermen aufstellen. Da dieses Beispiel zwei Unbekannte hat, brauchen wir zwei Terme. Es ist egal, welche wir nehmen, also nehmen wir den 0-ten und den ersten, um zu vermeiden, dass wir eine hohe Potenz einer irrationalen Zahl bilden müssen.
-
Löse das resultierende Gleichungssystem.
-
Setze die resultierenden Konstanten in die allgemeine Formel ein, um die Lösung zu erhalten.Werbeanzeige
-
Lass uns die Folge 2, 5, 14, 41, 122, ... , die durch obige Rekursion gegeben ist, betrachten. Diese Aufgabe kann nicht mit Hilfe der obigen Methoden gelöst werden, aber wir können eine Formel mit Hilfe von erzeugenden Funktionen finden.
-
Schreibe die erzeugende Funktion der Folge hin. Eine erzeugende Funktion ist einfach eine formale Potenzreihe, bei der der Koeffizient von x n der n-te Term der Folge ist.
-
Wandle die erzeugende Funktion um, wie gezeigt. Das Ziel in diesem Schritt ist, eine Gleichung zu finden, die uns ermöglicht, die erzeugende Funktion A(x) zu berechnen. Entferne den Anfangsterm. Wende die Rekurrenzgleichung auf die restlichen Terme an. Teile die Summe auf. Entferne konstante Terme. Benutze die Definition von A(x). Benutze die Formel für die Summe einer geometrischen Reihe.
-
Bestimme die erzeugende Funktion A(x).
-
Bestimme die Koeffizienten der Terme x n in A(x). Die Methoden, wie man es tun kann, hängen von der exakten Form von A(x) ab, aber die Methode der Partialbruchzerlegung, kombiniert damit, dass wir die erzeugende Funktion einer geometrischen Folge kennen, funktioniert hier, wie gezeigt.
-
Schreibe die Formel für a n hin, indem du den Koeffizienten von x n in A(x) bestimmst.Werbeanzeige
Tipps
- Induktion ist auch eine beliebte Technik. Es ist oft leicht, durch Induktion zu beweisen, dass eine bestimmte Formel einer gegebenen Rekursion genügt, aber das Problem ist, dass man dabei die Formel vorher erraten muss.
- Einige dieser Verfahren sind rechenintensiv mit vielen Möglichkeiten, einen dummen Fehler zu machen. Es ist gut, die Formel mit ein paar bekannten Werten zu überprüfen.
- "In der Mathematik sind die Fibonacci-Zahlen oder ist die Fibonacci-Folge die Zahlen in der folgenden ganzzahligenFolge: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
- Die Fibonacci-Spirale: eine Annäherung an den goldenen Schnitt, die erzeugt wird, indem Kreisbögen, die die gegenüberliegenden Ecken von Quadraten bei Fibonacci-Fliesen verbinden; hier werden Quadrate der Größen 1, 1, 2, 3, 5, 8, 13, 21 und 34 verwendet.
- Per Definitionem sind die ersten beiden Zahlen in der Fibonacci-Folge entweder 1 und 1 oder 0 und 1, je nach dem gewählten Startpunkt der Folge, und jede nachfolgende Zahl ist die Summe der beiden vorhergehenden.
- Mathematisch ausgedrückt wird die Folge F n der Fibonacci-Zahlen durch folgende Rekursion definiert
- F n = F n-1 + F n-2 mit Anfangswerten F 1 = 1, F 2 = 1 oder F 0 = 0, F 1 = 1.
- Das Verhältnis F n /F n-1 wird "goldener Schnitt" oder Phi (Φ) genannt, und dasselbe gilt für F n-1 /F n . 1
Werbeanzeige
Über dieses wikiHow
Diese Seite wurde bisher 11.297 mal abgerufen.
Werbeanzeige
Melde dich für den kostenlosen wikiHow Newsletter an!
Du erhältst hilfreiche Tipps und Anleitungen jede Woche direkt in deine Inbox.
Registriere mich!
