Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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


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.

share|cite|improve this answer
@Matt: Gleep! Yes, I certainly do. Thanks! – Brian M. Scott Oct 22 '12 at 16:18
You should have read the question better. $P(x) = \sum (a_n+a_{n+1})x^n$, not $\sum a_nx^n$. – Lord_Farin Oct 22 '12 at 16:21
@Lord_Farin: I read it fine: I just forgot what I was doing part way through! I’m fixing it now. – Brian M. Scott Oct 22 '12 at 16:23
@BrianM.Scott Looks good now; sorry for the rather impolite pointer. – Lord_Farin Oct 22 '12 at 16:43
@Lord_Farin: That’s okay; I’m just glad that someone caught it. (I should know better than to resume an answer after an interruption without checking the question again.) – Brian M. Scott Oct 22 '12 at 16:48

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.

share|cite|improve this answer
You should have read the question better. $P(x) = \sum (a_n+a_{n+1})x^n$, not $\sum a_nx^n$. – Lord_Farin Oct 22 '12 at 16:21
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$. – coffeemath Oct 22 '12 at 16:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.