# How to estimate a recursive inequality with an upper bound

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.

• Consider setting Dn = An + Bn, and see what you can say about the sequence D. Gerhard "Fewer Variables Make Things Simpler" Paseman, 2018.09.13. Sep 14, 2018 at 4:26
• Thank you, I considered that but I hit a snag because of the $p\Delta{t}$ term that exists on the left for $A_n$ but not $B_n$. Any ideas how to approach this? I apologize if I am missing something obvious - I am a self-learner without extensive background in the field. Sep 14, 2018 at 11:54
• P.S. I would like to not use an exponential bound such as Gronwall's lemma, if possible, for stability reasons. It is also possible that this can't be proved this way, and I need to start over. But I want to be sure I am not missing something. Sep 14, 2018 at 12:04

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

• Thank you. I guess I need to start all over again, then! Sep 14, 2018 at 14:13
• The bound you want will hold if $A_n$ dominates $B_n$ -- I have added details on this. Sep 14, 2018 at 15:21
• Hello again @losif, I think I proved this eventually - could you please help me take a look? Sep 24, 2018 at 17:52

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.

• Yes, with the sum instead of the max and, therefore, with the extra factor $n$ before the max, there is no problem; the problem was only with the max per se. Sep 24, 2018 at 21:36