1
$\begingroup$

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

2 Answers 2

2

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.

  • 0
    @K24: You’re welcome. Yes, this is a step beyond the basic problems. (Your description of the function was perfectly adequate; I just thought that it would be easier to read if I polished it up a bit.)2012-10-22
0

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.

  • 0
    Usually the generating function is written with $a_n$ as coefficient of $x_n$. I did say that in my answer. If one wants the term $a_n+a_{n+1}$ I think there's a simple thing to do to the answer I gave which adds adjacent coefficients... Sorry for the "misreading". I checked that the (now adjusted, after some typos" version gives 3,5,8,12,16,... for the actual numbers in the sequence, as coefficients of powers of $x$.2012-10-22