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?
Best Answer
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\;.$$