4
$\begingroup$

I am trying to show that $$\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n}\prod_{j=0}^{i}\frac{kn-j-k}{kn-j}=\frac{k^{k+1}-(k-1)^{k+1}}{(k+1)k^{k}}$$ for all $k\in\mathbb{N}$, $k\geq 4$.

I could verify the statement with Mathematica, but I could not find a self-standing proof. The product is telescopic, but I could only derive lower bounds instead of the exact value of the limit.

$\endgroup$
5
  • $\begingroup$ Have you tried Mathematica's Trace mode? Might help $\endgroup$ Commented Aug 14, 2022 at 13:00
  • $\begingroup$ I tried it, but it could not print the steps. $\endgroup$
    – giti
    Commented Aug 14, 2022 at 13:02
  • $\begingroup$ just to make sure there's no typo, did you indeed mean to write $(k-1)(k-1)^k$ in the numerator of the RHS (instead of $(k-1)^{k+1}$)? $\endgroup$ Commented Aug 14, 2022 at 13:15
  • $\begingroup$ The expression is simplified now. $\endgroup$
    – giti
    Commented Aug 14, 2022 at 13:52
  • 1
    $\begingroup$ I guess Mathematica used the identity $$ \sum_{k=a}^{b}\frac{\left(m-k\right)!}{\left(n-k\right)!}\ =\frac{\left(m-a+1\right)!}{\left(m-n+1\right)\left(n-a\right)!}-\frac{\left(m-b\right)!}{\left(m-n+1\right)\left(n-b-1\right)!} $$ together with the Stirling-approximation, i.e. substituting $ n!\leftarrow \sqrt{2\pi n}\;\left(\frac{n}{\mathrm{e}}\right)^n$ within the limit, then matched the products that converged and extracted them from the limit. The result is nowhere as clean as the given answer though $\endgroup$
    – Sudix
    Commented Aug 15, 2022 at 5:11

1 Answer 1

8
$\begingroup$

Start by re-expressing the product term \begin{align}\frac{(kn-k)(kn-k-1)\cdots(kn-k-i)}{(kn)(kn-1)\cdots(kn-i)} &=\frac{(kn-i-1)\cdots(kn-i-k)}{(kn)\cdots(kn-k+1)}=\frac{\binom{kn-1-i}k}{\binom{kn}k}. \end{align} So, the given sum $S_n(k):=\sum_{i=1}^n\prod_{j=0}^i\frac{kn-j-k}{kn-j}$ reads \begin{align} S_n(k)&=\frac1{\binom{kn}k}\sum_{i=1}^n\binom{kn-1-i}k =\frac1{\binom{kn}k}\sum_{j=0}^{n-1} \binom{kn-n-1+j}{k} \\ &=\frac1{\binom{kn}k}\left[\sum_{\ell=0}^{kn-2} \binom{\ell}k -\sum_{\ell=0}^{kn-n-1} \binom{\ell}k\right] \\ &=\frac1{\binom{kn}k}\left[\binom{kn-1}{k+1}-\binom{kn-n}k\right] \\ &=\frac{kn-1}{k+1}\cdot\prod_{j=1}^k\frac{kn-1-j}{kn-j}- \frac{kn-n}{k+1}\cdot\prod_{j=1}^k\frac{kn-n-1-j}{kn-j} \end{align} where we have utilized the identity $\sum_{\ell=0}^N\binom{\ell}k=\binom{N+1}{k+1}$. Therefore, going back to the required limit \begin{align} \lim_{n\rightarrow\infty}\frac1nS_n(k) &=\lim_{n\rightarrow\infty} \frac{kn-1}{(k+1)n}\cdot\prod_{j=1}^k\frac{kn-1-j}{kn-j}- \frac{(k-1)n}{(k+1)n}\cdot\prod_{j=1}^k\frac{(k-1)n-1-j}{kn-j} \\ &=\frac{k}{k+1}-\frac{k-1}{k+1}\cdot\frac{(k-1)^k}{k^k} =\frac{k^{k+1}-(k-1)^{k+1}}{(k+1)\,k^k}. \end{align} Your claim has been verified.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .