3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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