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!
Generating function given the recurrence relation
generating-functionsrecurrence-relations
Related Solutions
You've used the denominator of $\frac{1+x}{1-x^2-2x^3}$ to get the recurrence: the numerator gives the initial terms. If we generalise slightly so that you can see the derivation, $$\frac{b+cx+dx^\alpha}{1-x^2-2x^3}$$ gives recurrence $$a_n=a_{n-2} + 2a_{n-3} + b[n = 0] + c[n = 1] + d[n = \alpha]$$ where $[\cdot]$ is an Iverson bracket and evaluates to $1$ when the condition inside is true and $0$ when it is false. So in your case ($b=c=1, d=0$) we have $$\begin{eqnarray}a_0 &=& a_{-2} &+& 2a_{-3} + b &=& b &=& 1 \\ a_1 &=& a_{-1} &+& 2a_{-2} + c &=& c &=& 1 \\ a_2 &=& a_{0} &+& 2a_{-1} &=& a_0 &=& 1 \end{eqnarray}$$
Why?
"$\phi_S(x)$ is the generating function for $a_i$" is another way of saying $$\phi_S(x) = \sum_{n} a_n x^n$$
If we substitute that into the given rational function, $$\sum_{n} a_n x^n = \frac{1+x}{1-x^2-2x^3}$$ we can rearrange to $$(1-x^2-2x^3)\sum_{n} a_n x^n = 1+x$$ and then to $$\sum_{n} a_n x^n = 1+x + \sum_{i} (a_i x^{i+2} + 2a_i x^{i+3})$$ Then if we apply the coefficient extraction operator $[x^n]$ to both sides, using its linearity, we get $$a_n = [x^n]1 + [x^n]x + \sum_{i} ([x^n]a_i x^{i+2} + [x^n] 2a_i x^{i+3}) \\ = [n=0] + [n=1] + \sum_{i} (a_i [n=i+2] + 2a_i [n=i+3]) \\ = [n=0] + [n=1] + a_{n-2} + 2a_{n-3}$$
You have more or less the right idea, but the right hand side is the sequence $(4n)$, not $(4)$. We have, \begin{align*} \sum_{n=0}^\infty 4n x^n &= \sum_{n=0}^\infty 4(n + 1)x^n - \sum_{n=0}^\infty 4x^n \\ &= \frac{\mathrm{d}}{\mathrm{d}x}\sum_{n=0}^\infty 4x^{n+1} - \sum_{n=0}^\infty 4x^n \\ &= \frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{4}{1 - x} - 4\right) - \frac{4}{1 - x} \\ &= \frac{4}{(1 - x)^2} - \frac{4}{1 - x} \\ &= \frac{4x}{(1 - x)^2}. \end{align*}
As you noted, we have \begin{align*} A(x) - xA(x) - 2x^2A(x) &= a_0 + (a_1 - a_0)x + (a_2 - a_1 - 2a_0)x^2 + (a_3 - a_2 - 2a_1)x^3 + \ldots \\ &= a_0 + (a_1 - a_0)x + (4 \cdot 2)x^2 + (4 \cdot 3)x^3 + \ldots + 4n x^n + \ldots \\ &= \frac{4x}{(1 - x)^2} + a_0 + (a_1 - a_0)x - 4x \\ &= \frac{4x}{(1 - x)^2} - 4 + (-5 + 4)x - 4x \\ &= \frac{4x}{(1 - x)^2} - 4 - 5x \\ &= \frac{4x - (4 + 5x)(1 - x)^2}{(1 - x)^2} \\ &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2} \\ A(x) &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2(1 - x - 2x^2)} \\ &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2(1 - 2x)(1 + x)}. \end{align*} Before we apply partial fractions, it's worth testing if this fraction can be simplified at all. Plugging in $x = -1$ produces $0$, meaning that $1 + x$ divides it. Dividing out $1 + x$ from the numerator and denominator, $$A(x) = \frac{-5x^2 + 11x - 4}{(1 - x)^2(1 - 2x)}$$
Now we apply partial fractions. We wish to find $a, b, c$ such that $$A(x) = \frac{a}{1 - x} + \frac{b}{(1 - x)^2} + \frac{c}{1 - 2x},$$ or equivalently, $$-5x^2 + 11x - 4 = a(1 - x)(1 - 2x) + b(1 - 2x) + c(1 - x)^2.$$ Considering $x = 1$, $$-5 \cdot 1^2 + 11 \cdot 1 - 4 = b \cdot (-1) \implies b = -2.$$ Considering $x = \frac{1}{2}$, $$-5 \cdot \left(\frac{1}{2}\right)^2 + 11 \cdot \frac{1}{2} - 4 = c \cdot \left( \frac{1}{2}\right)^2 \cdot \implies c = 1.$$ Now, using these values of $b$ and $c$, we can find $a$ by substituting a different value for $x$, e.g. $x = 0$: $$-4 = a + (-2) \cdot 1 + 1 \cdot 1^2 \implies a = -3.$$ That is, $$A(x) = \frac{-3}{1 - x} + \frac{-2}{(1 - x)^2} + \frac{1}{1 - 2x}.$$ We finally convert these generating functions back to sequences: $$a_n = -3 + (-2)(n + 1) + 2^n = -5 + 2n + 2^n,$$ as required.
Best Answer
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)}\ .$$