Bildungsgesetze zweier Folgen

In diesem Artikel werden für zwei Folgen¹ α und β die Gleichheit ihres rekursiven und eines expliziten Bildungsgesetzes bewiesen.

Voraussetzungen

Vorausgesetzt werden $p,q\in\mathbb{R}\setminus\{0\}$ und $p^2>4q$ sowie $n\in\mathbb{N}$. Die rekursiven Definitionen sind:

$$\begin{aligned} \alpha(n) &= \begin{cases} 0 & \mathrm{falls\quad} n=1 \\ -\frac{q}{p+\alpha(n-1)} & \mathrm{falls\quad} n>1 \\ \end{cases} \\ \beta(n) &= \begin{cases} -p & \mathrm{falls\quad} n=1 \\ -p-\frac{q}{\beta(n-1)} & \mathrm{falls\quad} n>1 \\ \end{cases} \end{aligned}$$

Behauptungen

$$\begin{aligned} \forall n\in\mathbb{N}: \quad\alpha(n) &= q\frac{b^{n-1}-a^{n-1}}{b^n-a^n} \\ \forall n\in\mathbb{N}: \quad\beta(n) &= \frac{b^{n+1}-a^{n+1}}{b^n-a^n} \end{aligned}$$

Dabei sind a und b die beiden reellwertigen Lösungen der quadratischen Gleichung $0=x^2+px+q$:

$$\begin{aligned} a &= -\frac{p}{2}-\sqrt{\frac{p^2}{4}-q} \\ b &= -\frac{p}{2}+\sqrt{\frac{p^2}{4}-q} \end{aligned}$$

Im Anhang findet sich eine Veranschaulichung des Problems anhand einer Umsetzung in der Programmiersprache PHP.

Beweise

Lemma

Unter den gegebenen Voraussetzungen gilt:

$$b^{n+1}-a^{n+1} = -p\left(b^n-a^n\right)-q\left(b^{n-1}-a^{n-1}\right)$$

Beweis:

$$\begin{aligned} && b^{n+1}-a^{n+1} &= -p\left(b^n-a^n\right)-q\left(b^{n-1}-a^{n-1}\right) \\ \Leftrightarrow && b^{n+1}+pb^n+qb^{n-1} &= a^{n+1}+pa^n+qa^{n-1} \\ \Leftrightarrow && b^{n-1}\left(b^2+pb+q\right) &= a^{n-1}\left(a^2+pa+q\right) \\ \Leftrightarrow && b^{n-1}(0) &= a^{n-1}(0) \end{aligned}$$

Beweis für die Folge α

Zuerst wird bewiesen, dass die Behauptung für das konkrete $n=1$ gilt:

$$\begin{aligned} q\frac{b^{n-1}-a^{n-1}}{b^n-a^n} &\stackrel{n=1}{=} q\frac{b^0-a^0}{b^1-a^1} \\ &= q\frac{1-1}{b-a} \\ &= 0 \\ &= \alpha(1) \end{aligned}$$

So weit, so gut. Nun nehmen wir an, dass die Behauptung für ein konkretes n bewiesen wurde, und zeigen, dass sie dann auch für $n+1$ gilt:

$$\begin{aligned} \alpha(n+1) &= -\frac{q}{p+\alpha(n)} \\ &= -\frac{q}{p+\left(q\frac{b^{n-1}-a^{n-1}}{b^n-a^n}\right)} \\ &= -\frac{1}{\frac{p}{q}+\left(\frac{b^{n-1}-a^{n-1}}{b^n-a^n}\right)} \\ &= -\frac{1}{\frac{p\left(b^n-a^n\right)+q\left(b^{n-1}-a^{n-1}\right)}{q\left(b^n-a^n\right)}} \\ &= -\frac{q\left(b^n-a^n\right)}{p\left(b^n-a^n\right)+q\left(b^{n-1}-a^{n-1}\right)} \\ &\stackrel{\mathrm{Lemma}}{=} q\frac{b^n-a^n}{b^{n+1}-a^{n+1}} \end{aligned}$$

Folglich gilt die Behauptung für alle n.

Beweis für die Folge β

