5
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ Why the downvote? $\endgroup$ Mar 24 at 12:50

4 Answers 4

5
$\begingroup$

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.

enter image description here


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

enter image description here

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,

enter image description here

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)$$

$\endgroup$
7
  • $\begingroup$ Thank you, this essentially answers why the limit of $S_k$ is $2/3$. I can not yet see the pen-and-paper proof, but it should be doable based on the cited paper. However, it is not clear to me if this also helps to prove that $S_k$ is decreasing from $k=3$. (What I need is that $S_k\geq 2/3$ for all $k$.) $\endgroup$
    – macat
    Mar 27 at 1:12
  • $\begingroup$ Update: This will not imply that $S_k$ is decreasing, because the error terms hidden by $O(1/n)$ may change signs (based on experiments). So, another reasoning is necessary to prove that $S_k$ is decreasing from $k=3$. $\endgroup$
    – macat
    Mar 27 at 11:34
  • 1
    $\begingroup$ @macat From this simpler ratio you can apply Zeilberger´s algorithm to find the $\ell$-th order recurrence satisfied by $S_n$, as $$S_{n+1}=q_nS_n+q_{n-1}S_{n-1}+...q_{n-\ell}S_{n-\ell}$$. By analyzing the coefficients $q_n$ it should be possible to prove that $S_{n+1}<S_n$. In fact you should get $|q_j|<1,\ \ j=n-\ell, ..., n$ for $\ n>n_0$. $\endgroup$ Mar 27 at 19:50
  • 1
    $\begingroup$ This is a very old question. The answer is yes for linear recurrences. Even the asymptotic expansion can be obtained, Birkhoff and Trjitzinsky (1932). A good Introduction is found in Appendix B of Jet Wimp - Computation with Recurrence Relations (Applicable Mathematics Series) (1984), $\endgroup$ Mar 28 at 15:49
  • 1
    $\begingroup$ The method is named Creative Telescoping. But I guess it is tough to apply it pen-and-paper in this case. Expressions are not simple. Take a look, for instance, at the generating function obtained by Max Alekseyev. $\endgroup$ Mar 28 at 16:15
7
$\begingroup$

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.$$

$\endgroup$
7
  • 1
    $\begingroup$ I need some time to digest this magical solution. Could this approach also explain why $S_k$ is decreasing? $\endgroup$
    – macat
    Mar 27 at 22:08
  • $\begingroup$ This can probably be obtained from accurate asymptotic analysis of the coefficients of $(1-x){\cal S}(x)$. $\endgroup$ Mar 27 at 22:53
  • 1
    $\begingroup$ I am not sure how you got the limit $2/3$ of $S_k$. Of course, by the Hardy–Littlewood tauberian theorem (en.wikipedia.org/wiki/…), you can get $S_1+\cdots+S_k\sim2k/3$. However, if e.g. $s_k=2/3+\sum_{j\ge1}1(k=j^2)$, then you get $\lim_{x\uparrow1}(1-x)\sum_{k\ge1}s_k x^k=2/3$, whereas $s_k$ does not converge to a limit. $\endgroup$ Mar 28 at 4:31
  • 2
    $\begingroup$ @IosifPinelis: The function ${\cal S}(x) - \frac{2}{3}\frac{1}{1-x}$ converges for $|x|<8$ and thus its coefficient of $x^k$ is smaller than $(\frac18+\epsilon)^k$ giving the desired limit. $\endgroup$ Mar 28 at 13:49
  • 1
    $\begingroup$ @IosifPinelis: Yes, there should not be factor $k$ in the denominator (fixed now!). Thanks for noticing. To switch to $f(x)$, I use Lagrange–Bürmann formula. $\endgroup$ Mar 29 at 22:01
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Equation (1) looks promising, because this would also show that the limit of $S_k$ is $2/3$. Could this expression be obtained somehow with Mathematica or Maple? $\endgroup$
    – macat
    Mar 28 at 9:27
  • 1
    $\begingroup$ Maple's Ryabenko-Skorokhodov asymptotics give $$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}}+O\left(\frac{1}{n^2}\right)\right]$$ where $c_1=.5922905035e-6,\ c_2=.1110443475,\ c_3=.2493491970e-2$ are given numerically. $\endgroup$ Mar 28 at 17:18
  • $\begingroup$ @JorgeZuniga : Thank you for your comment. However, I doubt that this expansion is true. Indeed, substituting $S_n=\frac{2}{3}+\frac{a}{\sqrt{n}}+\frac{b}{n^{2/2}}+\frac{c}{n^{3/2}}+\frac{d}{n^{4/2}}+\cdots$ into your recurrence gives $a=0$, $b=2/27$, $c=0$, $d=2/81$. $\endgroup$ Mar 28 at 18:06
  • $\begingroup$ @IosifPinelis. Thanks a lot for pointing this out, It seems to be a matter of precision used in Maple, In fact $$\frac{2}{3}c_1\simeq 1e-6 \simeq 0,\ \ \frac{2}{3}c_2 \simeq 0.999399\frac{2}{27},\ \ \frac{2}{3}c_3\simeq 1e-2$$and precision is lost for higher order terms. I will check this out with a graeter working precision or fitting some computing parameters. Thanks again. $\endgroup$ Mar 28 at 19:46
  • 1
    $\begingroup$ @macat : Mathematica does not seem to be able to handle this. (I do not know or have Maple.) $\endgroup$ Mar 28 at 20:19
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Sorry, I do not know why formula (1) does not compile correctly after I click on the link. $\endgroup$ Mar 28 at 6:39
  • $\begingroup$ I have been trying to avoid the computation of $P_k$ for $k=4,\dots,9$. Do you think this is possible? $\endgroup$
    – macat
    Mar 30 at 19:58
  • $\begingroup$ @macat : I think it might be possible to avoid the calculation for some of these $k$, but hardly for all of them -- at least with this method. But why do you want to avoid these straightforward calculations? $\endgroup$ Mar 30 at 20:47
  • $\begingroup$ The main motivation behind this is an infinite sequence of similar questions (which are not the subjects of this thread), and the present one is the simplest of them. It does not make any difficulty to compute a finite prefix of the $P_k$'s in the current setting, but it is an issue if you need to do this infinitely many times. It would be also nicer to avoid these straightforward but quite lengthy computations. $\endgroup$
    – macat
    Mar 30 at 23:03
  • $\begingroup$ Let $Q_k=S_k-S_{k-1}$. By Zeilberger's algorithm we have that $Q_{k+2}=\frac{(7k-6)Q_{k+1}+kQ_{k}}{8k+12}$. We can compute $S_3,S_4$ and $S_5$, and verify that $Q_4>0$ and $Q_4\geq Q_5$. By induction, one gets that $Q_{k+2}=\frac{(7k-6)Q_{k+1}+kQ_{k}}{8k+12}\geq\frac{8k-6}{8k+12}Q_{k+1}$, hence $S_k$ is decreasing from $k=3$. $\endgroup$
    – macat
    Apr 3 at 13:06

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.