How to estimate a recursive inequality with an upper bound

Question

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.

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.

Answer 1

$\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.

Answer 2

Here is what I eventually did. In light of @losif's answer which I already accepted, can you please tell me what is wrong with my reasoning below? Given ($\star$), we have $$(1+pΔt)A_1+B_1 ≤ A_0 + B_0 + C_1\Delta{t} \tag{1}$$ and $$(1+pΔt)A_2+B_2 ≤ A_1 + B_1 + C_2\Delta{t} \tag{2}$$ Adding a non-negative $p\Delta{t}A_1$ to the right side of (2), we get $$(1+pΔt)A_2+B_2 ≤ (1+p\Delta{t})A_1 + B_1 + C_2\Delta{t} \tag{3}$$ and substituting (1) gives $$(1+pΔt)A_2+B_2 ≤ A_0 + B_0 + C_1\Delta{t} + C_2\Delta{t} \tag{4}$$ Continuing in this way, we will obtain $$(1+pΔt)A_n+B_n ≤ A_0 + B_0 + \sum_{k=1}^{n} C_k\Delta{t} \tag{5}$$ i.e. $$A_n + \frac{1}{1+p\Delta{t}}B_n \le \frac{1}{1+p\Delta{t}}\left(A_0 + B_0 + n\Delta{t}\max_{1\le k \le n}C_k \right)$$ which means that $$\min\left\{1,\frac{1}{1+p\Delta{t}}\right\}(A_n + B_n) \le \frac{1}{1+p\Delta{t}}\left(A_0 + B_0 + n\Delta{t}\max_{1\le k \le n}C_k \right)$$ and noting that $1 > \frac{1}{1+p\Delta{t}}$ for all $p > 0$ and $\Delta{t} >0$ leaves $$\frac{1}{1+p\Delta{t}}(A_n + B_n) \le \frac{1}{1+p\Delta{t}}\left(A_0 + B_0 + n\Delta{t}\max_{1\le k \le n}C_k \right)$$ i.e. $$ A_n + B_n \le A_0 + B_0 + n\Delta{t}\max_{1\le k \le n}C_k $$ which I set out to prove (except that the index of the max on the right, runs from 1, not 0), and this is okay in my case.