Generating function for $a_n= a_{n-1}+2a_{n-2}$+3 How do I find a generating function for $a_n= a_{n-1}+2a_{n-2}$+3 using sigma notation? with initial conditions $a_0$ =2 and $a_1$ = 2.
I'm mainly confused by how to deal with the "+3" at the end. Thanks!
What I've done so far is:
$\sum\limits_{n=0}^\infty a_n x^n = 2 + 2x+ \sum\limits_{n=2}^\infty (a_{n-1}+2a_{n-2} +3)x^n $
$\sum\limits_{n=2}^\infty (a_{n-1}+2a_{n-2} +3)x^n $ = $x\sum\limits_{n=1}^\infty a_{n-1}x^n$ +$2x^2 \sum\limits_{n=0}^\infty a_{n-2} x^n $ + $\frac{3}{(1-x)}$ 
 A: Let $f(z) = \sum\limits_{n=0}^\infty a_n z^n$. Multiply the defining recurrence relation
$$a_n = a_{n-1} + 2 a_{n-2} + 3,\quad n \ge 2$$
by $z^n$ and start summing from $n = 2$, you get
$$
\underbrace{f(z) - \overbrace{(2 + 2 z)}^{a_0 + a_1 z}}_{
\sum\limits_{n=2}^\infty a_n z^n = f(z) - a_0 - a_1 z}
= 
\underbrace{z(f(z)-\overbrace{2}^{a_0})}_{
\sum\limits_{n=2}^\infty a_{n-1}z^n = z\sum\limits_{n=1}^\infty a_n z^n}
+
\underbrace{2z^2 f(z)}_{2\sum\limits_{n=2}^\infty a_{n-2}z^n = 2z^2\sum\limits_{n=0}^\infty a_n z^n}
+ \overbrace{\frac{3z^2}{1-z}}^{3\sum\limits_{n=2}^\infty z^n}$$
Please note that there is no need of special treatment for the extra term $3$.
As long as you know how to compute the sum $\sum_{n=2}^\infty 3 z^n$, you are fine. 
Finally, rearranging above expression gives you
$$f(z) = \frac{2-2z + 3z^2}{(1-z)(1 - z - 2z^2)}$$
and that's it.
A: $a_{n+2}+\frac32=a_{n+1}+\frac32+2(a_n+\frac32)$. Now put: $b_n=a_n+\frac32\,$, then: $b_{n+2}=b_{n+1}+2b_n$
A: My preferred method is that of Graham, Knuth, & Patashnik, Concrete Mathematics. First rewrite the recurrence so that it’s valid for all $n$ if one assumes that $a_n=0$ for all $n<0$. In this case we get
$$a_n=a_{n-1}+2a_{n-2}+3-[n=0]-3[n=1]\;,$$
where the last two terms contain Iverson brackets and are there to get the initial conditions right. Now multiply through by $x^n$ and sum over $n$ to get
$$\sum_na_nx^n=\sum_na_{n-1}x^n+2\sum_na_{n-2}x^n+3\sum_nx^n-\sum_n[n=0]x^n-3\sum_n[n=1]x^n\;.$$
Each Iverson bracket is $0$ except for one value of $n$, so this reduces to
$$\sum_na_nx^n=\sum_na_{n-1}x^n+2\sum_na_{n-2}x^n+3\sum_nx^n-1-3x\;.$$
On the lefthand side you have the generating function, which I’ll call $g(x)$. On the righthand side I’m going to factor out some powers of $x$ to make subscripts match up with exponents:
$$g(x)=x\sum_na_{n-1}x^{n-1}+2x^2\sum_na_{n-2}x^{n-2}+\frac3{1-x}-1-3x\;.$$
Finally, since the sum is over all integers $n$ we can easily shift the index of summation to get
$$g(x)=xg(x)+2x^2g(x)+\frac3{1-x}-1-3x\;.$$
Now solve for $g(x)$.
