\( \newcommand{\I}{\textnormal{i}} \newcommand{\e}{\textnormal{e}} \renewcommand{\Re}{\textnormal{Re}} \renewcommand{\Im}{\textnormal{Im}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\C}{\mathbb{C}} \newcommand{\K}{{\cal K}} \)

Analysis-Blog: Folge 18

Folgen

Nummerierung unendlich vieler Objekte

Peter Becker

veröffentlicht: 05 May 2021, zuletzt geändert: 27 May 2024 15:54

Schlüsselwörter: Folge, Zahlenfolge, Rekursion, vollständige Induktion

Von Intelligenztests kennen wir die Aufgabe, eine Abfolge von Zahlen passend fortzusetzen.

Einführung

Von Intelligenztests kennen wir die Aufgabe, eine Abfolge von Zahlen passend fortzusetzen. Betrachten wir hierzu einige Beispiele:

  1. $1,4,9,16,25,\ldots$
  2. $2,3,5,7,11,13,17,\ldots$
  3. $1,-2,3,-4,5,-6,\ldots$
  4. $1,5,7,17,31,65,\ldots$
  5. $1,-\frac{1}{2},\frac{1}{3},-\frac{1}{4},\frac{1}{5},\ldots$
  6. $1,i,-1,-i,1,i,-1,-i,1,\ldots$

Wir wollen überlegen, wie diese Abfolgen von Zahlen jeweils passend fortgesetzt werden können.

  1. Hier besteht die Abfolge aus den ersten Quadratzahlen. Wir können $1,4,9,16,25$ als $1^2,2^2,3^2,4^2,5^2$ schreiben. Daher scheint $6^2=36$ die natürliche Fortsetzung zu sein.
  2. Die Abfolge besteht aus den ersten sechs Primzahlen. Dementsprechend passt $19$, die siebte Primzahl, als Fortsetzung.
  3. Wenn wir das Vorzeichen vernachlässigen, besteht die Abfolge aus den ersten sechs natürlichen Zahlen. Das Vorzeichen wechselt dabei stets von einer Zahl zur nächsten. Somit ist $7$ eine passende Fortsetzung.
  4. Hier ist es schon schwieriger zu erkennen, wie die Abfolge der Zahlen gebildet wird. Mit etwas Erfahrung sieht man aber, dass alle Zahlen direkte Vor- oder Nachfolger von Zweierpotenzen sind. So können wir die Abfolge als $2^1-1,2^2+1,2^3-1,2^4+1,2^5-1,2^6+1$ schreiben, also als aufsteigende Zweierpotenzen, von denen abwechselnd $1$ subtrahiert oder zu denen 1 addiert wird. Daher passt $2^7-1=127$ als Fortsetzung.
  5. In dieser Abfolge treten Brüche auf, mit wechselndem Vorzeichen, wobei der Nenner stets um $1$ größer wird. Damit lautet die Fortsetzung $-\frac{1}{6}$.
  6. Diese Abfolge enthält komplexe Zahlen. Wir können Sie auch als $i^0,i^1,i^2,i^3,i^4,i^5,i^6,i^7,i^8$ schreiben. Man beachte, dass $i^2 = -1$ gilt und somit $i^3 = i\cdot i^2 = -i$ und $i^4 = i^2\cdot i^2 = (-1)\cdot(-1) = 1$. Ausgehend von $1$ wiederholen sich die Zahlen. Als Fortsetzung ergibt sich somit $i^9=i$.

Der Begriff der Folge

Uns stellt sich nun die Frage, wie wir solch eine systematische Abfolge von Zahlen mathematisch ausdrücken. Die Antwort darauf ist einfach: Solch eine Regelmäßigkeit in der Abfolge von Zahlen können wir mithilfe einer Abbildung bzw. Funktion formulieren. Hierzu legen wir durch eine Abbildung fest, welchen Wert das $n$-te Element in der Abfolge annimmt.

Definition

Es sei $M$ eine Menge. Eine Folge in $M$ ist eine Abbildung \[ \begin{array}{cccc} a: & \mathbb{N} & \rightarrow & M \\ & n & \mapsto & a(n). \end{array} \] Statt $a(n)$ schreiben wir in der Regel $a_n$ und für diese Abbildung $(a_n)_{n\in\mathbb{N}}$, $(a_n)_{n\geq 1}$ oder auch nur $(a_n)$.

Das Element $a_n$ heißt $n$-tes Folgenglied der Folge $(a_n)$.

Handelt es sich bei $M$ um eine Menge von Zahlen, so sprechen wir von einer Zahlenfolge.

Für $M=\mathbb{R}$ bezeichnen wir $(a_n)$ auch als reelle Zahlenfolge, für $M=\mathbb{C}$ als komplexe Zahlenfolge.

Schauen wir uns die Begriffe der letzten Definition am Beispiel der ersten Folge von oben, die aus den Quadratzahlen besteht, an. Diese Folge entspricht der Abbildung $a:\mathbb{N} \rightarrow \mathbb{R}, n \mapsto n^2$. Das Symbol $(a_n)$ bezeichnet diese Abbildung. Demgegenüber steht $a_n$ für den Funktionswert an der Stelle $n$, ist also eine reelle Zahl. Für ein konkretes $n\in\mathbb{N}$ ergibt sich dementsprechend eine konkrete reelle Zahl, z. B. $a_6 = 36$. Die Zahl $36$ ist also das sechste Folgenglied von $(a_n)$.

