Skip to main content
edited body
Source Link
Jorge Zuniga
  • 2.8k
  • 1
  • 12
  • 29

To prove that $S_n$ decreases from some $n_0,\,$ ($n_0 = 3$$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

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

To prove that $S_n$ decreases from some $n_0,\,$ ($n_0 = 3$ 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

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=3$). 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.

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

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.

Source Link
Jorge Zuniga
  • 2.8k
  • 1
  • 12
  • 29

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 = 3$ 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=3$). 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.