I have a sequence that I'm trying to find both an ordinary generating function for as well as a closed form without a floor function. The sequence


is recursively generated by the formula

$$a_0=1$$ $$a_n=a_{n-1}+(-1)^{n-1}2(n-1)$$

So let $A(x)=\sum{a_nx^n}$. Then

$$A(x)=\sum_{n=0}^\infty{a_nx^n}=a_0+\sum_{n=1}^\infty[a_{n-1}+(-1)^{n-1}\cdot 2(n-1)]x^n$$

$$=1+\sum_{n=1}^\infty a_{n-1}x^n+2\sum_{n=1}^\infty{(-1)^{n-1}nx^n}+2\sum_{n=1}^\infty{(-1)^{n}x^n}$$ $$A(x)-1=xA(x)+\frac{2}{1+x}+2\sum_{n=1}^\infty{(-1)^{n-1}nx^n}$$

However, I'm stuck on the third summand. I know that $\sum{nx^n}=x/(1-x)^2$ but I have the alternating sign there which is throwing me off... Any suggestions?

  • $\begingroup$ You need to pull out the $a_0$ term in the summation before you use the recursion relation: currently you are missing a $+1$ on the right-hand side from the second equals sign onward. $\endgroup$ – Ben Sheller Mar 29 '16 at 18:27
  • $\begingroup$ Yes, I will fix that, but the sum of $nx^n$ is $x/(1-x)^2$ according to the proof I did and according to the solution to the problem in Wilf's "Generatingfunctionology". it is chapter 1 a and the answers are in the back. $\endgroup$ – Iceman Mar 29 '16 at 18:34
  • $\begingroup$ Oh you mean the other sum...the one i was looking for... $\endgroup$ – Iceman Mar 29 '16 at 18:41
  • $\begingroup$ So I got $\frac{1+2x-x^2}{(x+1)^2(x-1)}$. How can I extract the coefficients? $\endgroup$ – Iceman Mar 29 '16 at 19:05

You’ve a small error in evaluating the geometric summation:

$$2\sum_{n\ge 1}(-1)^nx^n=\frac{-2x}{1+x}\;,$$

not $\frac2{1+x}$, because the summation starts at $n=1$, not at $n=0$. The other summation is

$$2\sum_{n\ge 1}(-1)^{n-1}nx^n=-2\sum_{n\ge 1}n(-x)^n=\frac{-2(-x)}{\big(1-(-x)\big)^2}=\frac{2x}{(1+x)^2}\;,$$

as noted by AccidentalFourierTransform in the comments. Thus, you have

$$\begin{align*} A(x)&=\frac1{1-x}\left(1-\frac{2x}{1+x}+\frac{2x}{(1+x)^2}\right)\\ &=\frac{(1+x)^2-2x(1+x)+2x}{(1-x)(1+x)^2}\\ &=\frac{1+2x-x^2}{(1-x)(1+x)^2}\;. \end{align*}$$

Just for fun, I checked this by finding $A(x)$ in a completely different way that you might find instructive. Let

$$\begin{align*} f(x)&=\sum_{n\ge 0}(2n+1)x^{2n+1}\\ &=\sum_{n\ge 0}nx^n-\sum_{n\ge 0}2nx^{2n}\\ &=\frac{x}{(1-x)^2}-\frac{2x^2}{(1-x^2)^2}\;. \end{align*}$$

It’s not hard to see that $A(x)=1+f(x)-xf(x)=1+(1-x)f(x)$: $-xf(x)$ yields the $x^{2n}$ terms for $n>0$. Thus,

$$\begin{align*} A(x)&=1+(1-x)f(x)\\ &=1+\frac{x}{1-x}-\frac{2x^2}{(1-x)(1+x)^2}\\ &=\frac{1+2x-x^2}{(1-x)(1+x)^2}\;. \end{align*}$$

Added: To complete the task of finding a closed form for the numbers $a_n$, decompose $A(x)$ into partial fractions. If I’ve made no silly mistakes, it’s


Now write each term on the right as a summation:

$$\begin{align*} A(x)&=\frac{1/2}{1-x}+\frac{3/2}{1+x}-\frac1{(1+x)^2}\\ &=\frac12\sum_{n\ge 0}x^n+\frac32\sum_{n\ge 0}(-x)^n-\sum_{n\ge 0}(n+1)(-x)^n\\ &=\frac12\sum_{n\ge 0}x^n+\frac32\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}(-1)^n(n+1)x^n\\ &=\sum_{n\ge 0}\left(\frac12+\frac{3(-1)^n}2-(-1)^n(n+1)\right)x^n\;, \end{align*}$$



  • $\begingroup$ NIce. I just got the generating function right before as I mentioned in my comments. Now, this is the part that is getting me...how do I find a formula for the coefficients? I'm looking for something without floor function... $\endgroup$ – Iceman Mar 29 '16 at 19:07
  • 1
    $\begingroup$ @Iceman: The first step is to decompose it into partial fractions. Then you reverse engineer each partial fraction to express it as a series and read off and combine the coefficients. $\endgroup$ – Brian M. Scott Mar 29 '16 at 19:09
  • $\begingroup$ perfect. I also obtained this from you as well... no silly mistakes. $\endgroup$ – Iceman Mar 29 '16 at 19:53
  • $\begingroup$ @Iceman: Great! Always nice to get confirmation. $\endgroup$ – Brian M. Scott Mar 29 '16 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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