On proving a sequence converges by induction. 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?
 A: 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}$.