Der Definitionsbereich einer Folge muss nicht zwingend die Menge $\mathbb{N}$ der natürlichen Zahlen sein. Häufig betrachten wir auch Folgen, die schon bei $0$ beginnen, d. h. wir haben $\mathbb{N}_0$ als Definitionsbereich. Wenn wir dies deutlich machen wollen, schreiben wir $(a_n)_{n\in\mathbb{N}_0}$ oder auch $(a_n)_{n\geq 0}$. Wenn der genaue Definitionsbereich der Folge keine Rolle spielt oder sich aus dem Kontext ergibt, standardmäßig gehen wir von $\mathbb{N}$ als Definitionsbereich aus, schreiben wir einfach $(a_n)$.

Prinzipiell kann der Wertebereich $M$ einer Folge eine beliebige Menge sein. So wäre beispielsweise eine Folge mit $M = \{ \clubsuit, \spadesuit, \heartsuit, \diamondsuit \}$ eine Folge, die aus den Farben eines Kartenspiels besteht. Für \[ a_n = \left\{ \begin{array}{ll} \clubsuit & \text{für}\quad n\mod 4 = 1 \\ \spadesuit & \text{für}\quad n\mod 4 = 2 \\ \heartsuit & \text{für}\quad n\mod 4 = 3 \\ \diamondsuit & \text{für}\quad n\mod 4 = 0 \end{array} \right. \] ergibt sich damit die Folge \[ \clubsuit, \spadesuit, \heartsuit, \diamondsuit, \clubsuit, \spadesuit, \heartsuit, \diamondsuit, \clubsuit, \spadesuit, \heartsuit, \diamondsuit, \clubsuit, \ldots \] In der Analysis interessieren wir uns aber ausschließlich für Zahlenfolgen. Daher betrachten wir zunächst reelle Folgen, später auch komplexe Folgen. Meistens gehen wir dabei der Frage nach, ob eine Zahlenfolge bestimmte mathematische Eigenschaften aufweist. In späteren Blogs werden wir eine Reihe von solchen Eigenschaften kennenlernen.

Beispiel

Die Abbildungsvorschriften für die Beispielfolgen von oben lauten:
  1. $a_n = n^2$
  2. $b_n = n\text{-te Primzahl}$
  3. $c_n = (-1)^{n-1} n$
  4. $d_n = 2^n + (-1)^n$
  5. $e_n = \frac{(-1)^{n-1}}{n}$
  6. $f_n = i^{n-1}$.

Rekursiv definierte Folgen

Folgen können auch rekursiv definiert sein, d. h. die Definition des $n$-ten Folgenglieds $a_n$ basiert auf der Definition von Folgengliedern $a_i$ für $i \leq n-1$. Schauen wir uns hierzu ein Beispiel an: Für $(a_n)_{n\in\mathbb{N}}$ sei das $n$-te Folgenglied $a_n$ definiert durch \[ a_n = \left\{ \begin{array}{rl} 1 & \text{für } n = 1 \\ n \cdot a_{n-1} & \text{für } n \geq 2. \end{array} \right. \] Dies ist offensichtlich eine rekursive Definition, denn die Definition von $a_n$ nutzt $a_{n-1}$. Um $a_n$ zu berechnen, müssen wir die Definition so lange anwenden, bis sich die Rekursion auflöst. Wir betrachten dies am Beispiel von $a_4$: \[ a_4 = 4\cdot a_3 = 4\cdot 3 \cdot a_2 = 4\cdot 3 \cdot 2 \cdot a_1 = 4\cdot 3 \cdot 2 \cdot 1 = 24. \] Dieses Beispiel legt die Vermutung nahe, dass für das $n$-te Folgenglied $a_n = n!$ gilt. Um diese Vermutung zu bestätigen, müssen wir die Gültigkeit von $a_n = n!$ für alle $n\in\mathbb{N}$ beweisen. Als Beweismethode bietet sich hier die vollständige Induktion an. Ich empfehle, diesen sehr einfachen Beweis zur Übung selbst durchzuführen.

Übung 1

Es sei $a_1 = 1$ und $a_n = n\cdot a_{n-1}$ für $n\geq 2$.

Zeige mittels vollständiger Induktion: Es gilt \[ a_n = n! \text{ für alle } n \in \mathbb{N}. \]

Induktionsanfang für $n=1: a_1 = 1 = 1!$

Induktionsschritt $n \rightarrow n+1:$ \[ a_{n+1} = (n+1)\cdot a_n = (n+1) \cdot n! = (n+1)\cdot\prod_{k=1}^n k = \prod_{k=1}^{n+1} k = (n+1)! \]

Im Beweis nutzen wir beim ersten Gleichheitszeichen die Definition von $a_{n+1}$, beim zweiten Gleichheitszeichen die Induktionsvoraussetzung und beim dritten Gleichheitszeichen die Definition der Fakultätsfunktion. Beim vierten Gleichheitszeichen ziehen wir den Faktor $(n+1)$ in das Produkt und erhalten damit $(n+1)!$.

Mit dem Beweis von Übung 1 ist es uns gelungen, für die rekursiv definierte Folge $(a_n)$ eine explizite Formel, d. h. ohne Rekursion, für die Folgenglieder $a_n$ zu finden. Dies ist eine Aufgabe, die häufig für die Laufzeitanalyse von rekursiven Algorithmen notwendig ist. Solch eine explizite Formel für die Folgenglieder lässt sich aber keineswegs immer so leicht wie in Übung 1 herleiten. In einem folgenden Blog greifen wir dieses Thema wieder auf.

Vorige Folge Nächste Folge

Teilen und Drucken