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$.
Best Answer
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)$$