Is there a formula for $\sum_{j=1}^n \binom{m j}{m}$, where $m$ is an integer?

Question

Is there a formula for $\sum_{j=1}^n \binom{m j}{m}$, where $m$ is an integer?

It's similar to the Hockey-stick-identity $$ \sum_{j=1}^{mn} \binom{j}{m} = \binom{mn+1}{m+1}, $$ but now we only want to consider every $m$-th summand. Is there a formula or an upper bound (that's better than $\binom{mn+1}{m+1}$)?

Answer 1

Disclaimer

This answer does not contain a closed form, only ideas and some stronger upper bound than the one provided in the original question.

Combinatorial Argument

You are asked to choose $m+1$ unordered distinct numbers from $1,2,...,mn+m$. What is the number of possibilities where the largest chosen number satisfies $x_{max}\equiv 1 \mod{m}$?

Let the largest chosen number is $mj+1$ with $j\in\{1,...,n\}$, then the remaining numbers must be chosen from $1,2,...,mj$. The number of possibilities are then given by the original equation:

$$ \sum_{j=1}^{n}\binom{mj}{m} $$

Upper Bound

The number of sets with largest number $x_{max}\equiv k\mod{m}$, but we use $m$ instead of $0$ here for convenience, is given below:

$$ \sum_{j=1}^{n}\binom{mj+k-1}{m} \geq \sum_{j=1}^{n}\binom{mj}{m} $$

If we sum over all possible integer $k$, we obtain all possible $m+1$ chosen numbers out of $mn+m$ integers:

$$ \sum_{k=1}^{m} \sum_{j=1}^{n}\binom{mj+k-1}{m} = \binom{mn+m}{m+1} $$ Therefore, one can see that there is an upper bound:

$$ \frac{1}{m} \binom{mn+m}{m+1} \geq \sum_{j=1}^{n}\binom{mj}{m} $$

Remarks

Hope others can also give their thoughts and ideas. Also hope this is helpful for you.

Answer 2

Starting from @Rezha Adrian Tanuharja's upper bound $$A=\frac 1m \binom{m (n+1)}{m+1}=\frac{n\, \Gamma (m(n+1))}{\Gamma (m+2) \,\,\Gamma (m n+1)}$$n for large values of $m$

$$\log(A)=((n+1) \log (n+1)-n \log (n))\,m+\frac 12 \log \left(\frac{n (n+1)}{2 \pi m^3}\right)-$$ $$\frac{13 n^2+13 n+1}{12 m n (n+1)}+\frac{1}{2 m^2}+O\left(\frac{1}{m^3}\right)$$

Trying for $m=123$ and $n=45$, the above truncated expansion gives $$\log(A)=588.248 \quad\implies\quad A=2.97012\times 10^{255} $$ while the summation would give $5.66477\times 10^{254}$.

This looks pretty good.

Answer 3

We can reinterpret Rezha Adrian Tanuharja's answer as follows: for fixed $m$, we have the function $\binom{x}{m}$ is increasing as a function of $x \in \mathbb{N}$; therefore $$m \cdot \binom{jm}{m} \leq \binom{jm}{m} + \binom{jm + 1}{m} + \ldots + \binom{jm + m - 1}{m}$$ for any $j \geq 0$. (And then substitute and use the hockey stick identity.) But in fact for fixed $m$ we also have that $\binom{x}{m}$ is convex as a function of $x \in \mathbb{N}$; therefore $$m \cdot \binom{jm}{m} \leq \binom{jm - \lceil m/2\rceil + 1}{m} + \binom{jm - \lceil m/2\rceil + 2}{m} + \ldots + \binom{jm + \lfloor m/2\rfloor}{m}$$ for any $j \geq 0$. Consequently we can improve Rezha Adrian Tanuharja's answer slightly to $$ \sum_{j = 1}^n \binom{jm}{m} \leq \frac{1}{m} \binom{nm + \lfloor m/2\rfloor + 1}{m + 1}.$$

Answer 4

Im not sure about a closed form for the sum, but for fixed $m$, we have an asymptotic formula $$\sum_{j=1}^n\binom{mj}{m}\sim\frac{m^m}{(m+1)!}n^{m+1}.$$ To show this we can use the generating function of $(a_n)=\left(\sum_{j=1}^n\binom{mj}{m}\right)$. \begin{align*} f(z)&=\sum_{n=1}^\infty a_nz^n\\ &=\sum_{n=1}^\infty\sum_{j=1}^n\binom{mj}{m}z^n\\ &=\sum_{j=1}^\infty\sum_{n=j}^\infty\binom{mj}{m}z^n\\ &=\frac{1}{1-z}\sum_{j=1}^\infty\binom{mj}{m}z^j\\ &=\frac{1}{1-z}\sum_{j=1}^\infty\frac{(mj)(mj-1)\cdots(mj-m+1)}{m!}z^j. \end{align*} Now considering $f(z^m),$ we have \begin{align*} f(z^m)&=\frac{1}{1-z^m}\sum_{j=1}^\infty\frac{(mj)(mj-1)\cdots(mj-m+1)}{m!}z^{mj}\\ &=\frac{1}{1-z^m}\sum_{j=1}^\infty\frac{z^m}{m!}\frac{d^m}{dz^m}z^{mj}\\ &=\frac{z^m}{1-z^m}\cdot\frac{1}{m!}\frac{d^m}{dz^m}\left(\frac{z^m}{1-z^m}\right)\\ &=\frac{z^m}{1-z^m}\cdot\frac{1}{m!}\frac{d^m}{dz^m}\left(-1+\frac{1}{1-z^m}\right)\\ &=\frac{z^m}{1-z^m}\cdot\frac{1}{m!}\frac{d^m}{dz^m}\left(\frac{1}{1-z^m}\right)\\ &=\frac{z^m}{z^m-1}\cdot\frac{1}{m!}\frac{d^m}{dz^m}\left(\frac{1}{z^m-1}\right)\\ \end{align*} Using the method of partial fractions, we have $$\frac{1}{z^m-1}=\frac{1}{m}\sum_{j=1}^m\frac{r_j}{z-r_j}.$$ Where $r_j=\exp\left(2i\pi j/m\right)$. Hence \begin{align*} f(z^m)&=\frac{z^m}{z^m-1}\cdot\frac{1}{m!}\cdot\frac{1}{m}\sum_{j=1}^m\frac{r_j(-1)^mm!}{\left(z-r_j\right)^{m+1}}\\ &=\frac{z^m}{z^m-1}\cdot\frac{(-1)^m}{m}\sum_{j=1}^m\frac{r_j}{\left(z-r_j\right)^{m+1}}. \end{align*} And $$f(z)=\frac{z}{z-1}\cdot\frac{(-1)^m}{m}\sum_{j=1}^m\frac{r_j}{\left(z^{1/m}-r_j\right)^{m+1}}.$$ I claim that $f$ is a rational function, to show this, we will show by induction that the $k$th derivative of $1/(z^m-1)$ takes the form $z^{m-k}S_k(z^m)/T_k(z^m)$ for some polynomials $S_k$, $T_k$. Indeed for $k=0$ we may take $S_0(z^m)=1$ and $T_0(z^m)=z^m(z^m-1)$, now assume that the $r$th derivative of $1/(z^m-1)$ takes this form for some $r\geq0$ and consider \begin{align*} \frac{d^{r+1}}{dz^{r+1}}\left(\frac{1}{z^m-1}\right)&=\frac{d}{dz}\left(\frac{z^{m-r}S_r(z^m)}{T_r(z^m)}\right)\\ &=\frac{z^{m-r-1}((m-r)S_r(z^m)T_r(z^m)+mz^m(T_r(z^m)S_r^\prime(z^m)-S_r(z^m)T_r^\prime(z^m)))}{T_r(z^m)^2} \end{align*} This is of the expected form and so the result follows by induction. Therefore the $m$th derivative of $1/(z^m-1)$ is a rational function of $z^m$ from which it follows that $f(z^m)$ is a rational function of $z^m$ and hence $f(z)$ is a rational function of $z$.

If $\alpha$ is a pole of $f$, then $\alpha^{1/m}$ is a pole of $f(z^m)$ and hence $\alpha^{1/m}$ is an $m$th root of unity. It follows that $\alpha=1$ and that $f$ is of the form $P(z)/(z-1)^r$ for some polynomial $P$. We have \begin{align*} \lim_{z\rightarrow1}\left((z-1)^{m+2}f(z)\right)&=\lim_{z\rightarrow1}\left(z\cdot\frac{(-1)^m}{m}\sum_{j=1}^mr_j\left(\frac{z-1}{z^{1/m}-r_j}\right)^{m+1}\right)\\ &=\frac{(-1)^m}{m}\lim_{z\rightarrow1}\left(\left(\frac{z-1}{z^{1/m}-1}\right)^{m+1}\right)\\ &=\frac{(-1)^m}{m}\cdot m^{m+1}\\ &=(-1)^mm^m \end{align*} This limit exists and is non-zero, so $r=m+2$ and $P(1)=(-1)^mm^m$. A theorem of Sedgewick now gives us an asymptotic formula for $a_n$, namely $$a_n\sim\frac{(-1)^{m+2}(m+2)P(1)}{(m+2)!}n^{m+1}=\frac{m^m}{(m+1)!}n^{m+1}.$$