Proof of a discrete Gronwall-type inequality

Question

Let $a_0 \in (0,\infty)$, and for every $n \geq 1$, let $a_n \geq 0$ satisfy, for some $0 < \Delta < \infty$, the inequality $$a_n \leq \frac{\Delta}{n}\,\sum_{j=0}^{n-1} a_j.$$ I am wondering how one can deduce that $$a_n \leq a_0\,\frac{\Gamma(\Delta +n)}{\Gamma(\Delta)\,\Gamma(n+1)}$$ for every $n \geq 1$, in which $\Gamma(\cdot)$ denotes Euler's Gamma function. This result is reported as a lemma in this paper but without proof.

Answer 1

A proof by strong induction on $n$ shows that $$a_n \le a_0\,\frac{\Delta(1 + \Delta)(2+\Delta)\cdots (n-1 + \Delta)}{n!}\label{a}\tag{1}$$ First note the recursive inequality gives $a_1 \le \Delta a_0$. Now assume $k > 1$ and $\ref{a}$ holds for all positive integers $n < k$. By the recursive inequality and the induction hypothesis, $$a_k \le a_0\frac{\Delta}{k}\left[1 + \sum_{j = 1}^{k-1} \frac{\Delta(1 + \Delta)\cdots(j - 1 + \Delta)}{j!}\right]\label{b}\tag{2}$$ Observe $$\frac{\Delta(1 + \Delta)\cdots (j-1 + \Delta)}{j!} = \frac{(1 + \Delta)(2+\Delta) \cdots (j + \Delta)}{j!} - \frac{(1 + \Delta)(2 + \Delta)\cdots (j-1 + \Delta)}{(j-1)!}$$ for $1 \le j \le k-1$. Therefore, the entire sum inside the brackets in \ref{b} telescopes to $$\frac{(1 + \Delta)(2 + \Delta)\cdots (k-1 + \Delta)}{(k-1)!}$$ and we deduce \ref{a} for $n = k$.

The relation $\Gamma(s+1) = s\Gamma(s)$ for $s > 0$ implies $\Gamma(\Delta + n) = (\Delta + n-1)\cdots(\Delta + 2)(\Delta + 1)\Delta\Gamma(\Delta)$ and $\Gamma(n+1) = n!$ (since $\Gamma(1) = 1$). Thus, $\ref{a}$ can be rewritten $$a_n \le a_0\, \frac{\Gamma(\Delta + n)}{\Gamma(\Delta)\Gamma(n+1)}$$ as desired.