Estimate convergence rate for recurrences $a_{k} \le \frac{k}{k+2} a_{k-1}$ and $b_{k} \le \frac{k+\alpha}{k+2} b_{k-1}$

Question

Suppose a positive sequence satisfies the recurrence $$a_k \le \frac{k}{k+2} a_{k-1}$$ for $k \ge 2$. If we do the expansion, then \begin{align*} a_k \le \frac{k}{k+2} a_{k-1} \le \dots \le \frac{6}{(k+2)(k+1)} a_1 \in \mathcal O(\frac{1}{k^2}). \end{align*} Now suppose $$b_k \le \left( \frac{k}{k+2} + \frac{\alpha}{k+2} \right) b_{k-1}$$ where $\alpha$ is some positive number. I would expect $b_k$ reduces at a slower rate. Let us take $\alpha = \frac{1}{2}$. Mathematica gives a solution \begin{align*} \frac{ \Gamma(1+2k)} {\Gamma(4+2k)}= \frac{1}{4(k+1)(k+2)(3+2k)}. \end{align*} This seems to be a better asymptotes. Where does it go wrong? $b_k$ should not reduce faster than $a_k$.

Answer 1

I agree with the first part: \begin{align} a_k &\leq \frac{k}{k+2}a_{k-1}\\ &\leq \frac{2}{4\!\!\!\times}\frac{3}{5\!\!\!\times}\frac{4\!\!\!\times}{6\!\!\!\times}\frac{5\!\!\!\times}{7\!\!\!\times} \dotsb \frac{k-2}{k}\frac{k-1}{k+1} \frac{k}{k+2}a_1\\ &= \frac{6}{(k+1)(k+2)}a_1 \in O\left(\tfrac{1}{k^2}\right) \end{align}

But I don't agree with your Mathematica result. \begin{align} b_k &\leq \left(\frac{k}{k+2} + \frac{a}{k+2}\right) b_{k-1} = \left(\prod_{i=0}^{k-2} \frac{k+a-i}{k+2-i}\right) b_1 = \dfrac{\prod_{i=2}^{k} (i+a)}{\prod_{i=4}^{k+2}i} b_1\\ &= \frac{\Gamma(k+a+1)\,/\,\Gamma(a+2)}{\Gamma(k+3)\,/\,\Gamma(4)} b_1 = \frac{6}{\Gamma(a+2)}\frac{\Gamma(k+a+3)}{(k+a+2)(k+a+1)\Gamma(k+3)} b_1 \end{align}

A useful asymptotic approximation, for $\alpha\in\mathbb{C}$ $$\lim_{n\to\infty}\frac{\Gamma(n+\alpha)}{\Gamma(n)\,n^{\alpha}}=1$$ then \begin{align} b_k &\leq \frac{6}{\Gamma(a+2)}\frac{(k+3)^a}{(k+a+2)(k+a+1)}\frac{\Gamma(k+a+3)}{(k+3)^a\Gamma(k+3)}b_1\\ &\sim \frac{6 b_1}{\Gamma(a+2)} \frac{(k+3)^a}{(k+a+1)(k+a+2)} \in O\left(\tfrac{1}{k^{2-a}}\right) \end{align}

As long as I haven't messed up somewhere this should give $O\left(\tfrac{1}{n^{1.5}}\right)$ for $a=\tfrac12$.