\( \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

Übungen zu rekursiven Folgen

Peter Becker

veröffentlicht: 12 May 2021, zuletzt geändert: 25 Apr 2024 09:27

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

Diese Blog-Folge enthält eine Reihe von Übungen zu Fibonacci-Zahlen und rekursiv definierte Folgen.

Diese Blog-Folge enthält eine Reihe von Übungen zu Fibonacci-Zahlen und rekursiv definierte Folgen. Die Übungen kannst Du mittels vollständiger Induktion lösen. Somit ist diese Blog-Folge auch eine gute Übung zur vollständigen Induktion.

In den folgenden Übungen bezeichnet $F_n$ jeweils die $n$-te Fibonacci-Zahl.

Übung 1

Zeige: Für $n\in\mathbb{N}_0$ gilt $\displaystyle \sum_{k=0}^n F_k = F_{n+2} -1$.

$n=0$: \[ \sum_{k=0}^0 F_k = F_0 = 0 = 1-1 = F_{0+2} - 1 \] $n \rightarrow n+1$: \[ \sum_{k=0}^{n+1} F_k \\ = F_{n+1} + \sum_{k=0}^n F_k \\ \stackrel{I.V.}{=} F_{n+1} + F_{n+2} - 1 \\ = F_{n+3} - 1 \] Erläuterung: Wir ziehen den Summand $F_{n+1}$ aus der Summe heraus und wenden anschließend die Induktionsvoraussetzung sowie die Definition für die Fibonacci-Zahl $F_{n+3}$ an.

Übung 2

Zeige: Für $n\in\mathbb{N}_0$ gilt $\displaystyle \sum_{k=0}^n F_{2k} = F_{2n+1} - 1$.

$n=0$: \[ \sum_{k=0}^0 F_{2k} = F_0 = 0 = 1 - 1 = F_1 - 1 = F_{2\cdot 0 + 1} - 1 \] $n \rightarrow n+1$: \begin{eqnarray*} \sum_{k=0}^{n+1} F_{2k} & = & F_{2n+2} + \sum_{k=0}^n F_{2k} \\ & \stackrel{I.V.}{=} & F_{2n+2} + F_{2n+1} - 1 \\ & = & F_{2n+3} - 1 \\ & = & F_{2(n+1)+1} - 1 \end{eqnarray*}

Übung 3

Zeige: Für $n\in\mathbb{N}_0$ gilt $\displaystyle \sum_{k=0}^n F_k^2 = F_n F_{n+1}$.

$n=0$: \[ \sum_{k=0}^0 F_k^2 = F_0^2 = 0 = 0\cdot 1 = F_0 F_1 \] $n \rightarrow n+1$: \begin{eqnarray*} \sum_{k=0}^{n+1} F_k^2 & = & F_{n+1}^2 + \sum_{k=0}^n F_k^2 \\ & \stackrel{I.V.}{=} & F_{n+1}^2 + F_n F_{n+1} \\ & = & F_{n+1} (F_{n+1} + F_n) \\ & \stackrel{Def.}{=} &F_{n+1} F_{n+2} \end{eqnarray*}

Übung 4

Zeige: Für $n \geq 1$ gilt $\displaystyle F_{n+1} F_{n-1} - F_n^2 = (-1)^n$.

$n=1$: \[ F_2 \cdot F_0 - F_1^2 = 1\cdot 0 - 1 = -1 = (-1)^1 \] $n\rightarrow n+1$: \begin{eqnarray*} F_{n+2}F_n - F_{n+1}^2 & \stackrel{Def.}{=} & (F_{n+1} + F_n)(F_{n-1} + F_{n-2}) - (F_n + F_{n-1})^2 \\ & = & F_{n+1} F_{n-1} + F_n F_{n-1} + F_{n+1} F_{n-2} + F_n F_{n-2} - F_n^2 - 2F_n F_{n-1} - F_{n-1}^2 \\ & = & \left(F_{n+1} F_{n-1} - F_n^2\right) + \left(F_n F_{n-2} - F_{n-1}^2\right) + F_n F_{n-1} + F_{n+1} F_{n-2} - 2 F_n F_{n-1} \\ & \stackrel{I.V.}{=} & \underbrace{ (-1)^n + (-1)^{n-1} }_{=0} + F_n F_{n-1} + F_{n+1} F_{n-2} - 2 F_n F_{n-1} \\ & = & F_{n+1} F_{n-2} - F_n F_{n-1} \\ & \stackrel{Def.}{=} & F_{n+1} (F_n - F_{n-1}) - F_n (F_{n+1} - F_n) \\ & = & -F_{n+1} F_{n-1} + F_n^2 \\ & \stackrel{I.V.}{=} & (-1)^{n+1} \end{eqnarray*}

Übung 5

Die Lucas-Zahlen $L_n$ sind für $n\geq 0$ definiert durch \[ L_0 = 2, L_1 = 1 \text{ und } L_n = L_{n-1} + L_{n-2} \text{ für } n \geq 2. \] Zeige: \[ L_n = \left(\frac{1+\sqrt{5}}{2}\right)^n + \left(\frac{1-\sqrt{5}}{2}\right)^n \text{ für } n \in \mathbb{N}_0. \]

Wie bei der Formel von Moivre-Binet müssen wir für $L_0$ und $L_1$ die Korrektheit der Formel nachweisen. Dies ist der Induktionsanfang.

$n=0$: \[ \left(\frac{1+\sqrt{5}}{2}\right)^0 + \left(\frac{1-\sqrt{5}}{2}\right)^0 = 1 + 1 = 2 = L_0 \] $n=1$: \[ \left(\frac{1+\sqrt{5}}{2}\right)^1 + \left(\frac{1-\sqrt{5}}{2}\right)^1 = \frac{1 + \sqrt{5} + 1 - \sqrt{5}}{2} = \frac{2}{2} = 1 = L_1 \] $n \rightarrow n+1$: \begin{eqnarray*} L_{n+1} & = & L_n + L_{n-1} \\ & = & \left(\frac{1+\sqrt{5}}{2}\right)^n + \left(\frac{1-\sqrt{5}}{2}\right)^n + \left(\frac{1-\sqrt{5}}{2}\right)^{n-1} + \left(\frac{1-\sqrt{5}}{2}\right)^{n-1} \\ & = & \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} \left(\frac{1+\sqrt{5}}{2} + 1\right) + \left(\frac{1-\sqrt{5}}{2}\right)^{n-1} \left(\frac{1-\sqrt{5}}{2} + 1\right) = (*) \end{eqnarray*} Es gilt nun \begin{eqnarray*} \frac{1+\sqrt{5}}{2} + 1 & = & \frac{3 + \sqrt{5}}{2} \\ & = & \frac{6 + 2\sqrt{5}}{4} \\ & = & \frac{1 + 2\sqrt{5} + 5}{4} \\ & = & \left(\frac{1+\sqrt{5}}{2}\right)^2. \end{eqnarray*} Auf analoge Weise ergibt sich \[ \left(\frac{1-\sqrt{5}}{2} + 1\right) = \left(\frac{1-\sqrt{5}}{2}\right)^2. \] Damit erhalten wir \[ (*) = \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} + \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \] womit die Formel beweisen ist.

