I'm trying to multiply 2 generating functions ( (1/(1-x) ) and ( 1/(1-x^5) ) which have different denominations so that I can find the coefficient. When browsing math.stackexchange I found the equation:

\begin{align*} \frac{1}{1-x}\cdot\frac{1}{1-x^r}=\sum_{n\ge 0} \left(1+\left\lfloor\frac{n}{r}\right\rfloor\right)x^n \end{align*}

Could someone go through all of the steps of the equation and explain how and why the product of these two power series are equivalent to the summation shown on the right?


We obtain \begin{align*} \color{blue}{\frac{1}{1-x}\cdot\frac{1}{1-x^r}} &=\sum_{k=0}^\infty x^k\sum_{l=0}^\infty \left(x^r\right)^l\tag{1}\\ &=\sum_{k=0}^\infty x^k\sum_{l=0}^\infty x^{rl}\\ &=\sum_{n=0}^\infty \left(\sum_{{k+rl=n}\atop {k,l\geq 0}} 1\right) x^n\tag{2}\\ &=\sum_{n=0}^\infty \left(\sum_{k=0}^{\left\lfloor\frac{n}{r}\right\rfloor} 1\right)x^n\tag{3}\\ &\,\,\color{blue}{=\sum_{n=0}^\infty \left(1+\left\lfloor\frac{n}{r}\right\rfloor\right)x^n}\tag{4} \end{align*} and the claim follows.


  • In (1) we apply the geometric series expansion twice.

  • In (2) we multiply out using the Cauchy-product.

  • In (3) we eliminate the index $l$. Due to the factor $r$ and the relation $k=n-r\cdot l$ the upper limit of $k$ is set to $\left\lfloor\frac{n}{r}\right\rfloor$.

  • In (4) we simplify the inner sum noting that since we start with $k=0$ we have the additional term $1$.


\begin{align*} \frac{1}{1-x} \frac{1}{1-x^r} &= (1+x+x^2+\cdots)(1+x^r+x^{2r}+\cdots) \\ &= 1+x+x^2+\cdots \\ &+ x^r+x^{r+1}+x^{r+2}+\cdots \\ &+ x^{2r} + x^{2r+1} + x^{2r+2} + \cdots \\ &+ \cdots \end{align*} Every exponent from $x^0, \ldots, x^{r-1}$ is included once, every exponent from $x^r, \ldots, x^{2r-1}$ is included twice, etc. So the coefficient of $x^n$ is $1 + \lfloor n/r\rfloor$.

  • $\begingroup$ Thank you @Joshua P. Swanson for your response! I'm still quite confused about how the coefficient of x^n is 1 + (n/r) because say if the r-value is 5 and I'm finding the coefficient of an n-degree is not a multiple of 5 (eg. n = 14), wouldn't the coefficient not tabulate? I would get a fraction although the answer is supposed to be 3. I can only see how the coefficient of x^n being 1 + (n/r) works when the n value is a multiple of r. $\endgroup$
    – boop
    Jul 3 '21 at 7:10
  • $\begingroup$ You're ignoring the floor symbols. They tell you to just ignore the fractional part and truncate at the nearest lower integer. $\endgroup$ Jul 3 '21 at 17:22

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.