Rekursionen und erzeugende Funktionen

Die App löst lineare Rekursionen mit konstanten Koeffizienten beliebiger Ordnung über die charakteristische Gleichung – auch mehrfache und komplexe Wurzeln (die komplexe Form der Lösung und ihre Umwandlung in die reelle nach dem Satz von Moivre) – und mit einer rechten Seite der Form P(n)·qⁿ (auch cos nφ, sin nφ, Resonanz und eine Summe rechter Seiten). Die Anfangsbedingungen bestimmen die Konstanten; zur Probe berechnet die App weitere Glieder aus der Rekursion und vergleicht sie mit der Formel.

Mit dem Chip „Methode“ lassen sich auch die erzeugende Funktion (A(x) = Σ aₙxⁿ, Partialbrüche, geometrische Reihen), Matrixpotenzen (Diagonalisierung) oder bei 1. Ordnung das Aufsummieren wählen. Eine Rekursion 1. Ordnung mit variablem Koeffizienten (aₙ₊₁ = (n + 1)aₙ) wird über ein Produkt gelöst (Fakultäten), umformbare nichtlineare Rekursionen über die Substitution bₙ = 1/aₙ oder bₙ = ln aₙ. Ein System zweier Rekursionen löst sie durch Elimination einer Folge oder mit der Matrix, eine Teile-und-herrsche-Rekursion T(n) = aT(n/b) + f(n) über n = bᵏ – mit der Abschätzung nach dem Master-Theorem.

Mit der Operation „Erzeugende Funktion“ findet die App die erzeugende Funktion einer Folge, gegeben durch eine Formel (n² + 2ⁿ) oder ihre ersten Glieder (1, 0, 1, 0, …), und umgekehrt die Formel für aₙ aus einer Funktion A(x). Die Anzahl der nichtnegativen ganzzahligen Lösungen von x₁ + x₂ + … = N (auch mit Schranken oder Koeffizienten – Bezahlen mit Münzen) ist ein Koeffizient einer erzeugenden Funktion.

Der Graph zeigt die Glieder der Folge als Punkte (bei einem System beide Folgen).

Eingabe

`a(n+2) = 5a(n+1) - 6a(n), a(0) = 1, a(1) = 4`	Mit Klammern, die Bedingungen nach einem Komma.
`a_{n+2} = 5a_{n+1} - 6a_n`	Mit Indizes (auch vom Foto). Ohne Bedingungen: die allgemeine Lösung mit Konstanten C₁, C₂.
`F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1`	Der Index darf sinken (aₙ₋₁, aₙ₋₂); ein Wert kann mehreren Gliedern gegeben werden.
`a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0`	Ein System – die Gleichungen in Zeilen, die Bedingungen in der letzten.
`T(n) = 2T(n/2) + n, T(1) = 1`	Teile und herrsche – ein Glied bei n/b.
`n^2 + 2^n`	Die Formel einer Folge mit der Operation „Erzeugende Funktion“ (auch aₙ = …).
`1, 0, 1, 0, ...`	Die ersten Glieder, durch Kommas getrennt.
`1/(1 - x - x^2)`	Eine erzeugende Funktion in x (auch A(x) = …) – die Formel für aₙ.
`Anzahl der Lösungen x_1 + x_2 + x_3 = 10, x_1 <= 3`	Die Anzahl der nichtnegativen ganzzahligen Lösungen mit Schranken.

Beispiele

Zwei verschiedene reelle Wurzeln, die Probe mit weiteren Gliedern.

Eingabe: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

Die Fibonacci-Folge – die Formel von Binet.

Eingabe: F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

Komplexe Wurzeln 1 ± i – die komplexe Form und der Satz von Moivre.

Eingabe: a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

Die rechte Seite n, eine doppelte Wurzel 2.

Eingabe: a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

Dieselbe Rekursion mit der erzeugenden Funktion.

Eingabe: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Erzeugende Funktion

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

Dieselbe Rekursion mit Matrixpotenzen.

Eingabe: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Matrixpotenzen

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

Eine Rekursion 1. Ordnung durch Aufsummieren.

Eingabe: a_{n+1} = 2a_n + 1, a_0 = 0 Aufsummieren

$a_{n+1} = 2a_n + 1, a_0 = 0$

$a_{n+1} = 2a_n + 1, a_0 = 0$ $a_{n+1} = 2a_n + 1, a_0 = 0$

Ein variabler Koeffizient – das Produkt ergibt eine Fakultät.

Eingabe: a_{n+1} = (n+1)a_n, a_0 = 1

$a_{n+1} = (n+1)a_n, a_0 = 1$

$a_{n+1} = (n+1)a_n, a_0 = 1$ $a_{n+1} = (n+1)a_n, a_0 = 1$

Eine nichtlineare Rekursion – die Substitution bₙ = 1/aₙ.

Eingabe: a_{n+1} = a_n/(1 + a_n), a_0 = 1

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$

Ein System zweier Rekursionen durch Elimination der Folge bₙ.

Eingabe:

a_{n+1} = a_n + 2b_n
b_{n+1} = 3a_n + b_n
a_0 = 1, b_0 = 0

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

Teile und herrsche (Mergesort) – n = 2ᵏ und das Master-Theorem.

Eingabe: T(n) = 2T(n/2) + n, T(1) = 1

Die erzeugende Funktion der Folge n² + 2ⁿ.

Eingabe: n^2 + 2^n Erzeugende Funktion

Die Formel für aₙ aus einer erzeugenden Funktion – Partialbrüche über irrationale Wurzeln.

Eingabe: 1/(1 - x - x^2) Erzeugende Funktion

Die Anzahl der Lösungen von x₁ + x₂ + x₃ = 10 mit x₁ ≤ 3.

Eingabe: Anzahl der Lösungen x_1 + x_2 + x_3 = 10, x_1 <= 3

počet řešení x_1 + x_2 + x_3 = 10, x_1 <= 3

Bekannte Einschränkungen

Noch nicht: lineare Rekursionen höherer Ordnung mit variablen Koeffizienten, Systeme aus drei oder mehr Rekursionen, Teile und herrsche mit mehreren Gliedern (T(n/2) und T(n/3)) und nichtlineare Rekursionen, die diese Substitutionen nicht linear machen.