For 0<p<1, is the following sum asymptotically polynomial in n as $n\to \infty$:
$$\sum _{k=0}^n \left(2 p^{2^{k-1}}\right)^k \binom{n}{k}$$
If so, what would be the polynomial approxiamation? If not, what would be a meaningful approximation, or other bounds?
As of now I think I could show that it is not exponential...
Thanks.
Q: Find an approximation for, $$ S_n = \sum_{k=0}^n (2p^{2^{k-1}})^k {n \choose k} $$ A: The main idea here is to split the sum into good and bad sections. First, let's rephrase the question a little. Let $r = \frac{1}{\sqrt{p}} > 1$, then $$S_n = \sum_{k=0}^n (2r^{-2^k})^k {n \choose k}$$
Now with the weak estimate ${n \choose k} \leq n^k$, we get
$$ S_n \leq \sum_{k=0}^n r^{-k2^k} (2n)^k $$
If we can find the value $M$ after which the summand becomes less than 1, we'll be able to turn all the terms after that into a linear term.
So we want to find $M$ such that for all $k>M$, $$ r^{k2^k} \geq (2n)^k $$
Putting both sides to the power $1/k$, we only require $$ r^{2^k} \geq 2n \iff 2^k \geq \frac{\log(2n)}{\log (r)} $$
So $M = \log\left(\frac{\log(2n)}{\log (r)}\right)$ and we get
$$ \sum_{k \geq M}^n r^{-k2^k} (2n)^k \leq \sum_{k \geq M}^n 1 \leq n $$
Now let's look at the beginning part of the sum. Note that $M \leq \log\log(2n)$. For all $k<M$, we have that $$ (2n)^k \leq 2^{\log (2n) \left[\log\log(2n)-\log\log(r)\right]} \leq 2^{\log (2n) \log\log(2n)} = (2n)^{\log\log 2n} = n^{\log\log (2n)} \log(n) $$
We know that $r^{-k 2^k} < 1$ so we can ignore this term. So for the first sum we have $$ \sum_{k \leq M} r^{-k2^k} (2n)^k \leq M (2n)^M \leq \log(n)\log\log(2n)n^{\log\log(n)} $$
Combining both parts of the sum we have $$ S_n = O(\log(n)\log\log(n)n^{\log\log(n)}) = O(\log(n^{\log\log(n)})n^{\log\log(n)}) $$
Not quite a polynomial estimate but pretty close (if $n$ is the number of atoms in the universe, $\log\log (n)$ is about 8).
Edit: $${n \choose k} = \frac{n(n-1)\ldots (n-k-1)}{k(k-1)\ldots(2)(1)} \geq \frac{(n-k-1)^k}{k^k}$$ so substituting k = 1, 2, 3, ... we actually show that we can't get a polynomial bound unfortunately, as $(2r^{-2^k})^k$ is independent of $n$. Hope this answers your question!