1. Zadatak

Prvo rješenje.

Vrijedi

$$\begin{aligned} a_1&=1\\ a_2&=3a_1+2\\ a_3&=3a_2+2^2\\ &\ldots\\ a_{n-1}&=3a_{n-2}+2^{n-2}\\ a_n&=3a_{n-1}+2^{n-1} \end{aligned}$$

Pomnožimo prvu jednakost s $3^{n-1}$, drugu s $3^{n-2}$, treću s $3^{n-3}$, …, predzadnju s 3,

$$\begin{aligned} 3^{n-1}a_1&=3^{n-1}\\ 3^{n-2}a_2&=3^{n-1}a_1+2\cdot3^{n-2}\\ 3^{n-3}a_3&=3^{n-2}a_2+2^2\cdot3^{n-3}\\ &\ldots\\ 3a_{n-1}&=3^2a_{n-2}+2^{n-2}\cdot3\\ a_n&=3a_{n-1}+2^{n-1} \end{aligned}$$

te ih sve zbrojimo. Dobivamo:

$$\begin{aligned} a_n&=3^{n-1}+2\cdot3^{n-2}+2^2\cdot3^{n-3}+\ldots+2^{n-1}\\ &=3^{n-1}+\frac23\cdot3^{n-1}+\left(\frac23\right)^2\cdot3^{n-1}+\ldots+\left(\frac23\right)^{n-1}\cdot3^{n-1}\\ &=3^{n-1}\cdot\frac{1-\left(\frac23\right)^n}{1-\frac23}=3^n-2^n. \end{aligned}$$

Dakle, $a_n=3^n-2^n$.

Drugo rješenje.

Zadatak se može riješiti i matematičkom indukcijom, ukoliko se formula za opći član uspije naslutiti.

Izračunajmo nekoliko prvih članova niza:

$$\begin{aligned} a_1&=1\\ a_2&=3a_1+2=3\cdot1+2=5\\ a_3&=3a_2+2^2=3\cdot5+4=19\\ a_4&=3a_3+2^3=3\cdot19+8=65\\ &\ldots \end{aligned}$$

Uočimo da je $a_1=3-2$, $a_2=9-4$, $a_3=27-8$, $a_4=81-16$. Stoga naslućujemo da vrijedi $a_n=3^n-2^n$ za sve $n\in\mathbb N$. To ćemo dokazati matematičkom indukcijom. Baza indukcije vrijedi. Pretpostavimo da je za neki prirodan broj $k$, $a_k=3^k-2^k$. Tada je

$$\begin{aligned} a_{k+1}&=\text{ (prema danoj rekurziji) }=3\cdot a_k+2^k\\ &=\text{ (prema pretpostavci) }=3\cdot(3^k-2^k)+2^k\\ &=3\cdot3^k-3\cdot2^k+2^k=3^{k+1}-2^{k+1}. \end{aligned}$$

Dakle, ako je $a_k=3^k-2^k$, onda je $a_{k+1}=3^{k+1}-2^{k+1}$. Sada prema principu matematičke indukcije zaključujemo da za sve $n\in\mathbb N$ vrijedi $a_n=3^n-2^n$, što smo i htjeli pokazati.