Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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$).

share|cite|improve this answer
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
@KirthiRaman: I don't understand your comment. Please clarify. – Robert Israel Mar 8 '12 at 22:07
$ \frac{\log n}{\log(1/p)} =\frac{\log n}{-\log p} = - \frac{\log n}{\log p}$ – Kirthi Raman Mar 8 '12 at 22:52
Yes, I know that. So? – Robert Israel Mar 8 '12 at 23:08
Oops! for $0<p<1$, $log p < 0$. So my comment does not make sense then – Kirthi Raman Mar 9 '12 at 2:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.