# Asymptotic behavior of $\sum_{k=1}^{n}\left(1-p^{k}\right)^{n-k}$

I'm looking for pointers as to how to evaluate the asymptotic behavior of $\sum_{k=1}^{n}\left(1-p^{k}\right)^{n-k}$ for large $n$ where $0<p<1$ is fixed.

Any help is much appreciated.

-
Some examples indicate something like $n-f(p)$... – draks ... Mar 8 '12 at 19:42
That's obvious, @draks - the formula $Z_n(p)=\sum_k (1-p^k)^{n-k}$ is a polynomial in $p$ and $Z_n(0)=n$. – Thomas Andrews Mar 8 '12 at 19:45
Roughly speaking: Since $0<p<1$ we have $p^k$ decrease pretty fast to $0$, hence $1-p^k$ increase pretty fast to $1$, so the terms is "some what just below" $(1-p^n)$ - which would lead to the geometric sum $\sum_1^n(1-p^n)^{n-k}=\sum_0^{n-1}(1-p^n)^k=(1-(1-p^n)^n/p^n$. – AD. Mar 8 '12 at 19:46
@ThomasAndrews so my asymptotic is right...sorry I just looked at some examples, as I already wrote. No thinking involved... – draks ... Mar 8 '12 at 20:02

Note that $f(k,n) = (1-p^k)^{n-k}$ is an increasing function of $k$ for fixed $n$. For $k = \frac{\log n}{\log(1/p)} + t$ Maple says we have, as $n \to \infty$, $f(k,n) \approx e^{-p^t} + O(1/n)$. This goes exponentially to $1$ as $t \to +\infty$ and very rapidly to $0$ as $t \to -\infty$, so I suspect the sum will be $n - \frac{\log n}{\log(1/p)} + O(1)$ as $n \to \infty$ (i.e. the error made by approximating $f(k,n)$ by $0$ for $k < \frac{\log n}{\log(1/p)}$ and $1$ for $k > \frac{\log n}{\log(1/p)}$ will be bounded as $n \to \infty$).
Since $n$ and $k$ are non-negative integers, and $0<p<1$, it has to be the later, i.e. $f(n,k) \approx 1$ for $k > \frac{\log n}{\log(1/p)}$ – Kirthi Raman Mar 8 '12 at 21:49
$\frac{\log n}{\log(1/p)} =\frac{\log n}{-\log p} = - \frac{\log n}{\log p}$ – Kirthi Raman Mar 8 '12 at 22:52
Oops! for $0<p<1$, $log p < 0$. So my comment does not make sense then – Kirthi Raman Mar 9 '12 at 2:06