In class today, we had to find a closed generating function for $A_n=2n+1$. The sequence of the odd natural numbers. Anyone with an idea?

In class today, we had to find a closed generating function for $A_n=2n+1$, where $n\in \mathbb{N}$ and $A_n$ is the sequence of odd natural numbers. Anyone with an idea? I tried several thing but could not get it.

-
What is the derivative of a geometric series? – deinst Feb 11 '12 at 17:19

Consider $\displaystyle f(x)= x+x^3+x^5+x^7+\cdots= \frac x{1-x^2}$
Then $f'(x)=1+3x^2+5x^4+\cdots$ and : $$\left(\frac {x}{1-x^2}\right)'=\frac{2x^2}{(x^2-1)^2}-\frac{1}{x^2-1}=1+3x^2+5x^4+\cdots$$ and your generating function is : $$1+3t^1+5t^2+\cdots= \frac{2t}{(t-1)^2}-\frac{1}{t-1}=\frac{t+1}{(t-1)^2}$$

-

An alternative approach is to write down a recurrence for the sequence and produce the generating function from the recurrence. Clearly the recurrence here is $A_n=A_{n-1}+2$, with initial condition $A_0=1$. If we assume that $A_n=0$ for all integers $n<0$, we can use the Iverson bracket to do away with the initial condition and write the recurrence simply as $$A_n=A_{n-1}+2-[n=0]\;.$$ Now multiply both sides by $x^n$ and sum over $n$ to get the generating function $f$:

\begin{align*}f(x)=\sum_nA_nx^n&=\sum_n\left(A_{n-1}x^n+2x^n-[n=0]x^n\right)\\ &=\sum_nA_{n-1}x^n+2\sum_nx^n-\sum_n[n=0]x^n\\ &=x\sum_nA_{n-1}x^{n-1}+\frac2{1-x}-1\\ &=x\sum_nA_nx^n+\frac2{1-x}-1\\ &=xf(x)+\frac{1+x}{1-x}\;, \end{align*}

so $$(1-x)f(x)=\frac{1+x}{1-x}\;,$$ and $$f(x)=\frac{1+x}{(1-x)^2}\;.$$

-
Great explanation - a general way to proceed instead of a single insight about the properties of a particular infinite series! – Rex Kerr Feb 11 '12 at 22:36

$$\sum_{n=0}^\infty (2n+1)x^n=\sum_{n=0}^\infty\big( 2(n+1)-1\big) x^n =2\left(\sum_{n=0}^\infty \frac{d}{dx}x^{n+1}\right)-\left(\sum_{n=0}^\infty x^n\right)$$

$$=2\frac{d}{dx}\left(\frac{1}{1-x}-1\right)-\frac{1}{1-x}=\frac{2}{(1-x)^2}-\frac{1}{1-x}=\frac{1+x}{(1-x)^2}.$$

-