<s>[INST] How can I prove this sharp upper bound? Here :
What are sharp lower and upper bounds of the fast growing hierarachy?
Deedlit mentions that for natural $m,n\ge 2$ and natural $k>n+log_2(n)$ , we have $$2\uparrow^{m-1}n<f_m(n)<2\uparrow^{m-1} k$$
The left inequality can be proven by induction. But what about the right inequality ? How can I bound $2\uparrow^{m-1} k$ in a way that induction can be applied ? Or do I need another idea ?
 [/INST] So we will prove that for $m \ge 2, n \ge 3$, $f_m(n) \le 2\uparrow^{m-1}\lceil n + \log_2(n) + 1\rceil$.
Base case $m=2$: $f_2(n) = n 2^n = 2^{n+\log_2(n)} \le 2 \uparrow \lceil n + \log_2(n) + 1\rceil$.
Inductive step: 
We assume that $f_m(n) \le 2\uparrow^{m-1}\lceil n + \log_2(n) + 1 \rceil \le 2 \uparrow^{m-1}(2n)$.
Lemma.  For $m,n \ge 1$, $2\uparrow^m (n+2) > 2(2\uparrow^m n) + 2$.
Proof of Lemma: $2\uparrow^m(n+2) = 2 \uparrow^{m-1} (2 \uparrow^{m-1} (2\uparrow^m n)) \ge 2 \uparrow^0 (2\uparrow^0 (2\uparrow^m n)) = 4(2\uparrow^m n) > 2(2\uparrow^m n) + 2$ QED
Let $g(n) = 2 \uparrow^{m-1} n$ and $h(n) = 2 \cdot 2\uparrow^{m-1}(n)$.  Then the Lemma is equivalent to $g(n+2) > h(n)+2$.
Lemma 2. $f_m^i(n) < h^i(2n)) < g^i(2n+2)$.
Proof: 
$$g^i(2n+2) = g^{i-1}(g(2n+2)) > g^{i-1}(h(2n)+2) > g^{i-2}(h^2(2n)+2) > g^{i-3}(h^3(2n)+2) > \ldots > h^i(2n) > f_m^i(n)$$
QED
Lemma 3. $2n+2 < 2 \uparrow^m \lceil \log_2(n) + 1\rceil$ for $m \ge 2, n \ge 3$.
Proof of Lemma 3: It suffices to prove the case $n = 2^k$, which reduces the lemma to
$$2 \cdot 2^k + 2 < 2 \uparrow^m ( k + 1)$$
Base case $k=2$: $2 \cdot 2^2 + 2 = 10 < 2\uparrow\uparrow 3 \le 2\uparrow^m 3$.
Inductive step:
$$2\uparrow^m(k+2) = 2\uparrow^{m-1}(2\uparrow^m(k+1)) \ge 2(2\uparrow^m(k+1)) > 2(2^{k+1}+2) = 2^{k+2} + 4 > 2^{k+2} + 2$$
QED
So, $$f_{m+1}(n) = f_m^n(n) < g^n(2n+2) <g^n(2\uparrow^m \lceil \log_2(n)+1\rceil) = 2\uparrow^m \lceil n+ \log_2(n) + 1 \rceil$$
</s>