# Thread: recurrence and generating functions

1. ## recurrence and generating functions

Suppose $a_{n}=2a_{n-1}+3^{n}$ with $a_{0}=6$.

Then,

$G(x)=\sum_{0}^{\infty}a_{n}x^{n}$

$=a_{0}+\sum_{1}^{\infty}a_{n}x^{n}$

$=6+\sum_{1}^{\infty}(2a_{n-1}+3^{n})x^{n}$

$=6+\sum_{1}^{\infty}2a_{n-1}x^{n}+\sum_{1}^{\infty}3^{n}x^{n}$

$=6+2x\sum_{1}^{\infty}a_{n-1}x^{n-1}+\frac{1}{1-3x}$

$=6+2xG(x)+\frac{1}{1-3x}$.

So,

$G(x)-2xG(x)=6+\frac{1}{1-3x}$

$G(x)=\frac{7-18x}{(1-3x)(1-2x)}$

Solving for $A,B$ in

$G(x)=\frac{7-18x}{(1-3x)(1-2x)}=\frac{A}{1-3x}+\frac{B}{1-2x}$

we obtain

$A=\lim_{x\rightarrow\frac{1}{3}}=(1-3x)G(x)=3$

and

$B=\lim_{x\rightarrow\frac{1}{2}}=(1-2x)G(x)=4$

Thus,

$G(x)=\frac{3}{1-3x}+\frac{4}{1-2x}=3\sum_{0}^{\infty}3^{n}x^{n}+4\sum_{0}^{\infty }2^{n}x^{n}$.

So, the general formula for the recurrence is given by

$a_{n}=(3)3^{n}+(4)2^{n}$.

According to my exam, the correct answer is $a_{n}=(3)3^{n}+(3)2^{n}$, which I get when I use the method of undetermined coefficients. However, I am not seeing my mistake when I use the method above.

Also, lets say I have a recurrence relation starting with intitial contition $a_{1}$. Do I just start the infinite series at one and move on like any other problem (i.e., $G(x)=\sum_{1}^{\infty}a_{n}x^{n}$)? Finally, under what conditions does this method for solving recurrence relations fail?

2. Originally Posted by Danneedshelp
Suppose $a_{n}=2a_{n-1}+3^{n}$ with $a_{0}=6$.

Then,

$G(x)=\sum_{0}^{\infty}a_{n}x^{n}$

$=a_{0}+\sum_{1}^{\infty}a_{n}x^{n}$

$=6+\sum_{1}^{\infty}(2a_{n-1}+3^{n})x^{n}$

$=6+\sum_{1}^{\infty}2a_{n-1}x^{n}+\sum_{1}^{\infty}3^{n}x^{n}$

$=6+2x\sum_{1}^{\infty}a_{n-1}x^{n-1}+\frac{1}{1-3x}$ See below

$=6+2xG(x)+\frac{1}{1-3x}$.

So,

$G(x)-2xG(x)=6+\frac{1}{1-3x}$

$G(x)=\frac{7-18x}{(1-3x)(1-2x)}$

Solving for $A,B$ in

$G(x)=\frac{7-18x}{(1-3x)(1-2x)}=\frac{A}{1-3x}+\frac{B}{1-2x}$

we obtain

$A=\lim_{x\rightarrow\frac{1}{3}}=(1-3x)G(x)=3$

and

$B=\lim_{x\rightarrow\frac{1}{2}}=(1-2x)G(x)=4$

Thus,

$G(x)=\frac{3}{1-3x}+\frac{4}{1-2x}=3\sum_{0}^{\infty}3^{n}x^{n}+4\sum_{0}^{\infty }2^{n}x^{n}$.

So, the general formula for the recurrence is given by

$a_{n}=(3)3^{n}+(4)2^{n}$.

According to my exam, the correct answer is $a_{n}=(3)3^{n}+(3)2^{n}$, which I get when I use the method of undetermined coefficients. However, I am not seeing my mistake when I use the method above.

Also, lets say I have a recurrence relation starting with intitial contition $a_{1}$. Do I just start the infinite series at one and move on like any other problem (i.e., $G(x)=\sum_{1}^{\infty}a_{n}x^{n}$)? Finally, under what conditions does this method for solving recurrence relations fail?
$\sum_{1}^{\infty}3^{n}x^{n} = \frac{1}{1-3x}-1$