<s>[INST] Finding an explicit formula for $a_n$ defined recursively by The sequence $a_n$ is defined recursively by $a_0=0$, $a_n=4a_{n-1}+1$. I must use generating functions to solve this. $n\geq1$.
I have found a pattern:
$$\sum_{n=1}^\infty(4a_{n-1}+1)x^n = x+5x^2+21x^3+85x^4+341x^5+\ldots$$
If we subtract 1 from each term, respectively (ignoring the first term) we would have:
$$x+4x^2+20x^3+84x^4+340x^5+\ldots$$
As you can see, the pattern is the second term increases by 4, the third term increases by 4^2, the fourth term increases by 4^3, and the fifth term increases by 4^4. I wanted to use the formula for the geometric series, but the common ratio isn't 4, but $4^n$. Is there any way I can use this pattern to help me find the explicit formula, using generating functions?
Using $$\sum_{n=0}^\infty 4^nx^n = \frac{1}{1-4x}$$ Isn't helping me too much. But I have a feeling I can manipulate this generating function to solve this.
However, this might seem helpful:
$$\sum_{n=0}^\infty4^nx^{n+1} = 4^0x+4^1x^2+4^2x^3+4^3x^4+\ldots = x+4x^2+16x^3+64x^4+\ldots$$ 
After some work I have gotten this:
$$A(x)=\frac{x^2}{(1-x)(x-4)}$$ Where $A(x)$ is our unknown generating function (which we have been looking for). But I don't think this is correct because it does not match the answer down below. 
Edit: I have finally figured it out, I will be back with my LaTex code to present it.
Final edit:
Find an explicit formula for $a_n$ using the generation function technique.
\newline We will begin by multiplying each side by $x^n$ and summing over $n\geq1$. We will also let $A(x)=\sum_{n=0}^\infty a_nx^n$ be the unknown generating function which we are looking for.
$$\begin{align*}
\implies \sum_{n=1}^\infty a_nx^n&=\sum_{n=1}^\infty (4a_{n-1}+1)x^n
\end{align*}
$$
Because
$a_0=0$ is given, we can rewrite $A(x)$:
$$
\begin{align*} 
A(x)=a_0+\sum_{n=1}^\infty a_nx^n=\sum_{n=1}^\infty a_nx^n
\end{align*}
$$
Now, we continue to manipulate our equality.
$$
\begin{align*}
\implies \sum_{n=1}^\infty a_nx^n&=\sum_{n=1}^\infty (4a_{n-1}+1)x^n \\[2mm]
&=\sum_{n=1}^\infty 4a_{n-1}x^n + x^n \\[2mm]
&=\sum_{n=1}^\infty 4a_{n-1}x^n+\sum_{n=1}^\infty x^n \\[2mm]
&=\sum_{n=1}^\infty 4a_{n-1}x^n+ \frac{x}{1-x} \\[2mm]
&=\sum_{n=0}^\infty 4a_{n}x^{n+1}+ \frac{x}{1-x} \\[2mm]
&=a_0+\sum_{n=1}^\infty 4a_{n}x^{n+1}+ \frac{x}{1-x} \\[2mm]
&=\sum_{n=1}^\infty 4a_{n}x^{n+1}+ \frac{x}{1-x} \\[2mm]
&=4x\sum_{n=1}^\infty a_{n}x^{n}+ \frac{x}{1-x}. \\[2mm]
\end{align*}$$
It is clear now, that we have a multiple of our previously stated $A(x)$ on the left and right hand side.
$$
\begin{align*}
\implies&\sum_{n=1}^\infty a_{n}x^{n}=4x\sum_{n=1}^\infty a_{n}x^{n}+ \frac{x}{1-x} \\[2mm]
\implies&A(x)=4xA(x)+\frac{x}{1-x} \\[2mm]
\implies&A(x)-4xA(x)=\frac{x}{1-x}\\[2mm]
\implies& A(x)(1-4x)=\frac{x}{1-x}\\[2mm]
\implies& A(x)=\frac{x}{(1-x)(1-4x)}=\frac{x}{4x^2-5x+1} \\[2mm]
\end{align*}$$
Thus, the explicit formula for $a_n$ is given by $A(x)=\dfrac{x}{4x^2-5x+1}$ through the use of generating functions.
Finally, it follows that we have $$A(x)=\sum_{n=0}^\infty\frac{4^n-1}{3}x^n=\frac{x}{4x^2-5x+1}.$$
 [/INST] The characteristic equation for the homogenous part is: $x^2 - 4x = 0$ gives: $x = 0$ and $x = 4$. So the solution to the equation is: $a_n = c\cdot 4^n + b$. Now $a_0 = 0$ and $a_1 = 1$ gives: $0 = c + b$, and $1 = 4c + b$. So $b = -c$, and $c = \dfrac{1}{3}$, and $b = -\dfrac{1}{3}$. So: $a_n = \dfrac{4^n - 1}{3}$
</s>