Zuerst wird bewiesen, dass die Behauptung für das konkrete $n=1$ gilt:

$$\begin{aligned} \frac{b^{n+1}-a^{n+1}}{b^n-a^n} &\stackrel{n=1}{=} \frac{b^2-a^2}{b^1-a^1} \\ &= \frac{\left(b-a\right)\left(b+a\right)}{b-a} \\ &= b+a\\ &= -\frac{p}{2}+\sqrt{\frac{p^2}{4}-q}-\frac{p}{2}-\sqrt{\frac{p^2}{4}-q} \\ &= -p \\ &= \beta(1) \end{aligned}$$

Nun nehmen wir an, dass die Behauptung für ein konkretes n bewiesen wurde, und zeigen, dass sie dann auch für $n+1$ gilt:

$$\begin{aligned} \beta(n+1) &= -p-\frac{q}{\beta(n)} \\ &= -p-\frac{q}{\frac{b^{n+1}-a^{n+1}}{b^n-a^n}} \\ &= -p-q\frac{b^n-a^n}{b^{n+1}-a^{n+1}} \\ &= \frac{-p\left(b^{n+1}-a^{n+1}\right)-q\left(b^n-a^n\right)}{b^{n+1}-a^{n+1}} \\ &\stackrel{\mathrm{Lemma}}{=} \frac{b^{n+2}-a^{n+2}}{b^{n+1}-a^{n+1}} \end{aligned}$$

Folglich gilt die Behauptung für alle n. Tada!

Zusammenhang der Folgen α und β

Die Folgen α und β sind eng verwandt, was ihrer Definitionen wegen auch nicht verwunderlich ist. Aus den Bildungsgesetzen folgen direkt:

$$\begin{aligned} q &= \alpha(n+1)\beta(n) \\ -p &= \alpha(n)+\beta(n) \end{aligned}$$

Ebenso wie a und b sind die Graphen der Folgen demnach Spiegelungen an $-\frac{p}{2}$. Schaut man sich außerdem die folgenden Verallgemeinerungen $\mathrm{A}_r$ mit $\alpha(n) = \mathrm{A}_0(n)$ und $\mathrm{B}_s$ mit $\beta(n) = \mathrm{B}_{-p}(n)$ an,

$$\begin{aligned} \mathrm{A}_r(n) &= \begin{cases} r & \mathrm{falls\quad} n=1 \\ -\frac{q}{p+\mathrm{A}_r(n-1)} & \mathrm{falls\quad} n>1 \\ \end{cases} \\ \mathrm{B}_s(n) &= \begin{cases} s & \mathrm{falls\quad} n=1 \\ -p-\frac{q}{\mathrm{B}_s(n-1)} & \mathrm{falls\quad} n>1 \\ \end{cases} \end{aligned}$$

… stellt man fest: Diese Folgen sind unter den obigen Voraussetzungen genau dann für alle natürlichen Zahlen definiert, wenn $r\in\mathbb{R}\setminus\left\{\beta(n)\middle|n\in\mathrm{N}\right\}$ und $s\in\mathbb{R}\setminus\left\{\alpha(n)\middle|n\in\mathbb{N}\right\}$. Exakt jene Werte, die als Startwert r die Rekursion $\mathrm{A}_r$ irgendwann zur Division durch null führen würden, gibt also β an. α gibt genau all jene Werte an, die als Startwert s die Rekursion $\mathrm{B}_s$ irgendwann zur Division durch null führen würden. Beweis: trivial. ;-)

Ausblick

In Kürze werde ich in einem zweiten Artikel Konvergenz und Grenzwerte der Folgen herleiten.

Eigentlich handelt es sich jeweils um Scharen unendlich vieler Folgen mit den Parametern p und q. Der Übersichtlichkeit halber schreibe ich das in diesem Artikel nicht ausdrücklich mit, sondern spreche einfach von den Folgen α und β.

Anhang

Was sind rekursive und explizite Bildungsgesetze?

Rekursive und explizite Bildungsgesetze lassen sich gut an einem einfachen Beispiel illustrieren: Die Folge der Kerzenzahlen auf der Geburtstagstorte.

