It is well known that $\sum_{i=0}^\infty {n+i-1 \choose i}x^i=\frac{1}{(1-x)^n},$ i.e. $\frac{1}{(1-x)^n}$ is generating function for sequence $a_i={n+i-1 \choose i.}$

But I want to find generating function for sequence $a_i={n+im-1 \choose im.}$ Using The On-Line Encyclopedia of Integer Sequences, I understood that generating function for sequence $a_i={n+2i-1 \choose 2i.}$ is $\frac{1+(n-1)x}{(1-x)^2}.$ But I cann't recieve generating function if $m>2.$ I found two formulas for multiset formula. But they didn't help me.

Thanks a lot in advance for any help!


We can simplify our problem: $$ \binom{n+im-1}{im} = (-1)^{im}\binom{-n}{im} $$ We are looking for $$ A_p(x) = \sum\limits_{i=0}^\infty \binom{-n}{im+p}x^i $$ Where $p\in \{ 0, 1, \dots, m-1 \} $ (particularly, $p=0$). We also have: $$ S(x) = \sum\limits_{i=0}^\infty \binom{-n}{i} x^i = \frac{1}{(1+x)^n} $$

Let $\{ z, z^2, \dots, z^m \}$ be different complex solutions to the equation $z^m=1$.

$$ S(z^l \cdot x ) = \sum\limits_{i=0}^\infty \binom{-n}{i} (z^l\cdot x)^i = A_0(x^m) +z^l \cdot xA_1(x^m) + \dots + z^{l(m-1)} \cdot x^{m-1}A_{m-1}(x^m) $$ We created a linear system of equations, where the variables are functions $A_p(x)$. Now we will have, because $z+z^2+\dots+z^m=0$: $$ A_0(x^m) = \frac{1}{m} \sum\limits_{j=1}^m S(z^j \cdot x) = \frac{1}{m} (\frac{1}{(1+zx)^n}+\frac{1}{(1+z^2x)^n}+\dots+\frac{1}{(1+z^nx)^n}) $$ When $m=2$ $$ A_0(x^2) = \frac{1}{2}(\frac{1}{(1+x)^n}+\frac{1}{(1-x)^n}) $$ Derivation for any $p$ is possible, but needs more work with solving the linear equation.


The $m$-th roots of unity $\omega_j=\exp\left(\frac{2\pi ij}{m}\right), 0\leq j<m$ have the nice property to filter elements. For $m,N>0$ we have \begin{align*} \frac{1}{m}\sum_{j=0}^{m-1}\exp\left(\frac{2\pi ij N}{m}\right)= \begin{cases} 1&\qquad m\mid N\\ 0& \qquad otherwise \end{cases} \end{align*}

If $A(x)=\sum_{k=0}^\infty a_kx^k$ then \begin{align*} A(x)+A(\omega_1x)+\cdots+A(\omega_{m-1}x)=\sum_{k=0}^\infty a_{mk}x^{mk}\tag{1} \end{align*}

We set \begin{align*} A_1(x)=\sum_{k=0}^\infty \binom{n+k-1}{k}x^k=\frac{1}{(1-x)^n} \end{align*}

According to (1) we obtain \begin{align*} \color{blue}{A_m(x)}&\color{blue}{=\sum_{k=0}^\infty\binom{n+mk-1}{mk}x^k}\\ &=A_1\left(x^{1/m}\right)+A_1\left(\omega_1 x^{1/m}\right)+\cdots+A_{m-1}\left(\omega_{m-1} x^{1/m}\right)\\ &=\sum_{j=0}^{m-1}A_1\left(\omega_j x^{1/m}\right)\\ &\,\,\color{blue}{=\sum_{j=0}^{m-1}\frac{1}{\left(1-\omega_j x^{1/m}\right)^n}} \end{align*}

Some special cases:

Case $m=2$:

We have $\{\omega_0,\omega_1\}=\{1,e^{\pi i}\}=\{1,-1\}$

\begin{align*} A_2(x)&=\sum_{k=0}^\infty \binom{n+2k-1}{2k}x^k\\ &=\frac{1}{(1-\sqrt{x})^n}+\frac{1}{(1+\sqrt{x})^n} \end{align*}

Case $m=3$:

We have $\{\omega_0,\omega_1,\omega_2\}=\{1,e^{\frac{2\pi i}{3}},e^{\frac{4\pi i}{3}}\}=\{1,\frac{1}{2}(-1+\sqrt{3}),\frac{1}{2}\left(-1-\sqrt{3}\right)\}$

\begin{align*} A_3(x)&=\sum_{k=0}^\infty \binom{n+3k-1}{3k}x^k\\ &=\frac{1}{(1-\sqrt[3]{x})^n}+\frac{1}{(1+\frac{1}{2}(1-\sqrt{3})\sqrt[3]{x})^n}+\frac{1}{(1+\frac{1}{2}(1+\sqrt{3})\sqrt[3]{x})^n} \end{align*}

Case $m=4$:

We have $\{\omega_0,\omega_1,\omega_2,\omega_3\}=\{1,e^{\frac{\pi i}{2}},e^{\pi i},e^{\frac{3\pi i}{2}}\}=\{1,i,-1,-i\}$

\begin{align*} A_4(x)&=\sum_{k=0}^\infty \binom{n+4k-1}{4k}x^k\\ &=\frac{1}{(1-\sqrt[4]{x})^n}+\frac{1}{(1-i\sqrt[4]{x})^n}+\frac{1}{(1+\sqrt[4]{x})^n}+\frac{1}{(1+i\sqrt[4]{x})^n} \end{align*}


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.