# Asymptotic complexity of $\sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$

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.

• The largest term is for $k = m-1$. Looking at the terms for $k\in \{m,m-1,m-2\}$ suffices to determine the asymptotic behaviour using Stirling's formula. Jun 22 '14 at 23:07
• @DanielFischer I don't understnd why it suffices to look at these three terms only. Could you elaborate? Jun 23 '14 at 2:16