Solve for $a_{n}$ where $a_{n} = 4a_{n-1} + 2^{2n-1}$, $a_0=1$ and $a_1=6$ . $a_{n} = 4a_{n-1} + 2^{2n-1}$, $a_0=1$ and $a_1=6$.
So I am trying to find $a_n$ by using the generating function let's call it $A(x)$.
the equation then is written as (if I doing this correctly) :
$A(x)-ao = 4xA(x) + \sum_{k=1}2^{2n-1}*x^k$
now for  $\sum_{k=0}2^{2n-1}*x^k = \sum_{k=1}\frac{1}{2}4^{k}x^k \mapsto \frac{1}{2}\frac{1}{1-4x} - \frac{1}{2}$
Then we have: $(1-4x)A(x)= 1+\frac{1}{2}\frac{1}{1-4x} -\frac{1}{2}\Rightarrow A(x)=\frac{1}{2}\frac{1}{1-4x}+\frac{1}{2}\frac{1}{(1-4x)^2}\\ \Rightarrow a_n= ? $
$ (1-4x)^{-2} \mapsto 1 + \sum_{k=1}\binom{2+k-1}{k}*4^kx^{k}\\ \Rightarrow \frac{1}{(1-4x)^2}= 1+ \sum_{k=1}\binom{1+k}{k}*4^kx^{k} = 1+ \sum_{k=1}(k+1)4^kx^{k}= \sum_{k=0}(k+1)4^kx^{k}$
$And, \frac{1}{1-4x} \mapsto 4^n$
So $an = \frac{1}{2}4^n + \frac{1}{2}(n+1)4^n$  agrees with a1 = 6
 A: Note, you didn't provide the boundary value for $a_1$.
Do you specifically want to use a GF? If you set
$$
b_n = \frac{a_n}{2^{2n-1}}
$$
to get (since $2(n-1)-1 = 2n -3$)
$$
b_n = b_{n-1} + 1
$$
and,
$$
a_n = 2^{n-2}a_1 + 2^{n-1}
$$
A: Your initial equation for $A(x)$ is incorrect. You need to work the boundary condition $a_0 = 1$ into the equation.  (The condition $a_1=6$ is redundant, since it can be computed from $a_0$ and the recurrence relation.)
There is more than one way to do this, but one way is to write the recurrence equation so it is true for all $n$.  Although you did not state the restriction, the equation $a_n = 4 a_{n-1}+2^{2n-1}$ only holds for $n \ge 1$.  It is important to state such restrictions explicitly in order to avoid errors.
So here is how to revise the equation so it holds for all $n$.  Notice that if we simply let $n=0$ in the original equation, we have $1 = 0 + 2^{-1}$, which is obviously false. (We adopt the convention that $a_n = 0$ for all $n < 0$.) To patch things up, we write
$$a_n = 4 a_{n-1}+2^{2n-1} + (1/2) \delta_{0n}$$
where $\delta$ is the Kronecker delta function.  Now we have a relation that is true for all $n$, so
$$a_n x^n = 4 a_{n-1} x^n +2^{2n-1} x^n + (1/2) \delta_{0n} x^n$$
for all $n$. Summing over $n=0,1,2,\dots$, we have
$$\sum_{n=0}^{\infty} a_n x^n = 4 \sum_{n=0}^{\infty} a_{n-1} x^n + \sum_{n=0}^{\infty}2^{2n-1} x^n + 1/2 $$
so
$$A(x) = 4x A(x) + \frac{1}{2} \cdot \frac{1}{1-4x} + \frac{1}{2}$$
Maybe you can take it from here.
