How to use recurrence to define generating function? How to write generating function as power series?

Question

I am a software engineer teaching myself combinatorics. This problem is destroying me, but I am following what I thought was the appropriate strategy to solve a recurrence. I am also confused as to how to refactor the recursion into a power series.

Problem

Let $G(x) = \sum_0^\infty a_kx^k$ be a generating function. Let $a_0 = 1$ and $a_1 = 0$ and $a_n = 6a_{n-1} + a_{n-2}$ for $n > 1$.

• Show $G(x) = \frac{1-x}{1-x-6x^2}$.
• Find real numbers A and B such that$G(x) = \frac{A}{1-ax} + \frac{B}{1-bx}$ where $(1-ax)(1-bx) = 1 - x - 6x^2$
• Use geometric progression formula to expand $G(x)$ into a power series. Collect terms with $x^n$. The coefficient at $x^n$ will give you formula for $a_n$.

Attempt

1. Show $G(x) = \frac{1-x}{1-x-6x^2}$.

   Using recurrence, it can be clearly seen that we can argue as follows: $G(x) = \sum_0^\infty a_kx^k = \sum_1^\infty6a_{k-1}x^k + \sum_2^\infty a_{k-2}x^k$. Note the sum starts at 1 and 2 on right side because it is not defined for values below this. Thus, we obtain the following expression on the right side by simplifying: $6x + x^2 + \frac{6x^3}{1-x} + \frac{x^4}{1-x}$ because $\sum_m^\infty ax^k = \frac{ax^m}{1-x}$. Clearly, this is wrong. I suspect that I did not set up the recurrence correctly?

2. Find the real numbers A and B.

   I'm really frustrated by this. I get $A + B = 1$ and $Ab + Ba = 1$, but must I find what $a$ and $b$ are first? Otherwise I don't know how it is solvable? Unless in terms of $a$ and $b$ such as $B = \frac{ab+b}{-ab + bb}$ ?

3. Problem expressed as power series. $1 + 1x^2 + 6x^3 + 37x^4 + ...$ Right?

I appreciate your patience while I work through these. I feel stupid, but I don't care. This is how you learn in self study and I would appreciate someone setting me straight on the above. I definitely know 1 is wrong, but not clear on where I went wrong. I think I have the right idea for 2. I'm not quite sure what is being asked for in 3.

Answer 1

I think you mistyped the recurrence; it should probably be $a_n = a_{n-1} + 6a_{n-2}$. Either that or the answer in (1) is wrong (although your answer to (3) corresponds to the recurrence you gave). In any case, to compute the generating function you have to be more careful with the indices. As you correctly point out, the sums on the right start with $i=1$ and $i=2$; you should write \begin{align*} G(x) &= \sum_0^\infty a_kx^k = a_0 + a_1x + \sum_2^{\infty} a_kx^k \\ &= a_0 + a_1x + \sum_2^\infty a_{k-1}x^k + \sum_2^\infty 6a_{k-2}x^k \\ &= 1 + \sum_1^\infty a_kx^{k+1} + \sum_0^\infty 6a_kx^{k+2} \\ &= 1 + x\sum_1^\infty a_kx^k + 6x^2\sum_0^\infty a_kx^k \\ &= 1 + x\sum_0^\infty a_kx^k - x + 6x^2\sum_0^\infty a_kx^k \\ &= 1-x + xG(x) + 6x^2G(x). \end{align*} Solving for $G(x)$ gives $$G(x) = \frac{1-x}{1-x-6x^2}.$$

2. First factor $1-x-6x^2 = (1-3x)(1+2x)$, then use partial fractions.

Answer 2

You cant change the index by will, this is the fail. Every index must be from $k=0$, then you adjust it to get something identical to $G(x)$.

You apply the operator $\sum_{n\ge2}x^n$ to both sides of the equation:

$$\sum_{n\ge2}(a_n)x^n=\sum_{n\ge2}(6a_{n-1}+a_{n-2})x^n=\\ =G(x)-a_1x-a_0=6\sum_{n\ge2}a_{n-1}x^n+\sum_{n\ge2}a_{n-2}x^n=\\ =6x\sum_{n\ge2}a_{n-1}x^{n-1}+x^2\sum_{n\ge2}a_{n-2}x^{n-2}=\\ =6x\sum_{n\ge1}a_{n}x^{n}+x^2\sum_{n\ge0}a_{n}x^{n}=\\ =6x(-a_0+\sum_{n\ge0}a_{n}x^{n})+x^2\sum_{n\ge0}a_{n}x^{n}$$

Then we have $a_0=1$ and $a_1=0$ so

$$G(x)-1=6x(-1+G(x))+x^2G(x)\to\\ G(x)-6xG(x)-x^2G(x)=-6x+1\to \\ G(x)=\frac{6x-1}{x^2+6x-1}$$

Something seems wrong on the original post.