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

Can we calculate the given combinatorial sum in closed form?

$$ \frac{\binom{2}{0}}{1}+\frac{\binom{4}{1}}{2}+\frac{\binom{8}{2}}{3}+\frac{\binom{16}{3}}{4}+\cdots+\frac{\binom{2^n}{n-1}}{n}$$

share|cite|improve this question
According to Wolfram Mathematica $S_n=\sum_{k=1}^{n}\frac{1}{k}\binom{2k}{k-1}=2(-2 + (e^{2 + n}\Gamma(2 + n, 1)/\Gamma(3 + n))$ – Adi Dani Jan 28 '13 at 23:30
@Adi: The $2k$ looks like a typo, it should be $2^k$. (Is the calculation correct?) – TMM May 7 '13 at 22:59
The numerators increase much faster than the denominators, so this won't converge. – Fred Kline May 12 '13 at 4:11

It is doubtful that a closed form exists for this sum. However, the terms grow very quickly. For $n$ large the sum is well approximated by its last term, $$\sum_{k=1}^n \frac{1}{k}{2^k\choose k-1} \sim \frac{1}{n}{2^n\choose n-1}.$$ For $n=13$ the error due to this approximation is one part in a million. For $n=20$ the error is one part in ten billion.

share|cite|improve this answer

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.