<s>[INST] Solving a recursive inequality I have the following inequality for $\{x_t\}_{t\geq 0}$ and trying to find an upper bound for $x_t$. Let $c$ be a constant.

$$x_{t+1}\leq c^2\left[x_t+\frac{2t-3}{4}-\frac{tc^t}{2}+\frac{3c^{2t}}{4}\right]+\frac{1}{4}\tag{1}$$

My attempt: If we had an equality instead of inequality in $(1)$, I would have used generating function of $x_t$ to solve for $x_t$ but for an inequality I don't think I can use generating functions (?). So I tried to think of $x(t)$ as a continuous function of $t$ and $(1)$ being a finite difference approximation. Then:
\begin{align*}
x_{t+1}-x_t &\leq (c^2-1)x_t+c^2\left[\frac{2t-3}{4}-\frac{tc^t}{2}+\frac{3c^{2t}}{4}\right]+\frac{1}{4} \\ \\
x_{t+1}-x_t - (c^2-1)x_t &\leq c^2\left[\frac{2t-3}{4}-\frac{tc^t}{2}+\frac{3c^{2t}}{4}\right]+\frac{1}{4} \\ \\
\frac{dx}{dt}-(c^2-1)x &\leq c^2\left[\frac{2t-3}{4}-\frac{tc^t}{2}+\frac{3c^{2t}}{4}\right]+\frac{1}{4} \\ \\
\frac{d}{dt}\left( e^{-(c^2-1)t}x\right) &\leq e^{-(c^2-1)t}c^2\left[\frac{2t-3}{4}-\frac{tc^t}{2}+\frac{3c^{2t}}{4}\right]+\frac{1}{4} \\ \\
\end{align*}
and then integrate to find an upper bound on $x=x(t)$ but I'd think this is an approximation for an actual upper bound for $x_t$ and am not sure how to solve $(1)$ with or without using what I did above.
 [/INST] Following the hint in the comments, write $y_t = \frac{x_t}{c^{2t}}$. Then if we divide both sides of your inequality by $c^{2t+2}$ we find
$$
y_{t+1} \leq y_t + \frac{2t - 3}{4}c^{-2t} - \frac{t}{2} c^{-t} + \frac{3}{4} + \frac{1}{4}c^{-2t-2}.
$$
We can clean this up a bit more if we set $u_t = 4 y_t$, and multiply everything in sight by $4$. If we also write $\Delta u$ for the forward difference, we get
$$
(\Delta u)_t = u_{t+1} - u_t \leq (2t-3)c^{-2t} - 2tc^{-t} + 3 + c^{-2t-2}.
$$
Now we use the fundamental theorem of finite calculus. Everything on the right hand side of the inequality is summable in $t$, but if we sum the left hand side we get something that telescopes. Precisely, if we sum $t$ from $0$ to $n-1$ we get (using sage):
$$
\frac{4 x_n}{c^{2n}} = 
u_n \leq 
\frac{3 \, c^{4} - {\left(3 \, c^{4} - 5 \, c^{2}\right)} c^{2 n} - 5 \, c^{2} - 2 \, {\left(c^{4} - c^{2}\right)} n}{{\left(c^{4} - 2 \, c^{2} + 1\right)} c^{2 n}}
-2 \left ( 
- \frac{{{\left(c^{2} - c\right)} n + c - c^{n + 1}}}{{\left(c^{2} - 2 \, c + 1\right)} c^{n}}
\right )
+ 3n
+ \frac{c^{2 n} - 1}{{\left(c^{2} - 1\right)} c^{2 n}}.
$$
In the interest of not making silly mistakes I haven't done any simplification here -- these $4$ terms are what you get when you ask sage to sum each of the $4$ terms from the previous expression. You can tell this can be condensed by a fair bit, and it's also worth noting that if $|c| < 1$ a lot of these terms become small, or can be bounded by limits. I'll leave these simplifications and considerations to you, though.

I hope this helps ^_^
</s>