Hallo,
Bei Aufgabe 5.2 benötigst Du für den Induktionsanfang zwei Glieder der Folge, die durch \(2\) teilbar sind:$$f_0 = 0; \quad 3\mid n \land 2 \mid f_0\space \checkmark \\f_3 = 2; \quad 3\mid n \land 2 \mid f_3\space \checkmark $$Weiter gilt folgender Zusammenhang$$\begin{aligned} f_{n+3} &= f_{n+2} + f_{n+1} \\ &= (f_{n+1} + f_{n}) + (f_{n} + f_{n-1}) \\ &= (f_{n} + f_{n-1}) + 2 f_{n} + (f_{n-2}+f_{n-3}) \\ &= 3f_{n} + \underbrace{f_{n-1} + f_{n-2}}_{=f_{n}} + f_{n-3} \\ &= 4f_{n} + f_{n-3} \end{aligned}$$Für \(n \ge 3\) git also: Ist \(n\) durch \(3\) teilbar und somit auch \(n-3\) durch \(3\) teilbar und lt. Induktionsvoraussetzung sind dann \(f_n\) und \(f_{n-3}\) durch \(2\) teilbar, dann muss auch \(f_{n+3}\) durch \(2\) teilbar sein, da sich \(f_{n+3}\) aus einer (ganzzahligen) Linearkombination von \(f_n\) und \(f_{n-3}\) zusammen setzt.
Da zu beweisen ist, dass \(2\) (nur) genau dann \(f_n\) teilt, wenn \(n\) durch \(3\) teilbar ist, muss man nun noch zeigen, dass \(2 \nmid f_n\) wenn \(n \not\equiv 0 \mod 3\).
Das zeigt man genauso einmal für \(n \equiv 1 \mod 3\) und einmal für \(n \equiv 2 \mod 3\). Induktionsvoraussetzung für \(n \equiv 1 \mod 3\) ist$$f_1 = 1, \quad n \equiv 1 \mod 3 \quad \land \quad 2 \nmid f_1 \space \checkmark\\f_4 =3, \quad n \equiv 1 \mod 3 \quad \land \quad 2 \nmid f_4 \space \checkmark$$Und der Induktionsschritt lautet:$$f_{n+3} = 4 f_n + f_{n-3} \implies 2 \nmid f_{n+3} \space \text{wenn}\space 2 \nmid f_{n-3} $$usw.
