# Alternating sign odd number generating function.

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

$$\{1,1,-1,3,-3,5,-5,7,-7,9,-9,11,-11,\}$$

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?

• 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. – Ben Sheller Mar 29 '16 at 18:27
• 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. – Iceman Mar 29 '16 at 18:34
• Oh you mean the other sum...the one i was looking for... – Iceman Mar 29 '16 at 18:41
• So I got $\frac{1+2x-x^2}{(x+1)^2(x-1)}$. How can I extract the coefficients? – 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

$$A(x)=\frac{1/2}{1-x}+\frac{3/2}{1+x}-\frac1{(1+x)^2}\;.$$

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*}

so

$$a_n=\frac12+\frac{3(-1)^n}2-(-1)^n(n+1)=\frac{1+(-1)^n}2+(-1)^{n+1}n\;.$$

• 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... – Iceman Mar 29 '16 at 19:07
• @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. – Brian M. Scott Mar 29 '16 at 19:09
• perfect. I also obtained this from you as well... no silly mistakes. – Iceman Mar 29 '16 at 19:53
• @Iceman: Great! Always nice to get confirmation. – Brian M. Scott Mar 29 '16 at 19:54