2
$\begingroup$

Let $$A_k = \sum_{i=1}^k i {3k-2i-1 \choose i-1} {2i-2 \choose k-i}$$ $$B_k = \sum_{i=1}^k i {3k-2i-2 \choose i-1} {2i-1 \choose k-i}$$ $$C_k = \sum_{i=1}^k (3k-2i-2) {3k-2i-3 \choose i-1} {2i\choose k-i}$$ for $k\in\mathbb{N}$, where the binomial coefficients are to be taken as zero if any of the parameters are negative. I am trying to show that $S_k\geq 7/12=S_2$ for all $k$, where $$S_k=\frac{A_k+B_k+C_k}{k{3k-2\choose k}}.$$

The problem is that the formulas are quite complicated, and I can not find a way to work with them. Along the lines of the answers to a previous question, one can show that $S_k\to 3/5$ as $k\to\infty$. Therefore, it would be enough to show that $S_k$ is decreasing from $k=3$, which seems to be true based on the first 10000 values. Ideally, the proof should not involve the computation of $S_k$ for any $k>3$.

$\endgroup$
3
  • $\begingroup$ Based on an answer to the linked question, one can try to construct a recursion for $S_k$. Using Zeilberger's algorithm, one gets that $p_4S_{k+4}+p_3S_{k+3}+p_2S_{k+2}+p_1S_{k+1}+p_0S_{k}=0$, where the $p_i$'s are polynomials in $k$ with degree 10. This expression seems way too complicated to work with and to show the desired bound for all $k$ without checking the statement for many small $k$'s with a computer. $\endgroup$
    – macat
    Mar 31, 2022 at 20:35
  • $\begingroup$ Two questions. First, do you have a consolidated numerator summand for $S_k$ of type $a{b\choose c}{d\choose e}$?. Second, how did you get polynomials in k of degree 10?. I think they could be higher. $\endgroup$ Apr 2, 2022 at 2:00
  • $\begingroup$ @Jorge Zuniga, 1) I can not write $S_k$ as a single sum whose terms are of the form $a{b\choose c}{d\choose e}$. 2) In my first comment, I was reporting the result given by Maple's Zeilberger function applied to $S_k$ defined as above. $\endgroup$
    – macat
    Apr 2, 2022 at 4:18

1 Answer 1

3
$\begingroup$

Since this is a very similar question to another one already done, more than a partial answer, I will provide a detailed explanation to solve this kind of problems. I will try to apply it to this specific case.

First, you need support from some Math Symbolic Software. Either commercial soft, Mathworks Matlab, Maplesoft Maple or Wolfram's Mathematica or Non-commercial, Sage, Maxima. I will apply methods from Maple and Mathematica.

Second, even if you ask for a wide range of $n$ values. Solution is based on sequence asymptotics for $n>n_0$ and recurrences with some given or found $n_0$. Induction is applied from this point.

I. Asymptotics

Some basics are required (fractional powers of $n$ can be added accordingly)

If $$S_n=S+\frac{s_1}{n}+\frac{s_2}{n^2}+o(n^{-2}),\ S\ne 0$$ and $$S_{n+1}/S_n=R+\frac{r_1}{n}+\frac{r_2}{n^2}+o(n^{-2})$$ then $R=1,\ r_1=0,\ r_2=-s_1/S$. So that if 2 values of $[S,s_1,r_2]$ are known, the third one is also known. For $S,s_1>0$ the sequence $S_n$ is asymptotically decreasing since as $n\rightarrow\infty$ $$S_{n+1}/S_n=1-\frac{s_1}{S}\cdot\frac{1}{n^{2}}+o(n^{-2})<1$$ Your $S_n=A_n+B_n+C_n$ is the sum of 3 sequences of the same family. So that $S=A+B+C$ and $$S_n=A+B+C+\frac{a_1+b_1+c_1}{n}+\frac{a_2+b_2+c_2}{n^2}+o(n^{-2})$$For $\rho=\frac{a_1+b_1+c_1}{A+B+C}\ $ and $\ R_n=S_{n+1}/S_n$ $$R_n=1-\rho\cdot\frac{1}{n^{2}}+o(n^{-2})$$

To get $\rho$, you can apply for each sequence $A_n,B_n,C_n$ separatedly Ryabenko-Skorokhodov asymptotics (a big subset of Birkhoff and Trjitzinsky Theory on linear recurrence asymptotics) as implemented in Maple's function DefiniteSumAsymptotic(). This gives the limits $A,B,C$ immediately. It also gives numerically $a_1,b_1,c_1$, however you need to work with the last argument of this function to control some computing parameters. Transforming these values to rationals is simple.

enter image description here

So we have $$A_n=A+\frac{a_1}{n}+o(n^{-1})= \frac{3}{25}+\frac{96}{625}\frac{1}{n}+o(n^{-1})$$ $$B_n=B+\frac{b_1}{n}+o(n^{-1})= \frac{3}{25}+\frac{71}{625}\frac{1}{n}+o(n^{-1})$$ $$C_n=C+\frac{c_1}{n}+o(n^{-1})= \frac{9}{25}-\frac{132}{625}\frac{1}{n}+o(n^{-1})$$Therefore $S=3/5$,$\ s_1=7/125,$ and we get $\ \rho=7/75$, $$S_n=\frac{3}{5}+\frac{7}{125}\frac{1}{n}+o(n^{-1})$$ $$R_n=1-\frac{7}{75}\frac{1}{n^2}+o(n^{-2})$$ This last expression proves that $S_n$ is a decreasing sequence from some $n>n_0$

II.- Recurrences

