6
$\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$
4
  • 1
    $\begingroup$ After finishing your calculations, you can compare your result with OEIS A109613. $\endgroup$
    – dtldarek
    Mar 15, 2013 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, 2013 at 9:52
  • 3
    $\begingroup$ @MhenniBenghorbal Why did you add braces (which denote sets) around the sequences? $\endgroup$
    – Lord_Farin
    Jun 26, 2013 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$ Jul 2, 2013 at 14:22

2 Answers 2

6
$\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$
5
  • $\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$ Mar 15, 2013 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$ Mar 15, 2013 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$ Mar 15, 2013 at 10:36
  • $\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$ Mar 16, 2013 at 23:50
  • $\begingroup$ @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 $\endgroup$ Mar 17, 2013 at 11:45
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$
2
  • $\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$ Mar 15, 2013 at 9:43
  • 1
    $\begingroup$ @notamathwiz: it is what I found too. $\endgroup$
    – Siméon
    Mar 15, 2013 at 9:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .