Show that $r_k^n/n \le \binom{kn}{n} < r_k^n$ where $r_k = \dfrac{k^k}{(k-1)^{k-1}}$

Question

Show that for $n \ge 2$, $\dfrac{r_k^n}{n+1} \le \binom{kn}{n} < r_k^n$ where $r_k = \frac{k^k}{(k-1)^{k-1}}$.

This is a generalization of How to prove through induction which asks for a proof that $\binom{2n}n<4^n$.

I wondered what was true for $\binom{kn}{n}$ and this is what I came up with.

Note that $r_k =k(1+\frac1{k-1})^{k-1} \sim ek $ for large $k$.

The key is to get bounds for $\dfrac{\binom{k(n+1)}{n+1}}{\binom{kn}{n}}$ that are not too dependent on $n$. The upper bound I get is not, the lower bound is, but telescopes nicely.

Note: The algebra here is uncomfortably messy. I would definitely like a simpler proof, perhaps depending on Stirling's theorem.

Here goes.

$\begin{array}\\ s_k(n) &=\dfrac{\binom{k(n+1)}{n+1}}{\binom{kn}{n}}\\ &=\dfrac{\frac{(kn+k)!}{(n+1)!(kn+k-n-1)!}}{\frac{(kn)!}{n!(kn-n)!}}\\ &=\dfrac{n!(kn-n)!(kn+k)!}{(n+1)!(kn)!(kn+k-n-1)!}\\ &=\dfrac{\prod_{j=0}^{n}(kn+k-j)}{(n+1)\prod_{j=0}^{n-1}(kn-j)}\\ &=\dfrac{\prod_{j=0}^{k-1}(kn+k-j)\prod_{j=k}^{n}(kn+k-j)}{(n+1)\prod_{j=0}^{n-1}(kn-j)}\\ &=\dfrac{\prod_{j=0}^{k-1}(kn+k-j)\prod_{j=0}^{n-k}(kn-j)}{(n+1)\prod_{j=0}^{n-1}(kn-j)}\\ &=\dfrac{\prod_{j=0}^{k-1}(kn+k-j)}{(n+1)\prod_{j=n-k+1}^{n-1}(kn-j)}\\ &=\dfrac{\prod_{j=0}^{k-1}(kn+k-j)}{(n+1)\prod_{j=0}^{k-2}(kn-(j+n-k+1)}\\ &=\dfrac{\prod_{j=0}^{k-1}(kn+k-j)}{(n+1)\prod_{j=0}^{k-2}((k-1)n-(j-k+1)}\\ &=\dfrac{(kn+k)\prod_{j=1}^{k-1}(kn+k-j)}{(n+1)\prod_{j=0}^{k-2}((k-1)n+k-j-1)}\\ &=k\dfrac{\prod_{j=0}^{k-2}(kn+k-j-1)}{\prod_{j=0}^{k-2}((k-1)n+k-j-1)}\\ &=k\prod_{j=0}^{k-2}\dfrac{kn+k-j-1}{((k-1)n+k-j-1)}\\ &<k\left(\dfrac{k}{k-1}\right)^{k-1}\\ &=\dfrac{k^k}{(k-1)^{k-1}}\\ \end{array} $

since, if $1 \le a \le k-1$,

$\begin{array}\\ \dfrac{kn+a}{(k-1)n+a}-\dfrac{k}{k-1} &=\dfrac{(kn+a)(k-1)-k((k-1)n+a)}{(k-1)((k-1)n+a)}\\ &=\dfrac{(k^2n-kn+ka-a)-(k^2n-kn+ak)}{(k-1)((k-1)n+a)}\\ &=\dfrac{-a}{(k-1)((k-1)n+a)}\\ &< 0\\ \end{array} $

To get the lower bound,

$\begin{array}\\ \dfrac{kn+a}{(k-1)n+a}-\dfrac{k}{k-1} &=\dfrac{-a}{(k-1)((k-1)n+a)}\\ &=\dfrac{-1}{(k-1)((k-1)n/a+1)}\\ &\ge\dfrac{-1}{(k-1)(n+1)}\\ &=-\dfrac{1}{(k-1)n+1}\\ \end{array} $

or

$\begin{array}\\ \dfrac{kn+a}{(k-1)n+a} &\ge\dfrac{k}{k-1}-\dfrac{1}{(k-1)n+1}\\ &=\dfrac{k((k-1)n+1)-(k-1)}{(k-1)((k-1)n+1)}\\ &=\dfrac{k(k-1)n+1}{(k-1)((k-1)n+1)}\\ &=\dfrac{k(k-1)n+1}{(k-1)^2n+k-1}\\ &>\dfrac{k(k-1)n}{(k-1)^2n+k-1}\\ &=\dfrac{kn}{(k-1)n+1}\\ &=\dfrac{k}{(k-1)+1/n}\\ &=\dfrac{k}{(k-1)(1+1/(n(k-1))}\\ &=\dfrac{k}{k-1}\dfrac1{1+1/(n(k-1))}\\ \end{array} $

so that

$s_k(n) \ge k\prod_{j=0}^{k-2}\dfrac{k}{k-1}\dfrac1{1+1/(n(k-1))} = \dfrac{k^k}{(k-1)^{k-1}}\prod_{j=0}^{k-2}\dfrac1{1+1/(n(k-1))} = \dfrac{k^k}{(k-1)^{k-1}}\dfrac1{(1+1/(n(k-1)))^{k-1}} $.

In an earlier problem I showed (here: Prove that, if $0 < x < 1$, then $(1+\frac{x}{n})^n < \frac1{1-x}$) that if $0 < x < 1$ then $(1+x/n)^n < \frac1{1-x}$. Therefore $(1+1/(n(k-1)))^{k-1} <\frac1{1-1/n} $

so that

$s_k(n) >\dfrac{k^k}{(k-1)^{k-1}}(1-1/n) =\dfrac{k^k}{(k-1)^{k-1}}\dfrac{n-1}{n} =r_k\dfrac{n-1}{n} $.

The products of $\dfrac{n-1}{n}$ telescope to give the lower bound stated.

Answer 1

No one else has done anything, so I thought I'd see what happens when I follow my own suggestion of using Stirling's formula.

Definitely easier and, of course, more precise.

Here we go.

Since $n! \approx \sqrt{2\pi n}(n/e)^n$,

$\begin{array}\\ \binom{kn}{n} &=\dfrac{(kn)!}{n!(kn-n)!}\\ &\sim \dfrac{\sqrt{2\pi kn}(kn/e)^{kn}} {(\sqrt{2\pi n}(n/e)^n)(\sqrt{2\pi (kn-n)}((kn-n)/e)^{kn-n})}\\ &= \sqrt{\dfrac{2\pi kn}{(2\pi n)(2\pi (kn-n))}}\dfrac{(kn)^{kn}} {((n)^n)(((kn-n))^{kn-n})}\\ &= \sqrt{\dfrac{k}{2\pi n(k-1)}}\dfrac{k^{kn}n^{kn}} {(n)^n((n(k-1))^{nk-n)})}\\ &= \sqrt{\dfrac{k}{2\pi n(k-1)}}\dfrac{k^{kn}} {(((k-1))^{kn-n})}\\ &= k^n\sqrt{\dfrac{k}{2\pi n(k-1)}}\left(\dfrac{k} {k-1}\right)^{n(k-1)}\\ &= k^n\sqrt{\dfrac{k}{2\pi n(k-1)}}\left(\dfrac{k} {k-1}\right)^{kn-n}\\ &= \sqrt{\dfrac{k}{2\pi n(k-1)}}k^n\left(\left(\dfrac{k} {k-1}\right)^{k-1}\right)^{n}\\ &= \sqrt{\dfrac{k}{2\pi n(k-1)}}\left(\dfrac{k^k} {(k-1)^{k-1}}\right)^{n}\\ \end{array} $

This confirms my main result of the ratio of consecutive terms being $\dfrac{k^k} {(k-1)^{k-1}} $, with the multiplier of $\sqrt{\dfrac{k}{2\pi n(k-1)}}$ being nicely between $\dfrac1{n}$ and $1$.