Determine the generating function $f(x)$, of the recurrence relation..

Question

Determine the generating function of the recurrence relation

$a_n=3\cdot2^{n-1}-a_{n-1}$ for $n\geq2 , a_1=0$

So $a_0x+(3\cdot2-a_1)x^2+(3\cdot4-a_2)x^3 \ldots $ and what to do next?

Answer 1

This is a standard exercise.

$$f(x) = \sum \limits_{n = 1}^\infty a_n x^n = a_1x + \sum \limits_{n = 2}^\infty a_n x^n = \sum \limits_{n = 2}^\infty (3 \cdot 2^{n - 1} - a_{n - 1}) x^n\\ = \sum \limits_{n = 2}^\infty 3 \cdot 2^{n - 1} - x\sum \limits_{n = 1}^\infty a_n x^n = \sum \limits_{n = 2}^\infty 3 \cdot 2^{n - 1} - xf(x)$$

You should be able to take it from here.

Answer 2

My preferred method is to modify the recurrence slightly so that it is valid for all $n\ge 0$ on the assumption that $a_n=0$ when $n<0$. In order to make it valid at $n=1$, we need

$$0=a_1=3\cdot2^0-a_0=3-a_0\;,$$

so we want $a_0=3$, and the recurrence can be written

$$a_n=3\cdot2^{n-1}-a_{n-1}+3[n=0]\;,\tag{1}$$

where the last term is an Iverson bracket. Multiply $(1)$ by $x^n$ and sum over $n\ge 0$:

$$\begin{align*} \sum_{n\ge 0}a_nx^n&=\sum_{n\ge 0}3\cdot2^{n-1}x^n-\sum_{n\ge 0}a_{n-1}x^n+3\\ &=\frac32\sum_{n\ge 0}(2x)^n-x\sum_{n\ge 0}a_{n-1}x^{n-1}+3\\ &=\frac32\sum_{n\ge 0}(2x)^n-x\sum_{n\ge 0}a_nx^n+3\;. \end{align*}$$

The generating function is $g(x)=\sum_{n\ge 0}a_nx^n$, so we now have

$$g(x)=\frac32\sum_{n\ge 0}(2x)^n-xg(x)+3\;.\tag{2}$$

You should know a closed form for the summation in $(2)$, and you can then solve $(2)$ for $g(x)$ as a function of $x$.

Answer 3

You want to know $$f(x)=\sum \limits_{n = 1}^\infty a_n x^n$$ You have: $$f(x) = \sum \limits_{n = 1}^\infty a_n x^n = \sum \limits_{n = 2}^\infty (3 . 2^{n - 1} - a_{n - 1}) x^n = \sum \limits_{n = 2}^\infty 3 .2^{n - 1}x^n - x\sum \limits_{n = 1}^\infty a_n x^n = \sum \limits_{n = 2}^\infty 3. 2^{n - 1}x^n - xf(x)$$ So : $$f(x)(1+x)=3\sum \limits_{n = 2}^\infty 2^{n - 1}x^n=3x\sum \limits_{n = 1}^\infty 2^{n}x^n=3x\sum \limits_{n = 1}^\infty (2x)^n=3x(\frac{1}{1-2x}-1)$$ Finally : $$f(x)=\frac{3x}{1+x}\frac{2x}{1-2x}=\frac{6x^2}{(1+x)(1-2x)}$$

Answer 4

I'd prefer to consider $b_n=a_{n+1}$, so $b_0=0$ and $$ b_{n+1}=3\cdot2^{n-1}-b_n $$ Also $$ b_{n+2}=3\cdot2^{n+2}-b_{n+1} $$ and, since $3\cdot2^{n+1}=b_{n+1}+b_n$, we get $$ b_{n+2}-b_{n+1}-2b_n=0 $$ with $b_0=0$ and $b_1=6$. If $f(z)=\sum_{n\ge0}b_nz^n$ is the generating functions, we have $$ f(z)-zf(z)-2z^2f(z)-6z=0 $$ or $$ f(z)=\frac{6z}{1-z-2z^2}=\frac{2}{1-2z}-\frac{2}{1+z}= \sum_{n\ge0}(2^{n+1}-2(-1)^n)z^n $$ Your generating function is just the shift by one: $$ \frac{6z^2}{1-z-2z^2} $$