# Ordinary generating function

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

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

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

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

RHS 1st term $\sum_{n\geq1}3c_{n-1}x^{n}=$ $3x\sum_{n\geq1}c_{n-1}x^{n-1}=3xh(x)$

2nd term $\sum_{n\geq1}3^{n}x^{n}=$ $\left(\sum_{n\geq0}3^{n}x^{n}\right)-1
$

So $h(x)-1=3xh(x)+\frac{1}{1-3x}-1$; $\left(1-3x\right)h(x)=\frac{1}{1-3x}$ And $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 $c_{n}=(n+1)3^{n}$

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

Quote:

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

. . $\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: . $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 $h(x)=\frac{1}{(1-3x)^2}$.

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

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

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

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

We see that $c_n=n 3^{n-1}$ for $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

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

write

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

then use it on the equation

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

so

$\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 $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.