3
$\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$ Aug 14 at 13:00
  • $\begingroup$ I tried it, but it could not print the steps. $\endgroup$
    – giti
    Aug 14 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$ Aug 14 at 13:15
  • $\begingroup$ The expression is simplified now. $\endgroup$
    – giti
    Aug 14 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
    Aug 15 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$

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.