I'm trying to examine the asymptotic complexity of $$f(m) = \sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$$
Question: How do you prove or disprove $f(m) \in \mathcal{O}(2^{2^m})$?
Bonus Question: Is there even a $c < 2$ such that $f(m) \in \mathcal{O}(c^{2^m})$?
I tried expanding the binomials:
$$f(m) = \sum_{k=1}^m \frac{2^m! \cdot 2^k!}{2^k! \cdot (2^m-2^k)! \cdot 2^{k-1}! \cdot (2^k-2^{k-1})!} = 2^m! \cdot \sum_{k=1}^m \frac{1}{2^k! \cdot (2^m-2^k)! \cdot (2^{k-1}!)^2}$$
I furthermore considered Sterling's approximation, but I'm not sure whether you can use it on factorials with $k$, since $k$ is not necessarily large.