Um die Beziehung \( L_n = 2F_{n-1} + F_n \) für \( n > 1 \) zwischen den Lucas-Zahlen \( L_n \) und den Fibonacci-Zahlen \( F_n \) mit vollständiger Induktion zu beweisen, gehen wir wie folgt vor: **Induktionsanfang:** Für \( n = 2 \): - Die Lucas-Zahlen sind definiert als: - \( L_0 = 2 \) - \( L_1 = 1 \) - \( L_2 = 3 \) - Die Fibonacci-Zahlen sind definiert als: - \( F_0 = 0 \) - \( F_1 = 1 \) - \( F_2 = 1 \) Setzen wir \( n = 2 \) in die Beziehung ein: \[ L_2 = 2F_{1} + F_{2} \] Einsetzen der Werte: \[ 3 = 2 \cdot 1 + 1 = 2 + 1 = 3 \] Der Induktionsanfang ist also wahr. **Induktionsvoraussetzung:** Angenommen, die Beziehung gilt für \( n = k \) und \( n = k-1 \), d.h.: \[ L_k = 2F_{k-1} + F_k \] \[ L_{k-1} = 2F_{k-2} + F_{k-1} \] **Induktionsschritt:** Wir müssen zeigen, dass die Beziehung auch für \( n = k + 1 \) gilt, also: \[ L_{k+1} = 2F_k + F_{k+1} \] Wir verwenden die Rekursionsformeln für Lucas- und Fibonacci-Zahlen: - Lucas-Zahlen: \( L_{n} = L_{n-1} + L_{n-2} \) - Fibonacci-Zahlen: \( F_{n} = F_{n-1} + F_{n-2} \) Setzen wir die Induktionsvoraussetzungen in die Rekursion für \( L_{k+1} \) ein: \[ L_{k+1} = L_k + L_{k-1} \] Einsetzen der Induktionsvoraussetzungen: \[ L_{k+1} = (2F_{k-1} + F_k) + (2F_{k-2} + F_{k-1}) \] Nun fassen wir die Terme zusammen: \[ L_{k+1} = 2F_{k-1} + F_k + 2F_{k-2} + F_{k-1} = 3F_{k-1} + F_k + 2F_{k-2} \] Wir wissen, dass \( F_k = F_{k-1} + F_{k-2} \), also können wir \( F_k \) umschreiben: \[ L_{k+1} = 3F_{k-1} + (F_{k-1} + F_{k-2}) + 2F_{k-2} = 4F_{k-1} + 3F_{k-2} \] Jetzt verwenden wir die Fibonacci-Rekursion: \[ F_{k+1} = F_k + F_{k-1} \] Um \( L_{k+1} \) in der Form \( 2F_k + F_{k+1} \) zu zeigen, setzen wir \( F_k \) und \( F_{k-1} \) in die Gleichung ein: \[ L_{k+1} = 2F_k + (F_k + F_{k-1}) = 2F_k + F_{k+1} \] Somit haben wir gezeigt, dass die Beziehung auch für \( n = k + 1 \) gilt. **Schlussfolgerung:** Da der Induktionsanfang wahr ist und der Induktionsschritt funktioniert hat, gilt die Beziehung \( L_n = 2F_{n-1} + F_n \) für alle \( n > 1 \).