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.$