# How to prove the recurrence relation for this generating function problem?

I am a software engineer and I am learning combinatorics theory on my own. I recently got stumped by the following problem.

## Problem

Let $a_{0} = 2$ where $a_{n} = 3a_{n-1} - 2$ with $n>0$. Given $G(x) = \sum_1^na_{k}x^k$ be the generating function. Prove $G(x) = \frac{2-4x}{(1-3)(1-x)}$

## Attempt

Let us begin with $a_k = 3a_{k-1} -2$ so that we can see $a_k x^k = 3a_{k-1}x^k -2x^k$. Next we note $\sum_0^na_{k}x^k = \sum_0^k3a_{k-1}x^k -\sum_0^k2x^k$. Simplifying further, we obtain $G(x) = 3xG(x)-\sum_0^k2x^k$. Thus, we have $G(x)(1-3x) = -\sum_0^k2x^k$

## Huh?

How can $-\sum_0^k2x^k = \frac{2-4x}{(1-x)}$? I dare sare I have made an error in my approach above, but I cannot see it. I feel like I got so close to solving this, but completely missed the boat. Please help.

You have to be careful with both upper and lower index. Let $G(x) = \sum_n a_n x^n$ then you recurrence says $$\begin{split} G(x) &= \sum_{k=0}^\infty a_k x^k \\ &= a_0 + \sum_{k=1}^\infty 3 a_{k-1} x^k - \sum_{k=1}^\infty 2 x^k \\ &= 2 + 3x \sum_{k=1}^\infty a_{k-1} x^{k-1} - 2 \left[\frac{1}{1-x} - 1\right] \\ &= 4 + 3x \sum_{k=0}^\infty a_k x^k - \frac{2}{1-x} \\ &= 4 + 3x G(x) - \frac{2}{1-x} \end{split}$$ so you end up with $$G(x) = 4 + 3x G(x) - \frac{2}{1-x}$$ which you can now solve for $G(x)$
• Why is your summation become $\frac{1}{1-x} -1$ I am sorry. I don't see this sir. – hlyates Dec 8 '15 at 2:22
• Based on identities shouldn't $\sum_1^\infty2x^k = \frac{2x}{1-x}$? – hlyates Dec 8 '15 at 2:35
• @hlyates Leaving out the factor of $2$, note that $$\frac{1}{1-x} - 1 = \frac{x}{1-x}...$$ The logic is simple $$\sum_{k=1}^\infty x^k = \sum_{k=0}^\infty x^k - x^0 = \frac{1}{1-x} - 1$$ – gt6989b Dec 8 '15 at 18:43