Übung 6

Es sei \[ a_0 = 0, a_1 = 8 \text{ und } a_n = 2 a_{n-1} + 3 a_{n-2} \text{ für } n\geq 2. \] Zeige: \[ a_n = 2\cdot 3^n - 2\cdot (-1)^n \text{ für } n \in \mathbb{N}_0. \]

$n=0$: \[ 2\cdot 3^0 - 2\cdot (-1)^0 = 2 - 2 = 0 = a_0 \] $n=1$: \[ 2\cdot 3^1 - 2\cdot (-1)^1 = 6 + 2 = 8 = a_1 \] $n \rightarrow n+1$: \begin{eqnarray*} a_{n+1} & = & 2 a_n + 3 a_{n-1} \\ & = & 2 \left(2\cdot 3^n - 2\cdot (-1)^n\right) + 2 \left(2\cdot 3^{n-1} - 2\cdot (-1)^{n-1}\right) \\ & = & 4\cdot 3^n - 4\cdot (-1)^n + 6\cdot 3^{n-1} -6\cdot(-1)^{n-1} \\ & = & 4\cdot 3^n + 6\cdot 3^{n-1} - 4\cdot (-1)^n - 6\cdot (-1)^{n-1} \\ & = & 3^{n-1} (4\cdot 3 + 6) - (-1)^{n-1}(4\cdot(-1) + 6) \\ & = & 18\cdot 3^{n-1} - 2\cdot (-1)^{n-1} \\ & = & (*) \end{eqnarray*} Mit $18 = 2\cdot 3^2$ und $(-1)^{n-1} = (-1)^{n+1}$ folgt \[ (*) = 2\cdot 3^{n+1} - 2\cdot(-1)^{n+1}. \] Damit ist die Formel bewiesen.

Übung 7

Fliesenleger Jupp soll einen Weg der Länge $n$ pflastern. Ihm stehen hierfür vier verschiedene Fliesentypen der Länge eins in den Farben rot, grün, blau und gelb sowie zwei verschiedene Fliesentypen der Länge zwei in den Farben magenta und türkis zur Verfügung.

