Solving $A_{n+1}=3A_n+2^n$ Let's say I want to find a formula for the following expression given $n$ number of threes
$$\ldots(3(3(3(3(3(3+1)+2)+4)+8)+16)+\ldots$$
If $A_0=1$, then
$$A_{n+1}=3A_n+2^n$$
Plugging in values to see the pattern,
$$A_2 = 3+1$$
$$A_3 = 3^2+3+2^1$$
$$A_4 = 3^3+3^2+3\cdot2+2^2$$
But I don't know how to condense something like this into an explicit formula. 

One way to see the correct answer is to use that:
$$x^n-y^n=(x-y)\left(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}\right)$$
Putting in $x=3,y=2$ you get that:
$$3^n-2^n = 3^{n-1}+3^{n-2}\cdot2+\cdots+3\cdot 2^{n-2}+2^{n-1}$$
Now add $3^n$ to both sides, and you get:
$$2\cdot 3^n -2^n = 3^{n}+3^{n-1}+3^{n-2}\cdot2+\cdots+3\cdot 2^{n-2}+2^{n-1}$$
There are more advanced techniques to solve this sort of equation generally, but this is a good "eyeball" solution without appeal to generating functions.

The generating function approach is to write:
$$f(z)=\sum_{n=0}^{\infty} A_nz^n = A_0 + z\sum_{n=1}^{\infty} (3A_{n-1}+2^{n-1})z^{n-1} = 1+z\left(3f(z)+\frac{1}{1-2z}\right)$$ Solving for $f(z)$ gives us $$f(z)=\frac{1}{1-3z}\left(1+\frac{z}{1-2z}\right)=\frac{1-z}{(1-2z)(1-3z)}$$
You can then use partial fractions to get that:
$$f(z)=\frac{2}{1-3z}-\frac{1}{1-2z}$$
Thus giving $A_n=2\cdot 3^n-2^n.$
