5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ After finishing your calculations, you can compare your result with OEIS A109613. $\endgroup$ – dtldarek Mar 15 '13 at 9:20
  • $\begingroup$ $1+2x^2 + 2x^4 + \dots = \frac{2}{1-x^2} - 1 = \frac{1+x^2}{1-x^2}$. $\endgroup$ – Siméon Mar 15 '13 at 9:52
  • 3
    $\begingroup$ @MhenniBenghorbal Why did you add braces (which denote sets) around the sequences? $\endgroup$ – Lord_Farin Jun 26 '13 at 6:51
  • $\begingroup$ @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... $\endgroup$ – Tobias Kienzler Jul 2 '13 at 14:22
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$$ $\endgroup$ – Tobias Kienzler Mar 15 '13 at 9:58
  • $\begingroup$ 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)}$$ $\endgroup$ – notamathwiz Mar 15 '13 at 10:08
  • $\begingroup$ 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}$ $\endgroup$ – Tobias Kienzler Mar 15 '13 at 10:36
  • $\begingroup$ @notamathwiz Don't forget to accept answers if they helped you (click on the checkmark) $\endgroup$ – Tobias Kienzler Mar 15 '13 at 11:56
  • $\begingroup$ 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 $\endgroup$ – notamathwiz Mar 16 '13 at 23:50
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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