# 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. – dtldarek Mar 15 '13 at 9:20
$1+2x^2 + 2x^4 + \dots = \frac{2}{1-x^2} - 1 = \frac{1+x^2}{1-x^2}$. – Siméon Mar 15 '13 at 9:52
@MhenniBenghorbal Why did you add braces (which denote sets) around the sequences? – Lord_Farin Jun 26 '13 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... – Tobias Kienzler Jul 2 '13 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}$$ – Tobias Kienzler Mar 15 '13 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)}$$ – notamathwiz Mar 15 '13 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}$ – Tobias Kienzler Mar 15 '13 at 10:36
@notamathwiz Don't forget to accept answers if they helped you (click on the checkmark) – Tobias Kienzler Mar 15 '13 at 11:56
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 – notamathwiz Mar 16 '13 at 23:50

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 – notamathwiz Mar 15 '13 at 9:43
@notamathwiz: it is what I found too. – Siméon Mar 15 '13 at 9:47