So I was trying to prove this inequality $$\limsup \limits_{n \to \infty}\left( \frac{1 + a_{n+1}}{a_n}\right)^n \geq e$$ with $a_n$ any positive sequence. I found a proof in a textbook that I don't quite understand some steps. It goes like this:
Suppose the inequality doesn't hold. Then for some $0 < c < 1$ there is an $n_0$ such that $$\frac{1 + a_{n+1}}{a_n} < 1 + \frac{c}{n}$$ whenever $n \geq n_0$, i.e., $$a_{n+1} < \left( 1 + \frac{c}{n}\right)a_n -1$$ (This is the step I'm struggling with) Consequently, by induction on $k$, $$a_{n_{0}+k} < a_{n_0}\prod_{i=0}^{k-1}\left( 1 + \frac{c}{n_0 + i} \right) – k$$
for $k = 1, 2, 3…,$ and so $$a_{n_0 + k} < a_{n_0}\exp \left( \sum_{i=0}^{k-1}\frac{c}{n_0 + i}\right) -k < a_{n_0}(n_0 + k)^c – k$$
However, for k large enough, $a_{n_0} (n_0 + k)^c – k < 0$. This contradicts the assumption that $a_{n_0 + k}$ is positive, and so our inequality is proved.
Can you guys help me understand what happened between the induction step? I don't get how it was done. Thanks in advance
Best Answer
The step that you'd like clarity on goes like this.
We know from the assume false step that there exists a $c$ and $n_0$ such that $$ a_{n+1} < \left(1 + \frac{c}{n}\right)a_n - 1 \quad \forall n \geq n_0.\tag{1} $$ Now we can perform the inductive step.
Aim: What we want to show that is, for $ k =1,2,...$ $$ a_{n_0+k} < \prod_{i=0}^{k-1}\left(1 + \frac{c}{n_0+i}\right)a_{n_0} - k. $$
Base case: We first treat a base case: consider the case when $k = 1$. This holds true by Equation 1.
Inductive step: Assume the statement holds true for k = m for some arbitrary value $m \in \mathbb{N}$, i.e. $$ a_{n_0+m} < \prod_{i=0}^{m-1}\left(1 + \frac{c}{n_0+i}\right)a_{n_0} - m. $$ Then it suffices to prove the assumption for $ k = m+1 $. Since $m \in \mathbb{N}$ and $n_0 + m - 1 \geq n_0$, it follows that $n_0 + m \geq n_0$, therefore it follows by Equation 1 $$ a_{n_0+(m+1)} = a_{(n_0+m) + 1} < \left(1 + \frac{c}{n_0 + m}\right)a_{n_0+m} - 1. $$ Although, by the inductive assumption, we know that $$ a_{n_0+m} < a_{n_0}\prod_{i=0}^{m-1}\left(1 + \frac{c}{n_0+i}\right) - m, $$ and after inputting this into the above, we find that $$ a_{n_0+(m+1)} = a_{(n_0+m) + 1} < \left(1 + \frac{c}{n_0 + m}\right)a_{n_0}\prod_{i=0}^{m-1}\left(1 + \frac{c}{n_0+i}\right) - m - 1, $$ which after simplifying, reduces to $$ a_{n_0+(m+1)} < a_{n_0}\prod_{i=0}^{m}\left(1 + \frac{c}{n_0+i}\right) - (m + 1). $$ Thus, if the statement holds true for $k = m$, then it also holds true for $k = m+1$. This concludes the inductive proof.