2. Zadatak

Primijetimo da je $a_0=1=2^{2\cdot0}$, $a_1=4=2^{2\cdot1}$, $a_2=16=2^{2\cdot2}$ itd.

Tvrdimo da je $a_n=2^{2n}=(2^n)^2$ za svaki nenegativni cijeli broj $n$.

Tvrdnju ćemo dokazati koristeći matematičku indukciju.

Već smo uočili da tvrdnja vrijedi za $n=0$ i $n=1$.

Pretpostavimo da za neki prirodni broj $n\geq2$ vrijedi da je

$$a_{n-2}=2^{2(n-2)}\qquad\text{i}\qquad a_{n-1}=2^{2(n-1)}.$$

Tada je

$$\begin{aligned} a_n&=3a_{n-1}+4a_{n-2}\\ &=3\cdot2^{2n-2}+4\cdot2^{2n-4}\\ &=3\cdot2^{2n-2}+2^{2n-2}\\ &=4\cdot2^{2n-2}=2^{2n}. \end{aligned}$$

Po principu matematičke indukcije zaključujemo da je uistinu $a_n=2^{2n}$ za svaki nenegativni cijeli broj $n$, čime je tvrdnja zadatka dokazana.