Suppose we have the following first-order non-homogeneous recurrence relation $$z_{t+1} \leq \frac{1}{(1+b_1c_t)^2}\left[\left(1+b_2c_t^2 \right)z_t + b_3c_t^2\right] $$
where $t$ is an integer which varies from 0 to $T$, and $b_1$, $b_2$ and $b_3$ are constants which are greater than 0. In the above equation $z_t = \|w_{t+1} - w^{\star}\|$ i.e. above equation shows a relation about how fast is $w_t$ decreasing and will reach to $w^{\star}$. I am trying that the I wanted to solve for $z_T$ such that convergence of $w$ to $w^{\star}$ is $O\left(\frac{1}{T}\right)$ which can be also written as- $$z_T \leq \frac{d}{T}z_0 + e $$ where $d$ and $e$ are some constants. Is there a way to bound $c_t, b_1, b_2$ and $b_3$ such that the above equation becomes true? I am not sure how to solve the above equation, any pointers would be really helpful.
The answer is positive. Given $b_i$, for simplicity put $c_t=\tfrac 1{b_1t}$ for each $t>0$. Pick any $t\ge\tfrac{2b_2}{b_1^2}$ and any $A\ge \frac{2b_3}{b_1^2}$ such that $z_t\le\tfrac At$. Now it suffices to show that $z_{t+1}\le\tfrac A{t+1}$ and then conclude by induction. It remains to check that $$\frac A{t+1}\ge \frac 1{\left(1+\tfrac 1t\right)^2}\left(\left(1+\frac {b_2}{b_1^2t^2}\right)\frac At+\frac {b_3}{b_1^2t^2}\right)$$ $$\frac A{t+1}\ge \frac 1{t(1+t)^2}\left(At^2+\frac {b_2A}{b_1^2}+\frac{b_3}{b_1^2}t\right)$$
$$At(t+1)\ge At^2+\frac {b_2A}{b_1^2}+\frac{b_3}{b_1^2}t$$
$$At\ge \frac t2A+\frac A2t \ge \frac {b_2}{b_1^2}A+\frac{b_3}{b_1^2}t,$$
which holds by our choice of $t$ and $A$.