Q:

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. 

A:

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

A:

This is a non homogeneous linear recurrence relation. Usually with non-homogeneous equations of this form we split the solution up into a homogeneous one and a particular one. In this case we solve the homogeneous case first, so label it $h_n$.
$$h_{n+1} = 3 h_n$$
assume $h_n = r^n$, plug it in and we get $r^{n+1} = 3r^n$, we can divide out by $r^n$ since a $0$ solution is trivial. Generally if you find a bunch of roots, you take a linear combination of them. So in our case, the homogeneous solution is
$$h_n = c_13^n$$
now onto the particular solution, let's name it $p_n$, in this case we "pick" a solution of the form  $$p_n = a2^n + b$$ now plug it in 
$$a2^{n+1}+b = 3a2^{n} + 3b + 2^n$$
Simplified we get
$$-a2^n -2b = 2^n$$
matching coefficients we get $a=-1$ and $b=0$ so now our solution is
$$A_{n}=p_n+h_n = c_13^n-2^n$$
now use your initial condition of $A_0=1$ to get
$$A_0=1=c_1-1\implies c_1=2$$
So your final solution should be
$$A_n = 2\cdot 3^n - 2^n$$
This doesn't tell you why we chose the forms of the solutions that we did. But this is the general process of solving equations like these.

A:

Solution of the recurrence
  Given sequences $g(n) \neq 0$ and $b(n)$, we have that $f(n)$
  the solution of the recurrence
  $$f(n+1)=g(n).f(n)+b(n)$$
  is given by
  $$f(n)= \bigg(\sum^{n-1}_{p=1}\frac{b(p)}{\prod\limits^{p}_{k=1}g(k)}+f(1) \bigg)\prod^{n-1}_{k=1}g(k). $$
  See the proof here

Now taking $g(n)= 3$ and $b(n) =2^n.$ One obtains 
$$A_n= \prod^{n-1}_{k=1}3\bigg(\sum^{n-1}_{p=1}\frac{2^p}{\prod\limits^{p}_{k=1}3}+A_1 \bigg)=  3^{n-1}\bigg(\sum^{n-1}_{p=1}\frac{2^p}{3^p}+A_1 \bigg)\\=3^{n-1}\bigg(\frac{2}{3}\frac{\left(\frac{2}{3}\right)^{n-1}-1}{\frac{2}{3}-1}+A_1 \bigg)=3^{n-1}\bigg(2\left[1-\left(\frac{2}{3}\right)^{n-1}\right]+A_1 \bigg)\\=\left(2\cdot 3^{n-1}-2^n+ 3^{n-1}\cdot A_1\right).$$

Finally, With $A_1= 4$ since $A_0=1$ $$A_n=\left(2\cdot 3^{n-1}-2^n+ 3^{n-1}\cdot 4\right) = 2\cdot 3^{n}-2^n$$

