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.

  • $\begingroup$ 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. $\endgroup$ Jun 22 '14 at 23:07
  • $\begingroup$ @DanielFischer I don't understnd why it suffices to look at these three terms only. Could you elaborate? $\endgroup$
    – Simon S
    Jun 23 '14 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.