Non-homogenous recurrence relation I need to solve the recurrence relation  $A(n)=2A(n-2)+ 2^{n-2}$. I tried writing out equations up to the $A(2)$ and multiplying by powers of two and adding all the equations together  then all the terms cancelled but after that I couldn't find the sum of the powers of two. I forgot to mention that the base is $A(2)=2$ and n is even
 A: Let us compute some values of A(n):
$n=2, A(2)=2$
$n=4, A(4)=2A(2)+2^2=8=2^3$
$n=6, A(6)=2A(4)+2^4=32=2^5$
$n=8, A(8)=2A(6)+2^6=128=2^7$
You should see the pattern, It seems that $A(n)=2^{n-1}$. This is true and can be easily shown by induction.
A: You do this much the same way as you might solve a differential equation: first find the general solution to the homogeneous part of the equation, and then find a particular solution that you can add to that general solution.  
The homogeneous equation here is:
$$
A(n)=2A(n-2)
$$
Because $n$ is even, the general solution to this is easily seen to be:
$$
A_C(n)=B.2^{n/2}
$$
where $B$ is an arbitrary constant.  
We now seek a particular solution.  One thing we could try would be just setting:
$$
A_P(n)=2^{n-2}
$$
But then $2A_P(n-2)+2^{n-2}=2^{n-1}+2^{n-2}\neq2^{n-2}$.
That didn't work.  We somehow need to find some way to make the two terms on the left combine into one term.  If we try
$$
A_P(n)=2^{n-1}
$$
then we get:
$$
2A_P(n-2)+2^{n-2}=2^{n-2}+2^{n-2}=2^{n-1}=A_P(n)
$$
Thus, $A_P(n)=2^{n-1}$ is a particular solution to the equation.  The general solution then is:
$$
A(n)=A_C(n)+A_P(n)=B.2^{n/2}+2^{n-1}
$$
Since $A(2)=2$, we have
$$
2=B.2^1+2^1=2B+2
$$
So $B=0$, and the solution is $A(n)=2^{n-1}$.  
A: It never hurts in such problems to start by gathering some numerical data:
$$\begin{array}{rcc}
n:&2&4&6&8&10&12\\
A(n):&2&8&32&128&512&2048\\
A(n):&2^1&2^3&2^5&2^7&2^9&2^{11}
\end{array}$$
There’s a very obvious pattern here, that leads to the conjecture that $A(n)=2^{\text{what function of }n?}$ if $n$ is even. Complete the conjecture correctly, and you should have little difficulty using mathematical induction to prove that it’s correct.
Alternatively, let $B(n)=A(2n)$; then $$B(n)=2B(n-1)+2^{2(n-1)}=2B(n-1)+4^{n-1}\;,$$
and ‘unwrap’ the recurrence:
$$\begin{align*}
B(n)&=2B(n-1)+4^{n-1}\\
&=2\Big(2B(n-2)+4^{n-2}\Big)+4^{n-1}\\
&=2^2B(n-2)+2\cdot 4^{n-2}+4^{n-1}\\
&=2^2\Big(B(n-3)+4^{n-3}\Big)+2\cdot 4^{n-2}+4^{n-1}\\
&=2^3B(n-3)+2^2\cdot4^{n-3}+2\cdot 4^{n-2}+4^{n-1}\\
&\;\vdots\\
&=2^kB(n-k)+2^{k-1}\cdot 4^{n-k}+2^{k-2}\cdot 4^{n-k+1}+\ldots+2\cdot 4^{n-2}+4^{n-1}\\
&\;\vdots\\
&=2^{n-1}B(1)+\sum_{i=1}^{n-1}2^{i-1}\cdot4^{n-i}\\
&=2^n+\sum_{i=1}^{n-1}2^{i-1}\cdot4^{n-i}\\
&=2^n+\sum_{i=1}^{n-1}2^{i-1}\cdot2^{2n-2i}\\
&=2^n+\sum_{i=1}^{n-1}2^{2n-i-1}\\
&=2^n+\sum_{i=n}^{2n-2}2^i\\
&=2^n+2^n\sum_{i=0}^{n-2}2^i\\
&=2^n\left(1+\sum_{i=0}^{n-2}2^i\right)\\
&=\;?
\end{align*}$$
A: Generating functions to the rescue. Define $g(z) = \sum_{n \ge 0} A(n) z^n$, write:
$$
A(n + 2) + 2 A(n) + 2^n
$$
Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums to get:
$$
\frac{g(z) -A(0) - A(1) z}{z^2} = 2 A(z) + \frac{1}{1 - 2 z}
$$
As partial fractions:
$$
A(z)
  = \frac{1 - 2 A(0) - 2 (A(1) - 1) z}{2 (1 - 2 z^2)} + \frac{1}{2 (1 - 2 z)}
$$
You could now split the first term into partial fractions (but with irrational coefficients) or just take:
\begin{align}
\frac{1}{1 - 2 z^2}
  &= \sum_{n \ge 0} 2^n z^{2 n} \\
\frac{z}{1 - 2 z^2}
  &= \sum_{n \ge 0} 2^n z^{2 n + 1}
\end{align}
i.e., split into even and odd cases.
The second term is just a geometric series.
