36  Inequalities

Author
Affiliation

Aditya Mahajan

McGill University

Updated

June 17, 2025

36.1 Discrete Grönwall Inequality

Proposition 36.1 Let \(\{a_n\}_{n \ge 0}\), \(\{b_n\}_{n \ge 0}\), \(\{u_n\}_{n \ge 0}\) be real-valued sequences that satisfy \[\begin{equation}\label{eq:gronwall-recursion} u_{n+1} \le (1 + a_n)u_n + b_n. \end{equation}\] Define \(Φ_n = \prod_{k=0}^{n-1}(1 + a_k)\). Then, \[\begin{equation}\label{eq:gronwall} u_n \le Φ_n \biggl( u_0 + \sum_{k=0}^{n-1} \frac{b_k}{Φ_{k+1}} \biggr). \end{equation}\]

Now we prove the result by induction. At \(n=1\), the RHS of \(\eqref{eq:gronwall}\) is \[ (1 + a_0)\biggl(u_0 + \frac{b_0}{1+a_0}\biggr) = (1 + a_0) u_0 + b_0 = u_0. \] This forms the basis of induction. Now assume that \(\eqref{eq:gronwall}\) is true for \(n\) and consider \(n+1\). \[\begin{align*} u_{n+1} &\le (1 + a_n)u_n + b_n \\ &\le (1 + a_n) Φ_n \biggl( u_0 + \sum_{k=0}^{n-1} \frac{b_k}{Φ_{k+1}} \biggr) + b_n \\ &= Φ_{n+1}\biggl( u_0 + \sum_{k=0}^{n-1} \frac{b_k}{Φ_{k+1}} \biggr) + Φ_{n+1} \frac{b_n}{Φ_{n+1}} \\ &= Φ_{n+1}\biggl( u_0 + \sum_{k=0}^{n} \frac{b_k}{Φ_{k+1}} \biggr) \end{align*}\] which proves the result.

Some remarks

For ease of notation, let \(A_n = \sum_{k=0}^{n-1} a_k\) and \(B_n = \sum_{k=0}^{n-1} b_n\).

  1. In Proposition 36.1, no assumption is imposed on the sign of the sequences. Note that if \(1 + a_n \ge 0\), we can use the inequality \((1 + a_n) \le \exp(a_n)\) to bound \(Φ_n \le \exp(A_n)\).

    If we further assume that \(u_0 \ge 0\), \(a_k \ge 0\), and \(b_k \ge 0\), then \(Φ_{k+1} \ge 1\). So, a cruder upper bound on the right hand side of \(\eqref{eq:gronwall}\) is \[ u_n \le Φ_n (u_0 + B_n) \le (u_0 + B_n) \exp(A_n) \]

  2. Suppose the sequences \(\{a_n\}_{n \ge 1}\) and \(\{b_n\}_{n \ge 1}\) are non-negative and summable, i.e., \(\lim_{n \to ∞} A_n < ∞\) and \(\lim_{n \to ∞} B_n\). Then, \(Φ_n\) is an increasing sequence, and from Exercise 42.1, we get that \(\lim_{n \to ∞} Φ_n < ∞\). Let \(A_{∞}\), \(B_{∞}\), and \(Φ_{∞}\) denote upper bounds on \(\{A_n\}_{n \ge 0}\), \(\{B_n\}_{n \ge 0}\), and \(\{Φ_n\}_{n \ge 0}\). Then, we get that \[ u_n \le Φ_{∞}(u_0 + B_{∞}) \le (u_0 + B_{∞})\exp(A_{∞}). \] Thus, the sequence \(\{u_n\}_{n \ge 0}\) is bounded. See Theorem 42.2 for a generalization of this facts to stochastic sequences.

  3. If we expand out the recursive form of iteration of \(\{u_n\}_{n \ge 0}\), we get \[ u_n \le \biggl[ u_0 + \sum_{k=0}^{n-1} b_k \biggr] + \sum_{k=0}^{n-1} a_k u_k \]

  4. Combing the above, the discrete Grönwall inequality is often stated as follows (with different variables). Let \(\{a_n\}_{n \ge 0}\), \(\{c_n\}_{n \ge 0}\), and \(\{u_n\}_{n \ge 0}\), be real-valued sequences, where \(a_n \ge 0\) and \[ u_{n+1} \le c_n + \sum_{k=0}^{n-1} a_k u_k \] Then, \[ u_n \le c_n Φ_n \le c_n \exp(A_n). \]

    See Clark (1987) for a tighter version of the above bound.