Thread: recurrence and generating functions

1. recurrence and generating functions

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

Then,

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

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

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

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

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

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

So,

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

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

Solving for $\displaystyle A,B$ in

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

we obtain

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

and

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

Thus,

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

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

According to my exam, the correct answer is $\displaystyle 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 $\displaystyle a_{1}$. Do I just start the infinite series at one and move on like any other problem (i.e., $\displaystyle 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 $\displaystyle a_{n}=2a_{n-1}+3^{n}$ with $\displaystyle a_{0}=6$.

Then,

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

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

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

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

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

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

So,

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

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

Solving for $\displaystyle A,B$ in

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

we obtain

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

and

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

Thus,

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

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

According to my exam, the correct answer is $\displaystyle 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 $\displaystyle a_{1}$. Do I just start the infinite series at one and move on like any other problem (i.e., $\displaystyle G(x)=\sum_{1}^{\infty}a_{n}x^{n}$)? Finally, under what conditions does this method for solving recurrence relations fail?
$\displaystyle \sum_{1}^{\infty}3^{n}x^{n} = \frac{1}{1-3x}-1$