# How to calculate the Nth member of this Generating function?

The series 012012012... matches the following generating function:

$$T=\frac{x+2x^2}{1-x^3}$$

How could i find a closed expression of the nth member of this series?

• Can you tell (1) what you tried and (2) where you are stuck? Jun 10, 2014 at 8:28

For a bloated answer: \begin{align*} T &= \frac{x+2x^2}{1-x^3} \\ &= \frac{1}{1-x}+\frac{\frac{1}{2}-\frac{\sqrt{3}}{6}\, i}{-\frac{1}{2}+\frac{\sqrt3}{2}\, i - x}-\frac{\frac{1}{2}+\frac{\sqrt{3}}{6}\, i}{\frac{1}{2}+\frac{\sqrt3}{2}\, i + x} \end{align*}

Extracting $[x^n]$ now gives: \begin{align*} a_n &= 1+\frac{\displaystyle \frac{1}{2}-\frac{\sqrt{3}}{6}\, i}{\displaystyle \left(-\frac{1}{2}+\frac{\sqrt3}{2}\, i\right)^{n+1}}- (-1)^n \frac{\displaystyle \frac{1}{2}+\frac{\sqrt{3}}{6}\, i}{\displaystyle \left(\frac{1}{2}+\frac{\sqrt3}{2}\, i\right)^{n+1}} \end{align*}

Update

Thanks everyone for the discussion and answers!

Using Qiaochu Yuan's answer and notation, we can get the partial fraction, and in turn, the formula.

For any period $0,1,\ldots, k$, the generating function is:

$$G(x) = \frac{P(x)}{Q(x)}$$

where \begin{align*} P(x) &= \sum_{u=1}^k u\, x^u \\ Q(x) &= 1-x^{k+1} \end{align*}

and the general term is: \begin{align*} a_n &= \sum_{v=0}^k \frac{P\left(\zeta^v\right)}{Q'\left(\zeta^v\right)\, \zeta^{v\, (n+1)}} \end{align*}

where $\zeta=e^{2\pi\, i\, /(k+1)},\;\; i=\sqrt{-1}$

Simplification is looking difficult now!

• Thanks! That's exactly what I've been looking for. Also, how do you generally open f(x)/1-x^r ? or even f(x)/g(x)? Jun 10, 2014 at 11:27
• You are welcome! I understood from your reply to Claude Leibovici. It depends on how easy it is to factor the denominator. If $r<4$, then it's possible get the partial fraction as done here. Otherwise, it will be difficult. I use a computer for the tasks that are straight-forward.
– gar
Jun 10, 2014 at 11:45
• @Ido4848, if it is just $1 - x^r$, the zeros of that one are the $r$-th roots of unity, $\exp(2 \pi k i / r)$ for $0 \le k < r$, or $\cos (2 \pi k / r) + i \sin (2 \pi k / r)$ if you prefer. Jun 11, 2014 at 17:13
• @vonbrand well, that make sense... thanks Jun 12, 2014 at 7:14
• @vonbrand : Thanks for the suggestion, I started looking up after that and found an answer!
– gar
Jun 12, 2014 at 10:57

@Ido4848

Inspired by the way my old TI-92 would represent periodic sequences and Claude's answer we can get

$$A_n=1-\left(\frac{\sin (\frac{2 \pi n}{3})}{\sqrt{3}}+ \cos \left (\frac{2 \pi n}{3} \right )\right)$$

for the nth term.

• Very good idea, indeed. Cheers :) Jun 11, 2014 at 4:09
• That's awesome! How could you make it general(i.e. for 012...k012...k012...k...)? And what's the proof? Thanks! Jun 12, 2014 at 7:13
• Nice answer, never knew a calculator could do such a thing! @Ido4848 : I updated my answer.
– gar
Jun 12, 2014 at 11:03
• @Ido4848 could be generalized (maybe) but I voted on Claude's form. I guess that is a tacit downvote on this one. Jun 12, 2014 at 16:43
• @Ido4848 that's a different question... Jun 16, 2014 at 9:27

$$T=\frac{x+2x^2}{1-x^3} = (x+2x^2)\sum_{n=0}^{\infty} x^{3n} = \sum_{n=0}^{\infty}x^{3n+1}+2x^{3n+2}$$

So, coefficients of powers that are multiples of 3 =0
coefficients of powers that are one more than multiples of 3 = 1
coefficients of powers that are two more than multiples of 3 = 2


In what you wrote, you could see that $$a_n=n-3 \left\lfloor \frac{n}{3}\right\rfloor$$

• Yes. But I've tried to find a closed form as: Tn=a*(b^n)+c*(d^n)+...y*(z^n). or any other thing without the round down operator. Jun 10, 2014 at 8:48
• In order to be able to repeat the sequence $0120120123...$, it seems clear (at least to me !) that a rounding function is involved. Jun 10, 2014 at 9:02
• @Claude Leibovici or maybe a mod or trigonometric form. Jun 10, 2014 at 22:39