Understanding Generating Function 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.)
 A: 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$.
A: 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.
