How to find the generating function of a recurrent series: $b_{0} = 4$, $b_{n}=3b_{n-1}-2^{n-1}$ The series is defined as such:
$$
b_{0}=4
$$$$
b_{n}=3b_{n-1}-2^{n-1}\text{ for }n\geq1
$$
How do I go about finding its generating function?
I started like this:
$$
f(x)=\sum_{n=0}^{\infty} b_{n} \cdot x^n =4+\sum_{n=1}^{\infty}(3b_{n-1}-2^{n-1})\cdot x^n
$$
And now I am lost. How should I proceed?
 A: hint
$$b_n=3b_{n-1}-2^{n-1}\implies$$
$$b_n=3b_{n-1}-3.2^{n-1}+2.2^{n-1}\implies$$
$$b_n-2^n=3(b_{n-1}-2^{n-1})$$
So, with
$$c_n=b_n-2^n$$
you have
$$c_n=3.c_{n-1}$$
and
$$c_n=c_0.3^n\;\; where\;\;c_0=4-1=3$$
You can finish.
A: $$f(x)=4+3x\sum_{n=1}^\infty b_{n-1} x^{n-1} - x \sum_{n=1}^\infty (2x)^{n-1}\\
= 4+3xf(x)-\frac{x}{1-2x}$$
Can you start from here?
A: You are almost there! Keep in your mind that you should always look for two things when manipulating generating functions:

*

*Expressions like $\sum b_k x^k$, with exponent and index equal; beside the first terms that could not be there, this is your generating functions;

*Known generating functions; for example, keep in your pocket the identity

$$\sum t^j = \frac{1}{1-t}$$
And in general, if the coefficient of your series do not appear, you should be able to algebraically solve this expression independently from the recurrence formula you are transforming.
With this in mind, let's start from your last passage:
$$f(x)=\4+\sum_{n=1}^{\infty}(3b_{n-1}-2^{n-1})\cdot x^n = 4+ \sum_{n=1}^{\infty} 3b_{n-1} x^n - \sum_{n=1}^{\infty} 2^{n-1} x^n $$
The left part seem to be related to $\sum b_k x^k$; indeed, factoring a $3x$ you get
$$ \sum_{n=1}^{\infty} 3b_{n-1} x^n = 3x \sum_{n=1}^{\infty} b_{n-1} x^{n-1} = 3x \sum_{n=0} b_n x^n = 3x f(x) $$
Note the shift in the indices in the last passage, so that we recover the expression for $f(x) $.
The right part does not contain $b_k$; it should be a known expression. It is a slight variant of the identity I presented you above:
$$ \sum_{n=1}^{\infty} 2^{n-1} x^n = x \sum_{n=1}^{\infty} 2^{n-1} x^{n-1} = x \sum_{n=1}^{\infty} (2x) ^{n-1} = x\sum_{n=0}^{\infty} (2x) ^n = \frac{x}{1-2x} $$
Putting all together we have
$$ f(x) = 4+3x f(x) - \frac{x}{1-2x} = 3x f(x) + \frac{4-9x}{1-2x} $$
Solving for $f(x) $ we have
$$ f(x) =\frac{4-9x}{ (1-2x) (1-3x) }  $$
