Generating function for $a_n= a_{n-1}+2a_{n-2}$+3

Question

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

Answer 1

$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$

Answer 2

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

Answer 3

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.