Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer
Note this is identical to '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)} $$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.