Tighter bounds on the fast growing hierarchy? Not a dupe of this question, as I'm searching for tighter bounds.

We define the fast growing hierarchy for finite values as follows:
$$f_k(n)=\begin{cases}n+1,&k=0\\f_{k-1}^n(n),&k>0\end{cases}$$
where
$$f_k^a(n)=\underbrace{f_k(\dots f_k(}_an)\dots)$$
For example,
$$f_2(2)=f_1(f_1(2))=f_1(f_0(f_0(2)))=f_1(f_0(3))=f_1(4)\\=f_0(f_0(f_0(f_0(4))))=8$$
For $k=0,1,2$, we have known closed forms:
$$f_0(n)=n+1\\f_1(n)=2n\\f_2(n)=2^nn$$
And for $k=3$, I've derived tight bounds:
$$((2^n)\uparrow\uparrow n)n\le f_3(n)\le(2^nn)\uparrow\uparrow n$$
These bounds were obtained from the more general case:
$$((2^n)\uparrow\uparrow k)n\le f_2^k(n)\le(2^nn)\uparrow\uparrow k$$
Which can be seen by induction.  Note that:
$$f_2(((2^n)\uparrow\uparrow k)n)>2^{((2^n)\uparrow\uparrow k)n}n=((2^n)\uparrow\uparrow(k+1))n$$
Likewise, induction is doable on the upper bound.
We also have known lower bounds (trivial ones)
$$2\uparrow^{k-1}n\le f_k(n)$$
And the slightly less trivial upper bound (though it is far from a tight bound I'd imagine)
$$f_k(n)\le2\uparrow^{k-1}(2n)$$

Note that I have used Knuth's up-arrow notation, which is the natural extension past exponentiation.  It more or less goes as follows:
$$a\times b=\underbrace{a+\dots+a}_b\\a^b=a\uparrow b=\underbrace{a\times\dots\times a}_b\\a\uparrow\uparrow b=a\uparrow^2b=\underbrace{a\uparrow\dots\uparrow a}_b\\a\uparrow^3b=\underbrace{a\uparrow^2\dots\uparrow^2a}_b\\\vdots$$
Where the operation is expanded right to left:
$$3\uparrow3\uparrow3=3\uparrow(3\uparrow3)=3\uparrow27=7625597484987$$
$$3\uparrow3\uparrow3\ne(3\uparrow3)\uparrow3=27\uparrow3=19683$$


Using Knuth's up-arrow notation, is it possible to obtain even tighter bounds on $f_3(n)$?  What about $f_k(n)$ for $k>3$?

 A: Your bounds are quite good given their simplicity.  To get stronger bounds, we can use a lower tetration exponent - for example,
$$f_2^k(n) \ge \left(2^{2^n n} \uparrow\uparrow (k-1)\right)(2^n n)$$
One can verify it for $k = 1,2$, and then observe the inductive step
$$f_2^{k+1}(n) \ge f_2 \left( \left(2^{2^n n} \uparrow\uparrow (k-1)\right)(2^n n) \right) = 2^{\left(2^{2^n n} \uparrow\uparrow (k-1)\right)(2^n n)} \left(2^{2^n n} \uparrow\uparrow (k-1)\right)(2^n n) > \left( 2^{2^n n}\right)^{\left(2^{2^n n} \uparrow\uparrow (k-1)\right)} (2^n n) = \left(2^{2^n n} \uparrow\uparrow k\right)(2^n n)$$
To see that this is a tighter bound, note that $2^{2^n n} = 2^n \uparrow\uparrow 2$, and by induction $$(2^{2^n n}) \uparrow\uparrow k = (2^{2^n n})^{(2^{2^n n} \uparrow\uparrow (k-1))} > (2^n)^{2^n \uparrow\uparrow k} = 2^n \uparrow\uparrow (k+1)$$
For an upper bound, we can use
$$f_2^k(n) \le (2^{2^n n + n}n) \uparrow\uparrow (k-1) \qquad \text{ for } k \ge 2$$
We have equality at $k=2$, and
$$f_2^{k+1}(n) \le f_2((2^{2^n n + n}n) \uparrow\uparrow (k-1) ) = 2^{(2^{2^n n + n}n) \uparrow\uparrow (k-1) }((2^{2^n n + n}n) \uparrow\uparrow (k-1) ) < 2^{2((2^{2^n n + n}n) \uparrow\uparrow (k-1) )} < (2^{2^n n + n}n)^{(2^{2^n n + n}n) \uparrow\uparrow (k-1) } = (2^{2^n n + n}n) \uparrow\uparrow k$$
To see that this is a tighter bound, set $m = 2^n n$.  We must show that $2^m m \uparrow \uparrow (k-1) < m\uparrow\uparrow k$; to do this, we will prove that $(2^m m \uparrow\uparrow (k-1))m < m\uparrow\uparrow k$.
Observe that for $k=2$ we have $(2^m m)m < m^m$. ($m > 4$, so $m^m = m^2 m^{m-2} > m^2 2^{2m-4} > m^2 2^m$.)  Then for the inductive step, $$m\uparrow\uparrow(k+1) = m^{m\uparrow\uparrow k} > m^{(2^m m \uparrow\uparrow (k-1))m} = (m^m)^{2^m m \uparrow\uparrow (k-1)} > (2^m m^2)^{2^m m \uparrow\uparrow (k-1)} >(2^m m)^{2^m m \uparrow\uparrow (k-1)}m = (2^m m \uparrow\uparrow k)m $$
For higher levels of the fast-growing hierarchy, observe that
$f_k(n) > n \uparrow^{k-1} n$ for $k \ge 3, n \ge 2$
Hence if $f_{k+1}(n) \ge X$, then $f_{k+1}^m(n) \ge X \uparrow^k m$ by induction.
In particular, since we have $f_3(n) \ge (2^n \uparrow\uparrow n)n$, we then have
$$f_4(n) \ge ((2^n \uparrow^2 n)n) \uparrow^3 n$$
$$f_5(n) \ge (((2^n \uparrow^2 n)n) \uparrow^3 n) \uparrow^4 n$$
$$f_6(n) \ge ((((2^n \uparrow^2 n)n) \uparrow^3 n) \uparrow^4 n) \uparrow^5 n$$
and so on.  To keep the length of the bound from growing too large, we can replace an inner expression with a simpler bound like $f_k(n) \ge n \uparrow^{k-1} (n+1)$. So for example
$$f_k(n) \ge ((n \uparrow^{k-3} (n+1))\uparrow^{k-2} n) \uparrow^{k-1} n$$ for $k \ge 6$
Upper bounds are more troublesome.  It seems clear that if we replace $(2^n \uparrow^2 n)n$ with $2^n n \uparrow^2 n$ across the board we will get upper bounds, but I imagine the proof for this will be rather intricate.
