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

A: In this answer I will provide a solution to the problem:

Given $A_0=1$ and $A_{n+1}=3A_n+2^{n-1}$ for all non-negative $n$, find the expression for $A_n$.

The answer should be $2\times 3^n-2^n$, and here is how you can obtain it without induction. As mentioned in ultrainstinct's answer, this is a inhomogeneous recursive relation and the following is how it can be made homogeneous (with the cost of increasing the order from 1 to 2).
$$A_{n+2}=3A_{n+1}+2^n,$$
$$2A_{n+1}=6A_n+2^n,$$
Substract them to get a homogeneous recurring relation,
$$A_{n+2}=5A_{n+1}-6A_n,$$
The characteristic equation for this is just $x^2-5x+6=0$, and the two roots are $x=2$ and $x=3$. Now you have the general solution,
$$A_n=C_1\times 3^n+C_2\times 2^n,$$
You can determine the constants $C_1$ and $C_2$ from the initial conditions.
A: We can find the general formula with algebra of some operators.
Define $E^k$ on operator that makes $E^k a_n= a_{n+k}$, then we can write that recurrence in the form
$$   (E-3)a_n=2^n\;\;\;\;\;\;(1) $$
We can show that the operator $E-s$ cancel terms in the form $c.s^n$,
$$(E-s)s^n =s^{n+1}-Es^{n}=s^{n+1}-s^{n+1}=0. $$
So apply $E-2$ in $(1)$.
We have
$$(E-2)(E-3)a_n=0. $$
It can be shown, that we can reverse, and find the solution in the form of sums of the terms 
$$a_n=c_12^n+c_23^n \;\;\;\;(2).$$
But now is easy with the initial conditions to find $c_1$ and $c_2$.
From $(1)$,  and applying $(E-3)$ in $(2)$ we have
$$(E-3)a_n=c_1(E-3)2^n=c_1(2^{n+1}-32^n)=c_12^n(2-3)=-c_12^n=2^n .$$
So $c_1=-1$.
Apply $n=0$ in $(2)$,
$$a_0=c_2-1=1, $$
so $c_2=2.$
Then $$a_n=2.3^n-2^n. $$