On the other side, Zeilberger's algorithm allows to find and provide a proof of linear recurrences of order $\ell$ for holonomic (hypergeometric) sequences $Q_n$ $$p_\ell Q_{n+\ell}+p_{\ell-1} Q_{n+\ell-1}+...+p_1 Q_{n+1}+p_{0} Q_{n} =0$$ $$Q_{n+\ell}=q_{\ell-1} Q_{n+\ell-1}+...+q_1 Q_{n+1}+q_{0} Q_{n} $$where $p_\ell$ and $q_\ell$ are polynomials and rationals in $n$ respectively. If you map $Q_{n+\ell}\leftrightarrow y^\ell$ and solve the polynomial equation asymptotically for $y$ as $n\rightarrow\infty$ (using, for instance, AsymptoticSolve[] from Wolfram's Mathematica™) you get the asymptotic leading expression for $Q_{n+1}/Q_n$. For the kind of sequences (logarithmically convergent sequences) you are working on, the polynomial solution $y\rightarrow 1$ as $n\rightarrow\infty$ must be selected.

Zeilberger's algorithm is implemented in Maple™, Maxima™ and Mathematica™ using Sigma™ package. [Sigma - A summation package by Carsten Schneider \ © RISC \ V 2.89 (November 10, 2021)]

We use Zeilberger on $A_n$,$\,B_n\,$ and $\,C_n$ to get recurrences of order 4 with polynomial degrees 15, 16 and 16 respectively. Asymptotic polynomial roots for $y\rightarrow 1$ are $$A_{n+1}/A_n=1-\frac{32}{25}\frac{1}{n^2}+o(n^{-2})$$ $$B_{n+1}/B_n=1-\frac{71}{75}\frac{1}{n^2}+o(n^{-2})$$ $$C_{n+1}/C_n=1+\frac{44}{75}\frac{1}{n^2}+o(n^{-2})$$ Therefore for $\left[A,B,C\right]=\left[\frac{3}{25},\frac{3}{25},\frac{9}{25}\right]$ we recover $\left[a_1,b_1,c_1\right]=\left[\frac{96}{625},\frac{71}{625},-\frac{132}{625}\right]$ and $\rho=\frac{7}{75}$

To prove that $S_n$ decreases from some $n_0,\,$ ($n_0 = 5$ in this case), it is convenient to work with $T_n=S_{n-1}-S_n$ and prove that $T_n>0$ for all $n>n_0$. Applying

enter image description here

Algorithm provides a recurrence of order 4 with polynomials of degree 12, giving $$T_{n+4}=r_3\,T_{n+3}+r_2\,T_{n+2}+r_1\,T_{n+1}+r_0\,T_{n}$$ where rational coefficients (depending on $n$) $\ r_1,\ r_2,\ r_3$ are positive and $r_0$ is negative. (If every $r_j$ were positive $T_{n+4}>0$ would follow immediately by induction starting at the first values from $n_0=5$). Coefficient limits are $[r_0,r_1,r_2,r_3]\rightarrow[\frac{-32}{59049},\frac{101}{6561},\frac{15404}{59049},\frac{176}{243}]\ $ as $\ n\rightarrow\infty$. Note that $T_n$ is an asymptotically decreasing sequence, as it is proved using the above tools, in fact $$T_{n+1}/T_n = 1-\frac{2}{n}+o(n^{-1})$$ We need now a bound such that for some $\alpha<0$ and $n>3$ $$r_0\,T_n > \alpha\,r_1\,T_{n+1}$$ $$T_{n+4}>r_3\,T_{n+3}+r_2\,T_{n+2}+(1+\alpha)\,r_1\,T_{n+1}$$By taking $\alpha=(1+\epsilon_n)\cdot\lim_{n\rightarrow\infty}r_0/r_1\,$ with $\,\epsilon_n=15/n$ and the limit ratio we obtain $$\alpha=-\frac{32}{909}\left(1+\frac{15}{n}\right)$$ Since $(1+\alpha)\,r_1,r_2,r_3>0$ for $n>3$, we get $T_{n+4}>\left([1+\alpha]\,r_1+r_2+r_3\right)\cdot T_{n+3}$ or equivalently $$T_{n+1}>\gamma(n)\cdot T_n$$with $\gamma(n)>0$ for $n>n_0$. A simple proof by induction complete these steps.

All this process can be coded and performed on an appropiate software platform.

$\endgroup$
4
  • $\begingroup$ The last proof by induction seems to work only from $n_0=5$, because we need that the $T_n$'s are non-negative. Is there a chance that this approach can be turned into a pen-and-paper proof? $\endgroup$
    – macat
    Apr 9, 2022 at 23:11
  • $\begingroup$ @macat, OK. If the first $T_n>0$ is at $n_0=5$ you have to prove that this rational $[1+\alpha]\,r_1+r_2+r_3>0$ from this value. This is a ratio of two polynomials in $n$. Look for the real roots of the resulting numerator polynomial first and then the real roots of the denominator polynomial. None polynomial should have real roots to the right of $n_0$ and both must have same sign for all $n>n_0$. $\ T_{n+1}>\gamma(n)\cdot T_n$ follows by induction from $n_0$. I do not think there is a pen-and-paper proof. You have to use a computer to get the roots. $\endgroup$ Apr 10, 2022 at 20:48
  • $\begingroup$ @macat checked. The right-most real roots are respectively at $\nu=[1.12596.., 1.11566..]$ for [numerator, denominator] of rational function $[1+\alpha]\,r_1+r_2+r_3$ $\endgroup$ Apr 12, 2022 at 17:52
  • $\begingroup$ This means that $T_{n+1}>γ(n)⋅T_n$ holds for all $n>\max(\nu)+3=4.12596...,$, namely from $n=n_0=5$ and claim is proved. $\endgroup$ Apr 13, 2022 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.