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.
Proof of a discrete Gronwall-type inequality
discrete mathematicsinductioninequalityrecurrence-relations
Related Solutions
Well, since no one gave a complete answer yet--and because I wrote one anyway--here's the proof by induction, in a manner which is hopefully easy for students (without much proof experience) to understand. Credit goes to the Wu and Wu paper posted by @Jeff.
Both sides of the Schwarz inequality are real numbers $\geq 0$. If $\sum_{j=1}^n |a_j|^2 \sum_{j=1}^n |b_j|^2 = 0$, then it must be that $a_1 = a_2 = \ldots = a_n = 0$ and/or $b_1 = b_2 = \ldots = b_n = 0$, so clearly $|\sum_{j=1}^n a_j \overline{b_j}|^2$ also $= 0$ and we are done. Now we only need to prove the case in which both sides of the inequality are positive.
Base Case. For $n = 1$, we have $$|\sum_{j=1}^1 a_j \overline{b_j}|^2 = |a_j \overline{b_j}|^2 = |a_j|^2 |b_j|^2 = \sum_{j=1}^1 |a_j|^2 \sum_{j=1}^1 |b_j|^2.$$
Inductive Step. The inductive hypothesis is $|\sum_{j=1}^{n-1} a_j \overline{b_j}|^2 \leq \sum_{j=1}^{n-1} |a_j|^2 \sum_{j=1}^{n-1} |b_j|^2$. Since we only need to worry about the case in which both sides are positive, so we can take the square root to obtain $$|\sum_{j=1}^{n-1} a_j \overline{b_j}| \leq \sqrt{\sum_{j=1}^{n-1} |a_j|^2 \sum_{j=1}^{n-1} |b_j|^2}.$$
Thus $|\sum_{j=1}^n a_j \overline{b_j}|$
$= |\sum_{j=1}^{n-1} a_j \overline{b_j} + a_n \overline{b_n}|$
$\leq |\sum_{j=1}^{n-1} a_j \overline{b_j}| + |a_n \overline{b_n}|$ (by the triangle inequality)
$\leq \sqrt{\sum_{j=1}^{n-1} |a_j|^2 \sum_{j=1}^{n-1} |b_j|^2} + |a_n \overline{b_n}|$ (by the inductive hypothesis)
$= \sqrt{\sum_{j=1}^{n-1} |a_j|^2} \sqrt{\sum_{j=1}^{n-1} |b_j|^2} + |a_n| |b_n|.$
Here we're a little stuck. We want to be able to square $|a_n|$ and $|b_n|$ and bring them into their respective square-rooted sums. So if we label $a = \sqrt{\sum_{j=1}^{n-1} |a_j|^2}$, $b = \sqrt{\sum_{j=1}^{n-1} |b_j|^2}$, $c = |a_n|$, and $d = |b_n|$, we want to be able to say $ab + cd \leq \sqrt{a^2 + c^2} \sqrt{b^2 + d^2}$. In fact, we can say it! This inequality is always true for any $a, b, c, d \in \mathbb{R}$, because
$0 \leq (ad - bc)^2 = a^2 d^2 - 2abcd + b^2 c^2$
$\Rightarrow 2abcd \leq a^2 d^2 + b^2 c^2$
$\Rightarrow a^2 b^2 + 2abcd + c^2 d^2 \leq a^2 b^2 + a^2 d^2 + b^2 c^2 + c^2 d^2$
$\Rightarrow (ab + cd)^2 \leq (a^2 + c^2)(b^2 + d^2),$
and since both sides are positive reals, we can take the square root.
We now use this inequality to obtain
$|\sum_{j=1}^n a_j \overline{b_j}| \leq \sqrt{\sum_{j=1}^{n-1} |a_j|^2} \sqrt{\sum_{j=1}^{n-1} |b_j|^2} + |a_n| |b_n|$
$\leq \sqrt{\sum_{j=1}^{n-1} |a_j|^2 + |a_n|^2} \sqrt{\sum_{j=1}^{n-1} |b_j|^2 + |b_n|^2}$
$= \sqrt{\sum_{j=1}^n |a_j|^2 \sum_{j=1}^n |b_j|^2},$
and just square both sides to complete the inductive step.
I’m grateful for all efforts people made to solve my problem. With the help of my teacher, I finally find a solution. And it turns out that there is some thing wrong in the original problem.
Let $0=x_0<x_1<\cdots<x_n=T$ be such that $\|f\|_{L^\rho(x_{k-1},x_k)}=1/2$ for each $1\leq k\leq n-1$ and $\|f\|_{L^\rho(x_{n-1},x_n)}\leq1/2$. A simple calculation gives that $\|f\|_{L^\rho(0,x_k)}=\frac{k^{1/\rho}}2$ for $1\leq k\leq n-1$.
Next we do the iteration. By Minkowski's inequality and Hölder's inequality \begin{align*} \|\varphi\|_{L^\gamma(0,x_{k+1})}&\leq\eta+\|f\varphi\|_{L^\beta(0,x_{k+1})}\\ &\leq\eta+\|f\varphi\|_{L^\beta(0,x_{k})}+\|f\varphi\|_{L^\beta(x_k,x_{k+1})}\\ &\leq\eta+\|f\|_{L^\rho(0,x_k)}\|\varphi\|_{L^\gamma(0,x_k)}+\|f\|_{L^\rho(x_k,x_{k+1})}\|\varphi\|_{L^\gamma(x_k,x_{k+1})}\\ &\leq\eta+\frac{k^{1/\rho}}2\|\varphi\|_{L^\gamma(0,x_k)}+\frac12\|\varphi\|_{L^\gamma(x_k,x_{k+1})}\\ &\leq\eta+\frac{k^{1/\rho}}2\|\varphi\|_{L^\gamma(0,x_k)}+\frac12\|\varphi\|_{L^\gamma(0,x_{k+1})}. \end{align*} Note that $1\leq \rho<\infty$, we thus have $$\|\varphi\|_{L^\gamma(0,x_{k+1})}\leq 2\eta+k^{1/\rho}\|\varphi\|_{L^\gamma(0,x_k)}\leq 2\eta+k\|\varphi\|_{L^\gamma(0,x_k)}.$$ By induction we can easily deduce that $$\|\varphi\|_{L^\gamma(0,x_k)}\leq 2\eta (k+1)!$$
Fix $t\in(0,T)$, then there is some $1\leq k\leq n$ such that $t\in [x_{k-1},x_k)$, so \begin{align*} \|\varphi\|_{L^\gamma(0,t)}&\leq 2\eta (k+1)!\\ &=2\eta \Gamma(k+2)\\ &=2\eta \Gamma\left(3+\frac{k-1}2\cdot2\right). \end{align*} Since $\|f\|_{L^\rho(0,t)}\geq \|f\|_{L^\rho(0,x_{k-1})}=\frac{(k-1)^{1/\rho}}2$, we conclude that \begin{align*} \|\varphi\|_{L^\gamma(0,t)}&\leq 2\eta\Gamma\left(3+2(2\|f\|_{L^\rho(0,t)})^\rho\right)\\ &\leq\eta\Phi\left(2^\rho\|f\|_{L^\rho(0,t)}^\rho\right). \end{align*}
Best Answer
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.