Determine an explicit form for the generating function and a closed form given a recurrence

Question

Let $f_n = 4f_{n-1} - 4f_{n-2}$ be a recurrence relation for $f$ with initial conditions $f_0 = 1$ and $f_1 = 4$. I want to determine an explicit form for the generating function of $f$, $F(x)$ as well as a closed form for $f_n$. I'd appreciate someone verifying if my attempt at a solution is correct.

Rearranging the recurrence relation yields $f_n - 4f_{n-1} + 4f_{n-2} = 0$ and then I can take the generating function of both sides to get:

$$\sum_{n \geq 2}(f_n - 4f_{n-1} + 4f_{n-2})x^n=0.$$

Splitting this up yields:

$\begin{align*} 0 &= \sum_{n \geq 2}f_nx^n - 4\sum_{n \geq 2}f_{n-1}x^n + 4\sum_{n \geq 2}f_{n-2}x^n\\ &= \sum_{n \geq 0}f_nx^n - 4x - 1 - 4\sum_{n \geq 2}f_{n-1}x^n + 4\sum_{n \geq 2}f_{n-2}x^n\\ &= F(x) - 4x - 1 -4x\sum_{n \geq 2}f_{n-1}x^{n-1} + 4x^2\sum_{n \geq 2}f_{n-2}x^{n-2}\\ &= F(x) - 4x - 1 -4x(F(x) - 1) + 4x^2F(x).\\ \end{align*}$

Now we can solve for $F(x)$ which yields $F(x) = \frac{1}{(1-2x)^2}$ so this is the generating function. But using the binomial theorem for negative powers we have:

$$F(x) = (1- 2x)^{-2} = \sum_{k=0}^{\infty}\binom{2 + k - 1}{k}(-1)^k(-2x)^k.$$

Extracting the $n$th coefficient yields $f_n = \binom{n + 1}{n} \cdot 2^n$.

Answer 1

Define the generating function $F(z) = \sum_{n \ge 0} f_n z^n$, multiply the recurrence shifted by $2$ by $z^n$ and sum over $n \ge 0$, recognize some sums:

$\begin{align*} \sum_{n \ge 0} f_{n + 2} z^n &= 4 \sum_{n \ge 0} f_{n + 1} z^n - 4 \sum_{n \ge 0} f_n z^n \\ \frac{F(z) - f_0 - f_1 z}{z^2} &= 4 \frac{F(z) - f_0}{z} - 4 F(z) \end{align*}$

Solve for $F(z)$:

$\begin{align*} F(z) &= \frac{1}{(1 - 2 z)^2} \\ &= \sum_{n \ge 0} (-1)^n \binom{-2}{n} (2 z)^n \\ &= \sum_{n \ge 0} \binom{n + 2 - 1}{2 - 1} 2^n z^n \end{align*}$

Extracting the coefficient of $z^n$ you get:

$\begin{align*} f_n &= [z^n] F(z) \\ &= \binom{n + 1}{1} \cdot 2^n \\ &= (n + 1) \cdot 2^n \end{align*}$