Finding an explicit formula for $a_n$ defined recursively by

Question

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

Answer 1

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}$$

Answer 2

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}$

Answer 3

$\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}