Rekursiv nennt man solche Bildungsgesetze von Folgen, die auf die Folge selbst Bezug nehmen: „Zum ersten Geburtstag ist eine Kerze auf der Torte, zu jedem anderen Geburtstag ist eine Kerze mehr als im Vorjahr auf der Torte“ – die Zahl der Kerzen wird über die Zahl der Kerzen des Vorjahres bestimmt. Nicht immer ist so eine Definition praktisch. Möchte man etwa wissen, wie viele Kerzen zum achtzehnten Geburtstag auf die Torte sollen, muss man sich erst bis zum ersten Geburtstag zurückwühlen und von dort an dann für jedes Jahr eine Kerze hinzunehmen, bis man beim achtzehnten Geburtstag ankommt und weiß: Es sind 18 Kerzen.

Explizit nennt man solche Bildungsgesetze, die zu einer gegebenen Nummer direkt das entsprechende Glied der Folge ermitteln. Im Kerzenbeispiel: „Zum n-ten Geburtstag sind n Kerzen auf der Torte.“ Man weiß dann sofort: Zum 18-ten Geburstag müssen 18 Kerzen auf die Torte.

Es ist allerdings nicht immer einfach, von einem rekursiven Bildungssgesetz auf ein explizites Bildungsgesetz zu schließen. Oft haben einfache rekursive Gesetze aufwendige explizite Darstellungen.

Veranschaulichung in einer Programmiersprache: PHP

Man kann das in diesem Artikel behandelte Problem gut in einer Programmiersprache nachvollziehen, was die Aufgabe manchem Programmierer sicherlich leichter zugänglich macht. Ich wähle dafür PHP. Man möge mir verzeihen, dass die Beispiele weder bestmöglich optimiert sind noch ungültige Parameter abfangen.

Beim Ausprobieren ist zu beachten, dass Rechner mit Fließkommazahlen nur bedingt genau rechnen und weiteren Beschränkungen unterworfen sind, weshalb die mathematisch äquivalenten Funktionen im Grenzbereich in PHP ggf. abweichende Ergebnisse liefern können.

Los geht’s – gegeben ist ein rekursive Funktion:

// p und q sind Fließkomma-Konstanten mit p * p > 4 * q und p * q != 0
// $n ist eine Ganzzahl mit $n >= 1

function alpha ($n) {
    return ($n == 1)? 0: -q / (p + alpha ($n - 1));
}

Rekursive Funktionen können sehr elegant sein, sind allerdings bei der Berechnung selten die effizienteste Variante. Man kann dieselbe Aufgabe mit einer iterativen Lösung angehen, die aus technischen Gründen weniger Arbeitsspeicher beansprucht und meist schneller ist:

function alpha ($n) {
    $z = 0;
    for ($i = 1; $i < $n; $i++) {
        $z = -q / (p + $z);
    }
    return $z;
}

Prinzipiell unterscheiden sich rekursive und iterative Varianten jedoch nicht. In beiden Fällen wird das Ergebnis durch wiederholte Ausführung derselben Berechnung ermittelt, wobei angefangen mit null jedes Zwischenergebnis immer wieder als Eingabe der Berechnung des nächsten Zwischenergebnisses verwendet wird. Möchte man alpha von 50 ausrechnen, wird in der rekursiven Variante 50-mal die Funktion alpha aufgerufen, in der iterativen Variante 50-mal die for-Schleife durchlaufen.

Schöner wäre die Berechnung des Ergebnisses nach einer expliziten Formel: Man gibt n ein, die Funktion wird ohne Wiederholungen einmal durchlaufen und spuckt das Ergebnis aus. Eine solche Funktion gibt es:

function alpha ($n) {
    $a = -p / 2 - sqrt (p * p / 4 - q);
    $b = -p / 2 + sqrt (p * p / 4 - q);
    return q * (pow ($b, $n - 1) - pow ($a, $n - 1)) / (pow ($b, $n) - pow ($a, $n));
}

pow (x, m) berechnet dabei die m-te Potenz von x („x hoch m“) während sqrt die Quadratwurzel ergibt.

Zu zeigen, dass diese explizite Funktion tatsächlich dasselbe errechnet wie die rekursive Variante, ist genau, worum es in dem Beweis geht.