4
$\begingroup$

I'm trying to solve this linear recurrence with generating functions, but I keep getting stuck on the last few steps. I found the generating function, but after splitting it into partial fractions and putting it in sigma notation, I don't know how to simplify it into one summation:

$g_0$=1, $g_1$=2, $g_2$=-2

$g_n$=7$g_{n-1}$-16$g_{n-2}$+12$g_{n-3}$

I got up to the point;

$$\frac{1-5z}{1-7z+16z^2-12z^3}=\frac{7-8z}{(1-2z)^2}+\frac{-6}{1-3z}$$

and finally;

$$=(7-8z)\sum_{n=0}^\infty(n+1)2^nz^n-6\sum_{n=0}^\infty3^nz^n$$

I have no clue what to do now, but the final result should be;

$$g_n=(3n+7)\cdot2^n-6\cdot3^n$$ The question is from here if I missed anything (pg 15-18). Any help would be GREATLY aprreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

$$\begin{align*} (7-8z)\sum_{n\ge 0}(n+1)2^nz^n&=7\sum_{n\ge 0}(n+1)2^nz^n-8\sum_{n\ge 0}(n+1)2^nz^{n+1}\\\\ &=7\sum_{n\ge 0}(n+1)2^nz^n-4\sum_{n\ge 0}(n+1)2^{n+1}z^{n+1}\\\\ &=7\sum_{n\ge 0}(n+1)2^nz^n-4\sum_{n\ge 1}n2^nz^n\\\\ &=7+\sum_{n\ge 1}7(n+1)2^nz^n-\sum_{n\ge 1}4n2^nz^n\\\\ &=7+\sum_{n\ge 1}(3n+7)2^nz^n\\\\ &=\sum_{n\ge 0}(3n+7)2^nz^n\;, \end{align*}$$

so

$$(7-8z)\sum_{n\ge 0}(n+1)2^nz^n-6\sum_{n\ge 0}3^nz^n=\sum_{n\ge 0}\Big((3n+7)2^n-6\cdot3^n\Big)z^n\;,$$

and $g_n=(3n+7)2^n-6\cdot3^n$.

$\endgroup$
2
  • $\begingroup$ Thank you so much! This question has been keeping me up at night the last few days. $\endgroup$
    – user102120
    Oct 22, 2013 at 6:32
  • $\begingroup$ @user102120: You're welcome! $\endgroup$ Oct 22, 2013 at 6:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .