Um die Beziehung \( L_n = 2F_{n-1} + F_n \) für \( n > 1 \) zwischen den Lucas-Zahlen \( L_n \) und den-Zahlen \( F \) mittels 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_{2-1} + F_2 \] Das ergibt: \[ 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} \] Setzen wir die Induktionsvoraussetzungen ein: \[ L_{k+1} = (2F_{k-1} + F_k) + (2F_{k-2} + F_{k-1}) \] Das vereinfacht sich zu: \[ L_{k+1} = 2F_{k-1} + F_k + 2F_{k-2} + F_{k-1} \] \[ = 2F_{k-1} + 2F_{k-2} + F_k + F_{k-1} \] \[ = (2F_{k-1} + F_{k-1}) + F_k + 2F_{k-2} \] \[ = 3F_{k-1} + F_k + 2F_{k-2} \] Nun verwenden wir die Fibonacci-Rekursion: \[ F_k = F_{k-1} + F_{k-2} \] Setzen wir dies ein: \[ L_{k+1} = 3F_{k-1} + (F_{k-1} + F_{k-2}) + 2F_{k-2} \] \[ = 3F_{k-1} + F_{k-1} + 3F_{k-2} \] \[ = 4F_{k-1} + 3F_{k-2} \] Jetzt müssen wir zeigen, dass dies gleich \( 2F_k + F_{k+1} \) ist: \[ 2F_k + F_{k+1} = 2(F_{k-1} + F_{k-2}) + (F_k + F_{k-1}) = 2F_{k-1} + 2F_{k-2} + F_k + F_{k-1} \] Das zeigt, dass die Beziehung auch für \( n = k + 1 \) gilt. **Schlussfolgerung:** Da der Induktionsanfang wahr ist und der Induktionsschritt gezeigt wurde, gilt die Beziehung \( L_n = 2F_{n-1} + F_n \) für alle \( n > 1 \).