Aloha :)
Um eine Idee für eine geschlossene Formel zu bekommen, rechnen wir weitere Folgenglieder aus:$$a_2=18\quad;\quad a_3=62\quad;\quad a_4=258\quad;\quad a_5=1022\quad;\quad a_6=4098$$Es fällt sofort auf, dass alle Werte nahe bei einer Zweier-Potenz liegen, genauer weichen sie um den Wert \(2\) nach oben oder unten von einer Zweierpotenz ab. Wir können daher folgende Vermutung aufstellen:$$\text{Vermutung: }\quad a_n=2^{2n}+(-1)^n\cdot2\quad;\quad n\ge0$$Wir beweisen unsere Vermutung durch vollständige Induktion:
1) Verankerung bei \(n=0\):$$a_0=3\quad;\quad a_0=2^{2\cdot0}+(-1)^0\cdot2=2^0+2=3\quad\checkmark$$2) Induktionsschritt \(n\to n+1\):$$a_{n+1}=3a_{n}+4a_{n-1}$$$$\phantom{a_{n+1}}\stackrel{\text{I.V.}}{=}3\cdot(2^{2n}+(-1)^{n}\cdot2)+4\cdot(2^{2(n-1)}+(-1)^{n-1}\cdot2)$$$$\phantom{a_{n+1}}=3\cdot2^{2n}+(-1)^{n}\cdot6+4\cdot2^{2n-2}+(-1)^{n-1}\cdot8$$$$\phantom{a_{n+1}}=3\cdot2^{2n}\underbrace{-(-1)^1}_{=(+1)}(-1)^{n}\cdot6+\underbrace{2^2}_{=4}\cdot2^{2n-2}+\underbrace{(-1)^2}_{=1}(-1)^{n-1}\cdot8$$$$\phantom{a_{n+1}}=3\cdot2^{2n}-(-1)^{n+1}\cdot6+2^{2n}+(-1)^{n+1}\cdot8$$$$\phantom{a_{n+1}}=4\cdot2^{2n}+(-1)^n\cdot(-6+8)$$$$\phantom{a_{n+1}}=2^{2n+2}+(-1)^n\cdot2$$$$\phantom{a_{n+1}}=2^{2(n+1)}+(-1)^n\cdot2\quad\checkmark$$Damit ist unsere Vermutung bewiesen.
