Understanding Generating Function

Question

I have been looking at This Problem and Answer about generating functions. The problem asked for the generating function of: $$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1$$ I understand how Ron Gordon simplified it to: $$\sum_{n=2}^{\infty} (a_n-4 a_{n-1}+4 a_{n-2}) x^n = \sum_{n=2}^{\infty} n(n-1)2^{n-1} x^n + \sum_{n=2}^{\infty} x^n$$ and where he defined the generating function as: $$g(x) = \sum_{n=0}^{\infty} a_n x^n$$but then he broke the summation into $3$ seperate summations and this is where I start to get messed up. I do understand in the first summation how we can get: $$\sum_{n=2}^\infty a_nx^n=\sum_{n=0}^\infty a_nx^n-(a_0+a_1x)$$I don't understand the next two summations though.

Question:

1) In the second and third summation where did the $x$ and $x^2$ come from?

2) Do you always multiply by $x^n$ in generating functions? or does it change?

3) I believe I remember my professor saying that every generating function would always be $f(x)=\sum_{n=0}^na_nx^n$ but why is that the case?

4) I guess my overall trouble is understanding what the goal of a generating function is.

Any help would be much appreciated!

(I have looked at other questions, but I can't find a clear answer. So if there is one out there that I missed that answers this I'd be happy to delete my question. Thanks.)

Answer 1

First, we want to manipulate things so that the subscript of the coefficients matches the exponents: \begin{align*} \textsf{LHS} &= \sum_{n=2}^{\infty}a_nx^n - 4\sum_{n=2}^{\infty}a_{n-1}x^n + 4 \sum_{n=2}^{\infty}a_{n-2}x^n \\ &= \sum_{n=2}^{\infty}a_nx^n - 4x\sum_{n=2}^{\infty}a_{n-1}x^{n-1} + 4x^2 \sum_{n=2}^{\infty}a_{n-2}x^{n-2} \\ \end{align*} Next, we want to make a change of variables so that each summation involves $a_nx^n$. Let $s := n - 1$ for the second summation and let $t := n - 2$ for the third summation. Then $s$ ranges from $1$ to $\infty$ and $t$ ranges from $0$ to $\infty$. After making this substitution, we can switch back to $n$ by letting $n := s$ for the second summation and $n := t$ for the third summation. This part might seem weird, but just remember that the the indexing variable is just a dummy variable that can be replaced however we like (provided that the new variables are still nonnegative integers): \begin{align*} \textsf{LHS} &= \sum_{n=2}^{\infty}a_nx^n - 4x\sum_{s=1}^{\infty}a_{s}x^{s} + 4x^2 \sum_{t=0}^{\infty}a_{t}x^{t} \\ &= \sum_{n=2}^{\infty}a_nx^n - 4x\sum_{n=1}^{\infty}a_{n}x^{n} + 4x^2 \sum_{n=0}^{\infty}a_{n}x^{n} \\ \end{align*} Next, we want to make all the summation indices start from $0$: \begin{align*} \textsf{LHS} &= \left[\sum_{n=0}^{\infty}a_nx^n - a_0 - a_1x \right] - 4x \left[\sum_{n=0}^{\infty}a_{n}x^{n} - a_0 \right] + 4x^2 \left[\sum_{n=0}^{\infty}a_{n}x^{n} \right] \\ &= (1 - 4x + 4x^2)\sum_{n=0}^{\infty}a_{n}x^{n} + (4a_0 - a_1)x - a_0 \\ &= (1 - 4x + 4x^2)g(x) + 3x - 1 \\ \end{align*}

Thus, provided that we can also simplify the right hand side, it follows that: $$ g(x) = \frac{\textsf{RHS} - (3x - 1)}{1 - 4x + 4x^2} $$ which can hopefully be expressed in the form $\sum a_n x^n$ to get our desired coefficients $a_n$.

Answer 2

Easiest is to define:

$$ A(z) = \sum_{n \ge 0} a_n z^n $$

then shift indices so there aren't subtractions there:

$$ a_{n + 2} = 4 a_{n + 1} - 4a_n + \binom{n + 2}{2} 2^{n + 2} + 1 $$

Multiply by $z^n$ and sum over $n \ge 0$:

$$ \sum_{n \ge 0} a_{n + 2} z^n = 4 \sum_{n \ge 0} a_{n + 1} z^n - 4 \sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} \binom{n + 2}{2} 2^{n + 2} + \sum_{n \ge 0} z^n $$

We recognize:

$\begin{align} \sum_{n \ge 0} a_{n + k} z^n &= \frac{A(z) - a_0 - a_1 z - \dotsb - a_{k - 1} z^{k - 1}}{z^k} \\ \sum_{n \ge 0} \binom{n + 2}{2} 2^{n + 2} &= \sum_{n \ge 0} \binom{n}{2} 2^n z^n \\ &= \frac{(2 z)^2}{(1 - 2 z)^3} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \end{align}$

Replace in the sum above:

$$ \frac{A(z) - a_0 - a_1 z}{z^2} = 4 \frac{A(z) - a_0}{z} - 4 A(z) + \frac{(2 z)^2}{(1 - 2 z)^3} - 1 - 4 z + \frac{1}{1 - z} $$

Solve for $A$:

$$ A(z) = \frac{a_0 + (a_1 + 11 a_0) z - (7 a_1 - 46 a_0 - 1) z^2 + (18 a_1 - 92 a_0 - 6) z^3 - (20 a_1 - 88 a_0 - 16) z^4 + (8 a_1 - 32 a_0 - 12) z^5 } {1 - 11 z + 50 z^2 - 120 z^3 + 160 z^4 - 112 z^5 + 32^6} $$

Expand this as partial fractions, and read off the coefficients.