Gronwall's Lemma (Discrete version)

Solution 1:

(ii) basis Show that statement holds for $n=1$ using $u_0 \leq \alpha$. inductive step Assume $$u_j \leq \alpha \cdot \prod_{k=0}^{j-1} (1+w_k) \qquad (j=0,\ldots,n) \tag{1} $$ Then $$\begin{align} u_{n+1} &\leq \alpha+ \sum_{j=0}^{n} w_j \cdot u_j \stackrel{(1)}{\leq} \alpha+\sum_{j=0}^{n} \alpha \cdot w_j \cdot \prod_{k=0}^{j-1} (1+w_k) \\ &= \alpha \cdot \left(1+ \sum_{j=0}^n \prod_{k=0}^{j-1} (1+w_k) \cdot w_j \right) \stackrel{(i),\alpha \geq 0}{\leq} \alpha \cdot \prod_{k=0}^n (1+w_k) \end{align}$$ i.e. $(1)$ holds also for $j=n+1$.

(iii) Hint Note that $1+x \leq e^x$ for all $x \geq 0$.