5
$\begingroup$

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.

  • 8
    What is the derivative of a geometric series?2012-02-11

3 Answers 3

10

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

3

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}\;.$

  • 0
    Great explanation - a general way to proceed instead of a single insight about the properties of a particular infinite series!2012-02-11
3

$\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}. $