2
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.