Limit of a sum with binomial coefficients

Question

Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$ $$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$ $$C_k = \frac{\sum_{i=1}^k(2k-2i-1){2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$ for $k\in\mathbb{N}$, where the binomial coefficients are to be taken as zero if any of the parameters are negative.

I want to prove that $S_k:=A_k+B_k+C_k$ is decreasing from $k=3$ and $S_k\to2/3$ as $k\to\infty$. I have been struggling with a formal mathematical proof for a few days, and I hope that somebody can point me to the right direction.

Note that based on the first 10000 values, the above statements seem to hold, and $A_k,B_k$ and $C_k$ seem to tend to $2/9$ as $k\to\infty$, furthermore, $A_k$ and $B_k$ are decreasing whereas $C_k$ is increasing from $k=3$. Also note that $B_k+C_k$ is simply

$$\frac{\sum_{i=1}^k(2k-i-1){2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}.$$

The reason for not making this simplification is that I found it interesting that each of $A_k,B_k$ and $C_k$ tends to $2/9$. It may be better to handle $B_k+C_k$ as a unite.

Motivation: This question is related to a preceding question. In the setting explained in the other question, $S_k$ is the probability of the marked red ball staying red in a random permutation of $(2k-1)$ balls. The above statements are already proven in an excellent answer to the preceding question. The aim of the present question is to give a new proof using $A_k,B_k,C_k$.

Answer 1

Ryabenko-Skorokhodov algorithm is implemented in Maple package SumTools since Maple v11. (DefiniteSumAsymptotic function). Check this reference if you want to see all the details.

Ryabenko, A. A.; Skorokhodov, S. L., Asymptotics of sums of hypergeometric terms, Program. Comput. Softw. 31, No. 2, 65-72 (2005); translation from Programmirovanie 2005, No. 2, 22-31 (2005). ZBL1102.41029.

A, B and C asymptotics are obtained using DefiniteSumAsymptotic function. Denominator F is obtained using Stirling's approximation.

---

To prove that $S_{n+1}-S_n<0,\ \ \forall n>n_0$, I guess it is better to work with this simpler expression $$S_n=\frac{\sum_{k=1}^n{2n-k-1 \choose k-1}{k \choose n-k}}{{2n-1 \choose n}}$$ Note that sum lower index starts at $\lceil n/2 \rceil$.

Applying Ryabenko-Skorokhodov asymptotics to this expression, Maple outputs (using extended working precision)

$$S_n=\frac{2}{3}\cdot\left[1+\frac{c_1}{n^\frac{1}{2}}+\frac{\frac{1}{2}c_1^2+c_2}{n}+\frac{\frac{1}{6}c_1^3+c_1c_2+c_3}{n^\frac{3}{2}}+\frac{\frac{1}{24}c_1^4+\frac{1}{2}c_2^2+\frac{1}{2}c_1c_2+c_1c_3+c_4}{n^2}\right]+O\left(n^{-\frac{5}{2}}\right)$$ where these values are given numerically$$c_1=6.0502078578\cdot 10^{-14} \simeq 0,\ c_2=0.11111111109 \simeq \frac{1}{9},\ c_3=2.985896667978\cdot 10^{-9} \simeq 0,\ c_4=0.03086397685117\simeq \frac{5}{162}$$ Note that a proper fitting of computing parameters was made in order to produce a reasonable rational approximation. (Thanks to Iosif Pinelis for pointing this out)

---

To prove that for $S_n>0$, $\ \frac{S_{n+1}}{S_n}<1\ $ holds asymptotically, we apply Wilf-Zeilberger's machinery as it is contained in this reference,

Petkovšek, Marko; Wilf, Herbert S.; Zeilberger, Doron, (A=B). With foreword by Donald E. Knuth, Wellesley, MA: A. K. Peters. xii, 212 p. (1996). ZBL0848.05002.

by using Maple's Zeilberger() Function

Therefore, we get this recurrence of order 2 starting from $S_0=0 \wedge S_1=1$. (You can check that this recurrence produces the sequence values). $$p_n=\frac{21 n^2 + 44 n + 16}{24 n^2 + 52 n + 24},\ \ \ \ q_n=\frac{3 n^2 + 8 n + 5}{24 n^2 + 52 n + 24}$$ $$S_{n+2}=p_n\cdot S_{n+1}+q_n\cdot S_{n}$$ $$\left( \frac{S_{n+1}}{S_n} \right)^2\sim\frac{S_{n+2}}{S_{n+1}}\cdot\frac{S_{n+1}}{S_n} =p_n\cdot \frac{S_{n+1}}{S_n}+q_n$$

Thus, y$^\ell$ in the recurrence polynomial is mapped to $\left( {\frac{S_{n+1}}{S_{n}}}\right) ^\ell \ ,\ell>0\ $ as $n\rightarrow\infty$. The asymptotic roots of this polynomial must be found. This is done using Wolfram's AsymptoticSolve[] function,

Just the second solution is admissible and $S_n$ is decreasing (it approaches its limit from above monotonically),$$\frac{S_{n+1}}{S_n} \sim 1-\frac{1}{9n^2}<1$$ as $n\rightarrow\infty$. The claim $\exists\ n_0\ \mathrm{s.t.}\ S_n>S_{n+1}\ \forall\ n>n_0\ $ is proved.

For more details (pen-and-paper) on this last step. This result is obtained from $$\frac{S_{n+1}}{S_n}\sim \frac{1}{2}\cdot \left( p_n+\sqrt{p_n^2+4q_n}\right)$$ using $$p_n = \frac{7}{8}-\frac{1}{16\,n}-\frac{7}{96\,n^2}+\frac{127}{576\,n^3}-\frac{1399}{3456\,n^4}+\frac{13615}{20736\,n^5}+O\left(\frac{1}{n^6}\right)$$ and $$q_n=\frac{1}{8}+\frac{1}{16\, n}-\frac{5}{96\,n^2}+\frac{29}{576\,n^3}-\frac{197}{3456\,n^4}+\frac{1517}{20736\,n^5}+O\left(\frac{1}{n^6}\right)$$ which gives $$\frac{S_{n+1}}{S_n}=1-\frac{1}{9\,n^2}+\frac{20}{81\,n^3}-\frac{104}{243\,n^4}+O\left(\frac{1}{n^5}\right)$$

Answer 2

Simplifying we have: $$S_k = \frac{\sum_{i=1}^k i\binom{k}{2i-k}\binom{2k - i - 1}{k - 1}}{k\binom{2k-1}{k}}.$$ It follows that $S_k$ equals the coefficient of $x^k$ in $$\frac{1+2x}{2(1+x)(1-x)^k\binom{2k-1}{k}}.$$ Using Lagrange inversion, we further have it as the coefficient of $x^k$ in $\frac{f(x)}{\binom{2k-1}{k}}$, where $$f(x):=\frac{1+x+(1+2x)(1-4x)^{-1/2}}{2(2+x)}.$$ For $k\geq 1$, we further have $$\frac1{k\binom{2k-1}{k}} = \int_0^1 t^{k-1}(1-t)^{k-1} dt$$ and thus $$S_k = [x^{k-1}]\int_0^1 f'(xt(1-t))dt.$$ Computing this integral, we get the generating function: $${\cal S}(x):=\sum_{k\geq 1} S_k x^k = \frac{x^{1/2}}{(8+x)^{3/2}}\left(4\operatorname{arctanh}\frac{x^{1/2}}{(8+x)^{1/2}} - 2\operatorname{arctanh}\frac{x-1-x^{1/2}(8+x)^{1/2}}3 + 2\operatorname{arctanh}\frac{x-1+x^{1/2}(8+x)^{1/2}}3\right) + \frac{2}{3(1-x)} - \frac{16}{3(8+x)}.$$

This function has poles at $x=1$ and $x=-8$ and thus $$\lim_{k\to\infty} S_k = \lim_{x\to 1}(1-x){\cal S}(x) = \frac23.$$

Answer 3

It appears that \begin{equation*} S_k=\frac23+\frac ak+\frac b{k^{3/2}}+\frac c{k^2}+\frac{d_k}{k^{5/2}},\tag{1}\label{1} \end{equation*} where $a,b,c$ are certain real numbers such that $a>0$ and the $|d_k|$'s are bounded by a certain real $d$.

A proof of \eqref{1} should be rather straightforward (even if quite tedious) using Stirling's formula and the Laplace method -- both with higher-order terms but with explicit bounds on the remainder terms everywhere, as well as the Euler--Maclaurin summation formula. The first steps in this direction can be the observations that (i) \begin{equation*} S_k=\sum_{i=1}^k a_{k,i} \end{equation*} with
\begin{equation*} a_{k,i}:=\frac{i (2 k-i-1)!}{(2 i-k)! (k-i)! (2 k-2 i)!}\Big/ \binom{2 k-1}{k} \end{equation*} and (ii) $a_{k,i+1}\ge a_{k,i}$ if $i\le\frac23\,k-1$ and $a_{k,i+1}\le a_{k,i}$ if $i\ge\frac23\,k$.

It will then follow from \eqref{1} that $S_k$ is decreasing in $k\ge k_{a,b,c,d}$, where $k_{a,b,c,d}$ depends only on $a,b,c,d$. If $k_{a,b,c,d}$ is not too large, it should then be easy to check that $S_k$ is decreasing in $k$ if $3\le k\le k_{a,b,c,d}$. Thus, you will get that $S_k$ is decreasing in all $k\ge3$, to $2/3$, as desired.

Answer 4

Jorge Zuniga showed the identity \begin{equation*} S_{n+2}=p_n\,S_{n+1}+q_n\,S_n, \tag{1}\label{1} \end{equation*} where \begin{equation*} p_n=\frac{21 n^2 + 44 n + 16}{24 n^2 + 52 n + 24},\quad q_n=\frac{3 n^2 + 8 n + 5}{24 n^2 + 52 n + 24}. \end{equation*} Based on \eqref{1}, Jorge Zuniga showed that \begin{equation*} S_{n+1}<S_n \tag{2}\label{2} \end{equation*} for all large enough $n$.

Let us show that \eqref{2} holds for all $n\ge3$. Rewrite \eqref{1} as \begin{equation*} R_{n+1}=p_n+q_n/R_n, \tag{3}\label{3} \end{equation*} where \begin{equation*} R_n:=S_{n+1}/S_n. \end{equation*} Note that \begin{equation*} R_{1,n}<R_n<R_{5,n} \tag{4}\label{4} \end{equation*} for $n=10$, where \begin{equation*} R_{a,n}:=1-\frac{1}{9 n^2+a n}. \end{equation*}

Let us prove by induction on $n$ that \eqref{4} holds for all $n\ge10$. Suppose \eqref{4} holds for some $n\ge10$. For all $n\ge10$ we have \begin{equation*} R_{1,n+1}\le p_n+q_n/R_{5,n},\quad p_n+q_n/R_{1,n}\le R_{5,n+1} \end{equation*} and hence, by \eqref{3} and \eqref{4}, \begin{equation*} R_{1,n+1}\le p_n+q_n/R_{5,n}<R_{n+1}<p_n+q_n/R_{1,n}\le R_{5,n+1}, \end{equation*} so that \eqref{4} holds with $n+1$ in place of $n$. So, for all $n\ge10$ inequalities \eqref{4} hold and hence $R_n<R_{5,n}<1$, which implies \eqref{2} -- for $n\ge10$. It is easy to see that \eqref{2} holds for $n=3,\dots,9$ as well.

Thus, \eqref{2} holds for all $n\ge3$, as desired.