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}.$$
Best Answer
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}$$