# Ordinary generating function

• Jul 24th 2010, 03:08 PM
oldguynewstudent
Ordinary generating function
$\displaystyle c_{0}=1$ and $\displaystyle c_{n}=3c_{n-1}+3^{n}$ for $\displaystyle n\geq1$

$\displaystyle c_{n}x^{n}=3c_{n-1}x^{n}+3^{n}x^{n}$

$\displaystyle \sum_{n\geq1}c_{n}x^{n}=$$\displaystyle \sum_{n\geq1}3c_{n-1}x^{n}+\sum_{n\geq1}3^{n}x^{n} LHS \displaystyle \sum_{n\geq1}c_{n}x^{n}=$$\displaystyle \left(\sum_{n\geq0}c_{n}x^{n}\right)-1=h(x)-1$

RHS 1st term $\displaystyle \sum_{n\geq1}3c_{n-1}x^{n}=$$\displaystyle 3x\sum_{n\geq1}c_{n-1}x^{n-1}=3xh(x) 2nd term \displaystyle \sum_{n\geq1}3^{n}x^{n}=$$\displaystyle \left(\sum_{n\geq0}3^{n}x^{n}\right)-1$
So $\displaystyle h(x)-1=3xh(x)+\frac{1}{1-3x}-1$; $\displaystyle \left(1-3x\right)h(x)=\frac{1}{1-3x}$ And $\displaystyle h(x)=\frac{1}{\left(1-3x\right)^{2}}$

I don't know how to turn this into the answer in the book which is $\displaystyle c_{n}=(n+1)3^{n}$

• Jul 24th 2010, 06:38 PM
Soroban
Hello, oldguynewstudent!

Quote:

$\displaystyle c_0=1\:\text{ and }\:c_n \:=\:3c_{n-1}+3^n\:\text{ for }n\geq1$

I cranked out the first few terms and looked for a pattern.

. . $\displaystyle \begin{array}{cccccccccc} c_0 &=& 1 &=& 1\cdot1 &=& 1\cdot3^0 \\ c_1 &=& 6 &=& 2\cdot3 &=& 2\cdot3^1 \\ c_2 &=& 27 &=& 3\cdot9 &=& 3\cdot3^2 \\ c_3 &=& 108 &=& 4\cdot27 &=& 4\cdot3^4 \\ c_4 &=& 405 &=& 5\cdot81 &=& 5\cdot3^4 \\ c_5 &=& 1458 &=& 6\cdot243 &=& 6\cdot3^5 \\ \vdots && \vdots && \vdots && \vdots \end{array}$

Therefore: .$\displaystyle c_n \;=\;(n+1)\cdot 3^n$

• Jul 24th 2010, 09:46 PM
roninpro
Your answer looks fine. The last thing you have to do is find the Taylor series for $\displaystyle h(x)=\frac{1}{(1-3x)^2}$.

You can start with the geometric series $\displaystyle \frac{1}{1-x}=1+x+x^2+x^3\ldots+x^n+\ldots$

Then, $\displaystyle \frac{1}{1-3x}=1+3x+9x^2+27x^3+\ldots + 3^nx^n+\ldots$

Now, differentiating both sides, $\displaystyle \frac{3}{(1-3x)^2}=3+18x+81x^2+324x^3+\ldots+n3^nx^{n-1}+\ldots$

Finally, dividing both sides by $\displaystyle 3$, $\displaystyle \frac{1}{(1-3x)^2}=1+6x+27x^2+108x^3+\ldots +n3^{n-1}x^{n-1}+\ldots$

We see that $\displaystyle c_n=n 3^{n-1}$ for $\displaystyle n=2, 3, 4, \ldots$ (You can shift the index by one to get book's solution.)
• Jul 25th 2010, 07:39 AM
Renji Rodrigo
a general solution for recurrences in the form

$\displaystyle f(n+1)=a_n f(n)+b_n$
can be found using this trick

write

$\displaystyle f(n)=h(n) \prod\limits^{n-1}_{k=1} a_k$

then use it on the equation

$\displaystyle h(n+1) \prod\limits^{n}_{k=1} a_k = h(n)\prod\limits^{n}_{k=1} a_k +b_n$

so

$\displaystyle \Delta h(k) =\frac{b_n } {\prod\limits^{n}_{k=1} a_k}$
is a telescoping summation, finding h(n) we find f(n)

by example, puting a_k=3, we have h(0)=3 , by the initial condition so
h(n)=3(n+1) so $\displaystyle f(n)=3^n(n+1)$.
• Jul 25th 2010, 01:54 PM
oldguynewstudent
Yes, I see your point, but in the context of ordinary generating functions, I believe this approach would not go over with my professor.