On proving a sequence converges by induction.

Question

I would like to prove by induction that given a sequence of positive real numbers $\{x_k \}_{k \in \mathbb{N}}$ such that $$x_{k+1} \le \left(1 - \frac{2c \ell}{k} + \left(\frac{c}{k} \right)^2 M_1 L^2 \right) x_{k} + \frac{c^2}{k^2} M $$ where $0<c < \max\{ 1/ \sqrt{M_1} L, 2 \ell / M_1 L^2 \}$ and $\ell,M_1, L, M > 0$, then $$ x_{k+1} \le v/ (k+1) $$ where $v := \max \{x_1, c^2 M / (2\ell c -2) \}$.

My attempt:

the base case $x_{1} \le v$ is obviously verified, for the inductive step we obtain \begin{align*} & x_{k+1} \le \left(1 - \frac{2c \ell}{k} + \left(\frac{c}{k} \right)^2 M_1 L^2 \right) \frac{v}{k} + \frac{c^2}{k^2} M = \\ & \left( \frac{k^2 -2k + c^2 M_1 L^2}{k^3} \right)v - \frac{(2 c \ell -2)v}{k^2} + \frac{c^2M}{k^2} \end{align*} at this point we use the fact that $k^3 \ge (k^2-2k +1 ) ( k+1) $ for all $k> 1$ in conjunction with the definition of $c$ that gives
\begin{align*} k^2 -2k + c^2 M_1 L^2 \le k^2 -2k + 1, \quad 0<\left(1 - \frac{2c \ell}{k} + \left(\frac{c}{k} \right)^2 M_1 L^2 \right)< 1 \end{align*} while from the definition of $v$ \begin{align*} - \frac{(2 c \ell -2)v}{k^2} + \frac{c^2M}{k^2} \le 0 \end{align*} and utilizing these four inequalities we obtain \begin{align*} x_{k+1} \le \frac{v}{k+1} \end{align*} this should conclude the proof even if I am a bit unsure where inequality $0<\left(1 - \frac{2c \ell}{k} + \left(\frac{c}{k} \right)^2 M_1 L^2 \right)< 1 $ is being utilized, I suspect the bound $c < 2 \ell / M_1 L^2$ is not needed. Does this work?

Answer 1

This part of the answer is preliminary and is intended to show the problems with the proposed approach.

Put $A= M_1L^2$ and $D=\ell^2-A$. Assume that $M\ge 0$ and $D\le 0$. It follows that $P(k)=1 - \frac{2c \ell}{k} + \left(\frac{c}{k} \right)^2 A\ge 0$ for each $k$.

In the appoach from the question in order to cancel the term $\frac {c^2M}{k^2}$ we need $c\ell>1$, which fails for small $c$. And it seems that anyway we need $2c\ell>1$ to cancel the term of order $O(k)$. Let’s see this.

Consider the induction step of a proof of a bound $x_k\le \frac {u}{k-1}$ for $k\ge 2$ (it is essentially the same as the proposed, but leads to more simple calculations). Since $P(k)\ge 0$, $P(k)x_k\le P(k)\frac u{k-1}$. We are going to show that

$\frac uk\ge \left(1 - \frac{2c \ell}{k} + \left(\frac{c}{k} \right)^2 A\right)\frac u{k-1} + \frac{c^2}{k^2} M$

$uk(k-1)\ge \left(k^2 - 2c \ell k + c^2 A\right) u + c^2(k-1) M$

$u(2c\ell-1) k\ge c^2 Au + c^2(k-1) M$.

Comparing terms of order $O(k)$ we see that we need $2c\ell-1>0$ and $u\ge \frac{c^2M}{2c\ell-1}$. Moreover, the latter inequality usually should be strict because if we put $u=\frac{c^2M}{2c\ell-1}$ then the induction step inequality will cancel to

$0 \ge c^2 A\frac{c^2M}{2c\ell-1} - c^2M$.

$ c^2M\ge c^2 A\frac{c^2M}{2c\ell-1}$.

$1\ge c^2 A\frac{1}{2c\ell-1}$.

$0\ge 1-2c\ell+c^2 A$

$0\ge P(1)$

But we have $P(1)\ge 0$.

PS. But a condition $D\le 0$ is not crucial for the convergence of the sequence $\{x_k\}$ to $0$. If $P(k)<0$ then $x_{k+1}\le \frac {c^2}{k^2}M$, which should converge to zero even faster than $\frac v{k}$. But since when $k$ tends to infinity, $P(k)$ tends to $1$, we have $P(k)>0$ for sufficiently large $k$. Then similarly to the above arguments we can show that if $P(1)\le 0$ then there exists $u$ such that $x_{k}\le\frac u{k-1}$ for all sufficiently large $k$.

PPS. If $c\ell>0$ then the sequence $\{x_k\}$ converges to $0$. To show this pick any number $0<r<\min\{2c\ell,1\}$. Then there exists $K$ such that $P(k)\le Q(k)=1-\frac rk$ for each $k\ge K$. Consider an auxiliary sequence $\{y_k\}$, where $y_k= x_k+\frac {B}{k-1}$ for each $k\ge 2$ and $B=\frac{c^2M}{1-r}$. We claim that $y_{k+1}\le Q(k)y_k$ for each $k\ge K$. Indeed, we have

$y_{k+1}=x_{k+1}+\frac {B}{k}\le Q(k)x_k+\frac{c^2}{k^2}M+\frac {B}{k}= Q(k)\left(y_k-\frac{B}{k-1}\right) +\frac{c^2}{k^2}M+\frac {B}{k}$.

So it suffices to check that

$0\ge -Q(k)\frac{B}{k-1} +\frac{c^2}{k^2}M+\frac {B}{k}$

$0\ge –(k^2-rk)B +c^2(k-1)M+Bk(k-1)$

$0\ge rkB +c^2(k-1)M-Bk$

$k(B(1-r)-c^2M) \ge -c^2M$.

The last inequality holds by the choice of $B$.

Thus for each $k\ge K$ we have $y_{k+1}\le y_K\prod_{i=K}^k Q(i)$.

Pick any natural $R\ge\frac 1r$. Than for each $k=Rm$ we have

$$\prod_{i=1}^k Q(i)=\prod_{i=1}^{Rm} \left(1-\frac{r}{i}\right)\le \prod_{i=1}^{Rm} \left(1-\frac{1}{iR}\right)\le \prod_{j=1}^{m} \left(1-\frac{1}{jR}\right)^R\le \prod_{j=1}^{m} \frac j{j+1}=\frac 1{m+1}.$$

Thus the sequence $\{y_k\}$ converges to $0$, and so does $\{x_k\}$.

Remark that an inequality $\left(1-\frac{1}{jR}\right)^R\le \frac j{j+1} $ for each $j$ follows from Bernoulli's inequality. Indeed, by Bernoulli's inequality, $\left(1+\frac{1}{jR}\right)^R\ge 1+\frac 1j=\frac{j+1}j$. On the other hand, $\left(1+\frac{1}{jR}\right)^R\left(1-\frac{1}{jR}\right)^R=\left(1-\frac{1}{j^2R^2}\right)^R\le 1$. So $\left(1-\frac{1}{jR}\right)^R\le \frac j{j+1}$.