Return to 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

$$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}}\right]+O\left(\frac{1}{n^2}\right)$$ where $c_1=.5922905035e-6,\ c_2=.1110443475,\ c_3=.2493491970e-2$ are given numerically.

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

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

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

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

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

$$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}}\right]+O\left(\frac{1}{n^2}\right)$$ where $c_1=.5922905035e-6,\ c_2=.1110443475,\ c_3=.2493491970e-2$ are given numerically.

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

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

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

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

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