<s>[INST] 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. 
 [/INST] 
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$$

</s>