# Asymptotic equivalent of $\sum_{k=1} ^N\binom{N}{k}\frac{(-1)^{k+1}}{1-p^k}$

Suppose $$p \in (0,1)$$. I would like to find an asymptotic equivalent of

$$f(N)=\sum_{k=1} ^N\binom{N}{k}\frac{(-1)^{k+1}}{1-p^k}.$$

It looks like this sequence tends to infinity but extremely slowly.

• Intuitively, it'll go to infinity since for large $k$, $1-p^k$ is about $1$, and $\sum_{k=1}^N{N\choose k}(-1)^{k+1}=0$. Since the sum contains small values for $k$, the first couple of terms will have the largest impact on the outcome and the first couple of terms get quite large as $N$ gets large. – vrugtehagel Mar 19 '18 at 16:45
• I know for a fact it tends to infinity because this sum is actually the expected value of a ceartain random variable. But as for the asymptotic behavior, it's not so easy I think. – Joshua Benabou Mar 19 '18 at 16:57

A good asymptotic approximation is $$\sum_{k=1}^n\binom{N}{k} \frac{(-1)^{k+1}}{1-p^k} \sim \frac{\log{N}+\gamma}{\log{(1/p)}} + \frac{1}{2}, \, \, \, 0<p<1.$$
Use a geometric series for the factor involving $p$ to get the identity, $$\sum_{k=1}^n\binom{N}{k} \frac{(-1)^{k+1}}{1-p^k} = \sum_{k=0}^\infty \Big(1-(1-p^k)^N \Big).$$
Szpankowski in 'Average case Analysis of Algorithms on Sequences' shows how to solve this for $p=1/2$ in his Example 10.6. In fact, I reference this example as a solution to MSE 2794835. The modifications necessary for $p$ in your range appear straightforward, although I expect the approximation to break down for $p$ very near the endpoints. It is also interesting that oscillatory terms appear as corrections if an even more accurate approximation as a function of $N$ is desired.
• The constants are really not useful of $\sim.$ If true, it is true without $\gamma$ and $\frac12.$ What can we say about the error of this estimate? For $p=1/2$ and $n=3$ to $40000$, my data has that the difference between the sum and $\log_2(N)$ decreases and less than $\frac{1}{2}.$ But this estimate gives $\log_2(N)+\frac{1}{2}+\frac{\gamma}{\log 2}> \log_2(N)+\frac{1}{2}.$ – Thomas Andrews Apr 29 at 21:18
• Also, shouldn't the upper bound of the sum be $N$? $\sum_{k=1}^{N}$ rather than $\sum_{k=1}^{n}?$ – Thomas Andrews Apr 29 at 21:20
• On the other hand, $\frac{\lambda}{2}-\frac{1}{2}\approx 0.3327$ is almost exactly what I am seeing as the difference. – Thomas Andrews Apr 29 at 21:46