showing a genereral function from a generating function and recursive function

Question

I have an assignment problem that i have been fighting with for a while now..

I have this recursive function:

$$a_n=\begin{cases} 3,&\text{if }n=0\\ 5,&\text{if }n=1\\ 4a_{n-1}-4a_{n-2},&\text{if }n\ge 2\;. \end{cases}$$

We define the generating function $$P(n)=\sum_{n=0}^\infty (a_n+a_{n+1})x^n$$

Now I need to use the definition of $a_n$ in the recursive function to show that $$P(n)=\frac{8-19x}{(1-2x)^2}$$

I cant really get to this result, and I have been trying all sorts of things by now, nothing really leading me anywhere..

I hope some of you can help me! Thanks

Answer 1

Multiply the recurrence $a_n=4a_{n-1}-4a_{n-2}$ by $x^n$ and sum over $n\ge 2$ to get

$$\begin{align*} \sum_{n\ge 2}a_nx^n&=\sum_{n\ge 2}\left(4a_{n-1}x^n-4a_{n-2}x^n\right)\\ &=4x\sum_{n\ge 2}a_{n-1}x^{n-1}-4x^2\sum_{n\ge 2}a_{n-2}x^{n-2}\\ &=4x\sum_{n\ge 1}a_nx^n-4x^2\sum_{n\ge 0}a_nx^n\;. \end{align*}$$

Thus, if $g(x)=\sum_{n\ge 0}a_nx^n$, we have $g(x)-a_1x-a_0=4x\big(g(x)-a_0\big)-4x^2g(x)$, or, filling in the known values of $a_0$ and $a_1$,

$$g(x)-5x-3=4x\big(g(x)-3\big)-4x^2g(x)\;,$$

or finally $$g(x)=\frac{3-7x}{(1-2x)^2}\;.$$

Now you want

$$\begin{align*} P(x)&=\sum_{n\ge 0}(a_n+a_{n+1})x^n\\ &=\sum_{n\ge 0}a_nx^n+\sum_{n\ge 0}a_{n+1}x^n\\ &=g(x)+\frac1x\sum_{n\ge 0}a_{n+1}x^{n+1}\\ &=g(x)+\frac1x\sum_{n\ge 1}a_nx^n\\ &=g(x)+\frac1x\left(g(x)-a_0\right)\\ &=g(x)+\frac1x\left(g(x)-3\right)\\ &=\frac{(1+x)(3-7x)}{x(1-2x)^2}-\frac3x\\ &=\frac{3-4x-7x^2-3(1-2x)^2}{x(1-2x)^2}\\ &=\frac{8x-19x^2}{x(1-2x)^2}\\ &=\frac{8-19x}{(1-2x)^2}\;, \end{align*}$$

as desired.

Answer 2

I think you want your generating function to be a function of $x$. You are summing over $n$, so that index won't be in the function. And usually the generating function is defined as the sum of terms $a_nx^n$, rather than some other coefficient.

Then for your case you know the coeffients of $x^0$ and $x^1$ are 3,5 respectively. And for larger powers your recursion implies that $P(x)-4xP(x)+4x^2P(x)$ should give zero for those powers. So it looks like $P(x)-4xP(x)-4x^2P(x)=3-7x$, [the $-7$ comes from $5-4*3$ when taking the coefficient of $x$ in $P(x)-4xP(x)-4x^2P(x)$] giving the generating function as $(3-7x)/(1-4x+4x^2)$. Hope it's right, but I think this is the basic method...

Anyway I checked the power series on maple and it starts out with the right coefficient series $3,5,8,12,16...$.

I believe one can just multiply my generating function by $1+x$ to get one where the coefficients are the sums of adjacent terms $a_n+a_{n+1}$, but haven't checked that.