# Generating function for the sequence $1,1,3,3,5,5,7,7,9,9,\ldots$

The generating function for the sequence $\left\{1,1,1,1,...\right\}$ is $$1 + x + x^2 + x^3 ... = \frac{1}{1-x}$$ What is the generating function for the sequence $\left\{1,1,3,3,5,5,7,7,9,9,\dots \right\}$?

This is my attempt:

what we want to do is after the initial $\left\{1,1,1,1,...\right\}$ function we want to add two more functions shifted two to the right such as $\left\{0,0,1,1,1,...\right\}$ and keep adding such function 2 at a time and each new two are shifted 2 more to the right then the previous one. so first would be $\left\{1,1,1,1,\dots \right\}$ then add 2 of $\left\{0,0,1,1,1,1,\dots\right\}$ then add 2 more of $\left\{0,0,0,0,1,1,1,1,\dots\right\}$ and keep doing that. this gives us the function

$$\frac{1}{1-x}+\frac{2x^2}{1-x}+\frac{2x^4}{1-x}+...$$ or $$\frac{1}{1-x}+\frac{2x^{2k}}{1-x}$$ however $i$ do not know where to go from here, how do $i$ finish this problem?

• After finishing your calculations, you can compare your result with OEIS A109613. Mar 15, 2013 at 9:20
• $1+2x^2 + 2x^4 + \dots = \frac{2}{1-x^2} - 1 = \frac{1+x^2}{1-x^2}$. Mar 15, 2013 at 9:52
• @MhenniBenghorbal Why did you add braces (which denote sets) around the sequences? Jun 26, 2013 at 6:51
• @MhenniBenghorbal Why did you turn the pronoun I (though notamathwiz spelled it i) into a variable? That's almost philosophical, turning the OP into a replaceable entity... Jul 2, 2013 at 14:22

You already did the difficult part... You probably mean $$\frac1{1-x}+\sum_{k=1}^\infty\frac{2x^{2k}}{1-x}$$

So you just have to evaluate the geometric series $$\sum_{k=1}^\infty (x^2)^k = \frac1{1-x^2} - 1 = \frac{x^2}{1-x^2}$$

And obtain

$$\frac1{1-x} + \frac2{1-x}\sum_{k=1}^\infty x^{2k} = \frac{1+\frac{2x^2}{1-x^2}}{1-x} = \frac{x^2+1}{(1-x)(1-x^2)}$$

• Note this is identical to oeis.org/A109613 's $$\frac{1+x+x^2+x^3}{(1-x^2)^2}$$ if you multiply it by $$\frac{1+x}{1+x}$$ Mar 15, 2013 at 9:58
• first how did you evaluate the sum? and adding $$\frac{1}{1-x}$$ with $$\frac{x^2}{1-x^2}$$ gives me $$\frac{1-x^3}{(1-x)(1-x^2)}$$ not $$\frac{x^2+1}{(1-x)(1-x^2)}$$ Mar 15, 2013 at 10:08
• Sorry, I tend to omit too many steps... The sum is obtained from the geometric series (and subtract one because $k$ starts at 1 instead of 0), and that sum has to be multiplied by $\frac2{1-x}$ before adding it to $\frac1{1-x}$ Mar 15, 2013 at 10:36
• quick question, why is it what when you subtract 1 from the geometric series do you end up with a positive result when i'm getting a negative result Mar 16, 2013 at 23:50
• @notamathwiz $\frac1{1-x^2}-1 = \frac1{1-x^2}-\frac{1-x^2}{1-x^2}=\frac{1-(1-x^2)}{1-x^2}$ - I guess you forgot the double minus Mar 17, 2013 at 11:45

Here is another approach.

The generating function writes $(1+x)(1+3x^2 + 5x^4 + 7x^6 + 9x^8 + \dots)$ where the second term appears as the derivative of $x+x^3 + x^5 + x^7 + x^9 + \dots$

The later being the odd part of $1+x+x^2 + x^3 + x^4 + \dots$, we have: $$x + x^3 + x^5 + x^7 + x^9 + \dots = \frac{1}{2}\left(\frac{1}{1-x}-\frac{1}{1+x}\right)$$

Hence: $$1 + 3x^2 + 5x^4 + 7x^6 + 9x^8 + \dots = \frac{1}{2}\left(\frac{1}{(1-x)^2}+\frac{1}{(1+x)^2}\right)$$

Finnaly: $$\frac{1+x}{2}\left(\frac{1}{(1-x)^2}+\frac{1}{(1+x)^2}\right) = \frac{x^2+1}{(x-1)^2(1+x)}$$

• haha the correct result is actually $$\frac{1+x^2}{(1-x)(1-x^2)}$$ but i dont know how to get it Mar 15, 2013 at 9:43
• @notamathwiz: it is what I found too. Mar 15, 2013 at 9:47