2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why is your summation become $\frac{1}{1-x} -1$ I am sorry. I don't see this sir. $\endgroup$ – hlyates Dec 8 '15 at 2:22
  • $\begingroup$ Based on identities shouldn't $\sum_1^\infty2x^k = \frac{2x}{1-x}$? $\endgroup$ – hlyates Dec 8 '15 at 2:35
  • $\begingroup$ It is, and it works out even better with that expression. $\endgroup$ – hlyates Dec 8 '15 at 2:48
  • $\begingroup$ @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 $$ $\endgroup$ – gt6989b Dec 8 '15 at 18:43

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.