Übungsaufgabe: Rekursive Folge

Dies ist eine Aufgabe zum Thema Vollständige Induktion.

    Gegeben sei eine Folge von natürlichen Zahlen definiert durch

    $$ x_0 = 2, \qquad x_1 = 5, \qquad x_{n+1} = 5 \,\, x_n - 6 \,\, x_{n-1} \qquad \text{für alle} \qquad n \geq 1 $$

    Zeige, dass für alle \( n \in \mathbb{N}_0 \) gilt:

    $$ x_n = 2^n + 3^n \qquad (\ast) $$

    Vollständige Induktion benutzen.

    Lösung

    Induktionsanfang:   \( n = 0 \)

    $$ x_0 = 2 = 1 + 1 = 2^0 + 3^0 $$

    Induktionsannahme:   \( (\ast) \) gilt bis zu einem gewissen \( n \in \mathbb{N}_0 \)


    Induktionsschlusss:   \( n = n+1 \)

    \begin{aligned} x_{n+1} &= 5 \,\, x_n - 6 \,\, x_{n-1} \\[4pt] &= 5 \cdot (2^n+3^n) - 6 \cdot (2^{n-1} + 3^{n-1}) \\[4pt] &= 5 \cdot 2^n + 5 \cdot 3^n - 6 \cdot 2^{n-1} - 6 \cdot 3^{n-1} \\[4pt] &= 5 \cdot 2 \cdot 2^{n-1} + 5 \cdot 3 \cdot 3^{n-1} - 6 \cdot 2^{n-1} - 6 \cdot 3^{n-1} \\[4pt] &= 10 \cdot 2^{n-1} + 15 \cdot 3^{n-1} - 6 \cdot 2^{n-1} - 6 \cdot 3^{n-1} \\[4pt] &= 4 \cdot 2^{n-1} + 9 \cdot 3^{n-1} \\[4pt] &= 2 \cdot 2 \cdot 2^{n-1} + 3 \cdot 3 \cdot 3^{n-1} \\[4pt] &= 2^{n+1} + 3^{n+1} \\[4pt] \end{aligned}