Generating function for sequence $a_i={n+im-1 \choose im}$

Question

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!

Answer 1

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.

Answer 2

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*}