Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
2  
@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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.