Jupp fragt sich, wie viele verschiedene Pflasterungen es für einen Weg der Länge $n$ wohl gibt. Du sollst ihm bei der Beantwortung dieser Frage helfen.

  1. Es sei $a_n$ die Anzahl der verschiedenen Pflasterungen der Länge $n$. Gebe eine rekursive Formel für $a_n$ an.
  2. Zeige mithilfe Deiner rekursiven Formel aus (a): \[ a_n = \frac{1}{6} \left( (3 + \sqrt{6})(2+\sqrt{6})^n + (3 - \sqrt{6})(2-\sqrt{6})^n \right). \]

  1. Für eine Pflasterung der Länge $1$ haben wir vier verschiedene Fliesen zur Verfügung, also $a_1=4$.

    Eine Pflasterung der Länge $2$ können wir entweder mit zwei Fliesen der Länge $1$ erreichen ($4\cdot4 = 16$ Möglichkeiten) oder mit einer Fliese der Länge $2$, wofür wir zwei Möglichleiten haben. Also gilt $a_2 = 16 + 2 = 18$.

    Eine Pflasterung der Länge $n$ können wir mit einer Fliese der Länge $1$ beginnen (vier Möglichkeiten) und mit einer beliebigen Pflasterung der Länge $n-1$ fortsetzen. So ergeben sich $4a_{n-1}$ verschiedene Möglichkeiten.

    Wir können eine Pflasterung der Länge $n$ aber auch mit einer Fliese der Länge $2$ beginnen (zwei Möglichkeiten). Daraus ergeben sich dann $2a_{n-2}$ Möglichkeiten.

    Damit erhalten wir als Rekursionsformel: \[ a_1 = 4, a_2 = 18, a_n = 4 a_{n-1} + 2 a_{n-2} \text{ für } n \geq 3. \]

  2. Wir führen den Beweis mittels vollständiger Induktion. Da die Rekursionsformel nur für $n\geq 3$ gilt, müssen wir für $n=1$ und $n=2$ die Korrektheit der Formel direkt beweisen. Dies stellt den Induktionsanfang dar.

    $n=1$: \begin{eqnarray*} \frac{1}{6} \left( (3+\sqrt{6})(2+\sqrt{6}) + (3-\sqrt{6})(2-\sqrt{6}) \right) & = & \frac{1}{6} \left( 6 + 2\sqrt{6} + 3\sqrt{6} + 6 + 6 - 2\sqrt{6} - 3\sqrt{6} + 6 \right) \\ & = & \frac{1}{6} \cdot 24 = 4 \end{eqnarray*} $n=2$: \begin{eqnarray*} \frac{1}{6} \left( (3 + \sqrt{6})(2+\sqrt{6})^2 + (3 - \sqrt{6})(2-\sqrt{6})^2 \right) & = & \frac{1}{6} \left( (3 + \sqrt{6})(10 + 4\sqrt{6}) + (3 - \sqrt{6})(10-4\sqrt{6}) \right) \\ & = & \frac{1}{6} \left( 30 + 10\sqrt{6} + 12\sqrt{6} + 24 + 30 - 10\sqrt{6} - 12\sqrt{6} + 24 \right) \\ & = & \frac{1}{6}\cdot 108 = 18 \end{eqnarray*} $n \rightarrow n+1$: \begin{eqnarray*} a_{n+1} & = & 4 a_n + 2 a_{n-1} \\ & \stackrel{\text{I.V.}}{=} & \frac{4}{6} \left( (3 + \sqrt{6})(2+\sqrt{6})^n + (3 - \sqrt{6})(2-\sqrt{6})^n \right) \\ & & + \frac{2}{6} \left( (3 + \sqrt{6})(2+\sqrt{6})^{n-1} + (3 - \sqrt{6})(2-\sqrt{6})^{n-1} \right) \\ & = & \frac{1}{6} (3+\sqrt{6})(2+\sqrt{6})^{n-1} \left( 4(2+\sqrt{6})+2\right) \\ & & + \frac{1}{6} (3-\sqrt{6})(2-\sqrt{6})^{n-1} \left( 4(2-\sqrt{6})+2\right) = (*) \end{eqnarray*} An dieser Stelle bietet sich eine kleine Nebenrechnung an. Es gilt \[ 4(2+\sqrt{6})+2 = 10 + 4\sqrt{6} = 4 + 4\sqrt{6} + 6 = (2+\sqrt{6})^2 \] und \[ 4(2-\sqrt{6})+2 = 10 - 4\sqrt{6} = 4 - 4\sqrt{6} + 6 = (2-\sqrt{6})^2. \] Damit erhalten wir \begin{eqnarray*} (*) & = & \frac{1}{6} (3+\sqrt{6})(2+\sqrt{6})^{n+1} + \frac{1}{6} (3-\sqrt{6})(2-\sqrt{6})^{n+1} \\ & = & \frac{1}{6} \left( (3+\sqrt{6})(2+\sqrt{6})^{n+1} + (3-\sqrt{6})(2-\sqrt{6})^{n+1} \right). \end{eqnarray*} Damit ist die Formel bewiesen.

Vorige Folge Nächste Folge

Teilen und Drucken