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

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

• Note that $\binom{n + 1}{n}=n+1$.
– Feng
Aug 7, 2019 at 1:05
• I see no problems at a quick glance. Good work! Aug 7, 2019 at 1:09
• As a check, you can verify that the explicit formula for $f_n$ satisfies the recurrence relation and boundary conditions. Aug 7, 2019 at 21:42

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