Question 7

In the next two questions, we will talk about functions that grow exponentially fast. For this, we extend the OO- and \Omega-notation to ignore polynomial factors, that is, factors of the form n^knk. Formally, for a function g: \R^+ ightarrow \R^+g:R+R+ we define \tilde{O}(g(n)) := \bigcup_{k \geq 1} O\left( g(n)\cdot n^k ight)O~(g(n)):=k1O(g(n)nk). That is, f(n) \in \tilde{O}(g(n))f(n)O~(g(n)) if f(n) \in O(g(n)\cdot n^k )f(n)O(g(n)nk) for some k\in \NkN. Similarly, \tilde{\Omega}(g(n)) := \bigcup_{k \geq 1} O\left( g(n)\cdot n^{-k} ight)~(g(n)):=k1O(g(n)nk), that is, f(n) \in \tilde{\Omega}(g(n))f(n)~(g(n)) if f(n) \in O \left( \frac{g(n)}{n^k} ight)f(n)O(nkg(n)) for some k \in \NkN. Finally, \tilde{\Theta}(g) := \tilde{O}(g) \cap \tilde{\Omega}(g)~(g):=O~(g)~(g).

Set f(n) := \sum_{k=0}^n k^2 {n \choose k}f(n):=k=0nk2(kn). It turns out that f(n) \in \tilde{\Theta}\left({a^n} ight)f(n)~(an) for some number a. What is a?