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}.$$
 A: A way to go about this is to define
$$f(x) = \sum_{n=0}^{\infty} a_n x^n$$
Then
$$x f(x) = \sum_{n=0}^{\infty} a_n x^{n+1} = \sum_{n=1}^{\infty} a_{n-1} x^n$$
Using your recurrence, we find that
$$(1-4 x) f(x) = a_0 + \sum_{n=1}^{\infty} (a_n-4 a_{n-1}) x^n = a_0 + \sum_{n=1}^{\infty} x^n = a_0 + \frac{x}{1-x}$$
Note that $a_0=0$, so that we now have the generating function $f(x)$:
$$f(x) = \frac{x}{(1-x)(1-4 x)} = \frac{x}{1-5 x+4 x^2}$$
A: 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}$
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
A particular solution is $\ds{-\,{1 \over 3}}$.
Then
$\ds{\pars{~\mbox{with}\ a_{0} = 0~}}$,
\begin{align}
a_{n} + {1 \over 3} & =
4\pars{a_{n - 1} + {1 \over 3}} =
4^{2}\pars{a_{n - 2} + {1 \over 3}} =
4^{3}\pars{a_{n - 3} + {1 \over 3}}
\\[5mm] & = \cdots =
4^{n}\pars{a_{0} + {1 \over 3}} = {4^{n} \over 3}
\implies
\bbx{a_{n} = {4^{n} - 1 \over 3}} \\ &
\end{align}
