Generating function given the recurrence relation

Question

Let the recurrence relation be given by $$a_{n}=2a_{n-1}+3$$ and let $a_0=1$ find the generating function in closed form. $$\text{Attempt}$$ the general equation of the form $a_n=ca_{n-1}+d$ has the solution as $a_n=c^n(a_0+\frac{d}{c-1})-\frac{d}{c-1}$ thus the relation for th above recurrence relation is $a_n=4(2^n)-3$ . However I dont know how to handle that constant 3 hence I cant proceed to get the generating function.Any help would be appreciated!

Answer 1

The generating function is $$F(x) = \sum_{n\ge0}a_nx^n = 1 + x\sum_{n\ge0}(2a_n + 3)x^n = 1 + 2xF(x) + \frac{3x}{1-x}\ .$$ Thus, $$F(x) = \frac{1 + \frac{3x}{1-x}}{1 - 2x} = \frac{1 + 2x}{(1-x)(1-2x)}\ .$$

Answer 2

You can simply split the two terms in $a_n$, and write your generating function as a sum of two other generating functions:

\begin{align*} \sum_{n=0}^\infty (4(2^n)-3)x^n &= \sum_{n=0}^\infty 4(2^n) x^n - 3 \sum_{n=0}^\infty x^n\\ &=4\sum_{n=0}^\infty (2x)^n - 3\sum_{n=0}^\infty x^n\\ &= \frac{4}{1-2x} - \frac{3}{1-x}. \end{align*}