5

I am interested in a simplified version of the following sum $$\sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^k}{2^k-1}.$$ I have to evaluate it for values of n ranging from $10^{4}$ till $10^{10}.$ Is there a way to express it in terms of some special function computable through Matlab or mathematica?

UPDATE : For small values of $n$ I noticed that the value is quite close to $−log_2(n).$

Coniferous
  • 780

2 Answers2

2

We can rewrite the sum using a geometric series, then apply the binomial theorem: \begin{align*} \sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^k}{2^k-1}&=\sum_{k=1}^n (-1)^k {n\choose k} \sum_{m=1}^\infty \frac{1}{2^{mk}}\\ &=\sum_{m=1}^{\infty}\left[\left(1-\frac{1}{2^{m}}\right)^n-1\right]. \end{align*} In a sense this made things worse, because we replaced the finite sum with an infinite one. On the other hand, the infinite series is nice because:

  • the terms are all negative and increase monotonically to $0$, and
  • the terms decay exponentially once $m$ is bigger than $\log_2(n)$.

For $n$ large, terms in the series are very close to $-1$ when $m$ is less than $\log_2 n$ and very close to $0$ when $m$ is greater than $\log_2 n$. With some care, this is enough to show that the sum never differs from $-\log_2(n)$ by more than $2$.

Julian Rosen
  • 16,142
1

Using Newton's Binomial Theorem we can obtain a lower bound $$\sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^k}{2^k-1} \approx \sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^k}{2^k}=-1+\sum_{k=0}^{n}\binom{n}{k}\frac{(-1)^k}{2^k}=-1+(1-\frac{1}{2})^n=-1+\frac{1}{2^n}$$

Uri Goren
  • 2,940
  • So here you have approximated the denominator of each term $2^k-1\approx 2^k.$ Will it be possible to have some other form of approximation? – Coniferous Feb 16 '16 at 21:37
  • Unfortunately this approximation $-1+(1/2)^n$ is very inaccurate, because as $n$ grows it approaches $-1$, while apparently the absolute value of the formula increases about logarithmically with $n$. For example, f(10)=-3.7255593, f(100)=-6.98380, f(1000)=-10.2993. – Giovanni Resta Feb 16 '16 at 21:43
  • Another thing you can do is approximate $\frac{1}{2^k-1}$ as $\frac{k}{2^{k-1}}$, and get something like $-1-\frac{n}{2^{n-1}}$ – Uri Goren Feb 16 '16 at 21:45
  • For small values of $n$ I noticed that the value is quite close to $-log_2(n).$ hoping this information might help :)! – Coniferous Feb 16 '16 at 21:56
  • Yes, for example $f(1000)/\log_2(1000)= -1.0334$ and $f(10000)/\log_2(10000)= -1.0250$. – Giovanni Resta Feb 16 '16 at 22:09
  • Perhaps the Taylor series of $log(1+x)$ could be helpful – Uri Goren Feb 16 '16 at 22:11
  • @GiovanniResta can you please tell me how you calculated $f(10^4)$ ? Which software did you use ? – Coniferous Feb 16 '16 at 22:31
  • The approximation with (1- 1/2)^n was very elegant, but I did not understand how the -1 left the denominator and got subtracted from the overall sum – Saikat Feb 16 '16 at 23:15
  • The -1 in the denominator was neglected, the -1 in the sum is because the binomial sum in Newton's Binomial theorem starts from 0 and not 1 – Uri Goren Feb 17 '16 at 06:03
  • @Coniferous I used Mathematica. The problem here is that the intermediate addends are very large. In general, the largest term (abs.value) is when $k=n/3$. For example, for $n=10000$ and $k=3333$ the term is about $-6.9\cdot 10^{1758}$. The sum is alternating, there is huge cancellation, so the intermediate results NEED to be computed with a very large precision or the final result will be meaningless. In C language, you can use the GMP library. Be really careful because in some languages you got arbitrary precision integers by default, but not arbitrary precision floating-point numbers. – Giovanni Resta Feb 17 '16 at 09:09