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