, 2011

Evaluating the first few terms, one finds $a_1 = 1$, $a_2 = 5$, $a_3 = 19$, $a_4 = 65$, $a_5 = 211$ and $a_6 = 665$. The values always increase by a factor of $3$, plus a little bit. A guess is that the terms are similar to $3^n$, and computing the difference one fits it to be $2^n$. We'll show by induction that $a_n = 3^n - 2^n$.

The base case ($n=1$) works. Then, for all $n \in \mathbb{N}$,
$$a_{n+1} = 3a_n + 2^n = 3(3^n - 2^n) + 2^n = 3^{n+1} - 3 \cdot 2^n + 2^n = 3^{n+1} - 2^{n+1},$$
as required, so the induction holds and $a_n = 3^n - 2^n$ for all $n \in \mathbb{N}$.