0
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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)}\ .$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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*}

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.