The below is a simplification of part of a proof I'm working on, in numerical analysis. It is similar to a paper that I studied some months ago, for which I got [some advice here on MathOverflow](https://mathoverflow.net/questions/292107/resolving-an-inequality-in-the-final-step-of-derivation-of-an-a-priori-energy).


I have non-negative sequences $A\_k, B\_k, C\_k$ for $k=0\dots n$, a time-step $\Delta{t}$ and a positive number $p$ such that
$$(1+p\Delta{t})A\_n + B\_n \le A\_{n-1} + B\_{n-1} + C\_n\Delta{t} \tag{$\star$}$$ and **I would like to claim** that the final solution with the unknowns $A\_n$ and $B\_n$ is bounded by their initial solution plus a finite quantity containing the maximum value of the known quantity $C\_n$ i.e. there exists a bound of the form
$$A\_n + B\_n \le f(\Delta t) A\_0 + g(\Delta t)B\_0 + h(\Delta t)\max\_{0 \le k \le n}C\_k \tag{$\star\star$}$$
where I need to find the forms $f(\cdot)$, $g(\cdot)$ and $h(\cdot)$. 


**What I have tried:**


* I *removed* the non-negative $B\_n$ on the left side of ($\star$) and got $$(1+p\Delta{t})A\_n \le A\_{n-1} + B\_{n-1} + C\_n\Delta{t} \tag{1}$$
* Proceeding in a similar way to the linked answer, I multiplied through by $(1+p\Delta t)^{n-1}$ and set $E\_n = (1+p\Delta t)^nA\_n$ to get
$$E\_n \le E\_{n-1} + B\_{n-1}(1+p\Delta t)^{n-1} + C\_n(1+p\Delta t)^{n-1}\Delta{t} \tag{2}$$
* Applying recursion,
$$E\_n \le E\_0 + \max\_{0\le k \le n-1} B\_k \sum\_{k=0}^{n-1}(1+p\Delta t)^k + \max\_{0\le k \le n} C\_k \Delta{t}\sum\_{k=0}^{n-1}(1+p\Delta t)^k \tag{3}$$
* Now I divided by $(1+p\Delta t)^n$, and applied $A\_0 = E\_0$
$$A\_n \le \frac{A\_0}{(1+p\Delta t)^n} + \left(\max\_{0\le k \le n-1}B\_k + \max\_{0\le k \le n}C\_k\Delta{t}\right)\frac{1}{(1+p\Delta t)^n}\sum\_{k=0}^{n-1}(1+p\Delta t)^k \tag{4}$$
* Simplifying and bounding the below by a geometric sum to infinity, we have
$$\frac{1}{(1+p\Delta t)^n}\sum\_{k=0}^{n-1}(1+p\Delta t)^k = \sum\_{k=1}^{n}\frac{1}{(1+p\Delta t)^k} < \frac{1}{p\Delta t} \tag{5}$$
* Using (5) in (4) gives
$$A\_n \le \frac{A\_0}{(1+p\Delta t)^n} + \frac{1}{p\Delta t}\max\_{0\le k \le n-1}B\_k + \frac{1}{p}\max\_{0\le k \le n}C\_k \tag{6}$$
and the problems with this approach are


(a) There is no $B\_n$ term on the left since I discarded it, and (b) the $B\_{k-1}$ term on the right is an unknown. Only $B\_0$ can provide a useful bound here.


I think if I don't discard $B\_n$ in step 1, I might find a way to use recursion and end up with $B\_n$ on the left and $B\_0$ on the right. I have thought about summing from $0$ to $N$ but it's unclear how to proceed. Any suggestions on how to proceed will be very much appreciated.




---


I eventually figured it out (see answer below), but I am not certain because @losif's answer also seems irrefutable.



How to estimate a recursive inequality with an upper bound
$\newcommand{\de}{\delta}$


The bound ($\star\star$) that you want is impossible in general. E.g., take $A\_n=0$, $C\_n=1$, $B\_n=n\Delta t$ for all $n$, with $\Delta t>0$. Then ($\star$) will hold, whereas ($\star\star$) will not hold for large enough $n$, for any choice of $f,g,h$. 


**Added:** The bound ($\star\star$) will hold with $f=g=1$ and $h=b:=\frac{K+1}p$ if we additionally assume that $A\_n$ dominates $B\_n$ in the sense that $B\_n\le KA\_n$ for some real $K>0$ and all $n$. Indeed, let $\de:=\Delta t$, $S\_n:=A\_n+B\_n$, and $M\_n:=\max\_{0\le k \le n}C\_k$. Then, with such $f,g,h$, ($\star\star$) can be rewritten as 
\begin{equation}
 S\_n\le S\_0+bM\_n. \tag{!!}
\end{equation}
On the other hand, the condition $B\_n\le KA\_n$ can be rewritten as $(1+p\de)A\_n + B\_n\ge(1+\de/b)S\_n$; so, ($\star$) yields 
\begin{equation}
 (1+\de/b)S\_n\le S\_{n-1}+C\_n\de. 
\end{equation}
Now it is easy to to prove (!!) by induction. Indeed, for $n=0$ (!!) is trivial. Assuming (!!) holds with $n-1$ in place of $n$, we have 
\begin{multline}
 (1+\de/b)S\_n\le S\_{n-1}+C\_n\de\le S\_0+bM\_{n-1}+C\_n\de
 \le(1+\de/b)S\_0+(b+\de)M\_n \\ 
 =(1+\de/b)(S\_0+bM\_n),
\end{multline}
so that (!!) indeed follows. 


