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 am trying to find an exact formula for the following:


I don't think this should be too bad with a rearrangement of terms, but I keep getting stuck.

share|cite|improve this question
WA doesn't seem to give a nice formula... – user17762 Nov 29 '12 at 7:16
But that is without the other part of the sum and infinite..... – Joe Nov 29 '12 at 7:18
Ah, never mind, the link wasn't working properly at first. I have been told there is a nice exact form though – Joe Nov 29 '12 at 7:23

Here are some steps to the solution:

  • To get rid of the denominators, use ${2n\choose n-i}\frac1{n+i+1}={2n+1\choose n-i}\frac1{2n+1}$.
  • To simplify the steps to come, use the change of variable $k=n-i$, thus ${2n+1\choose n-i}(2i^2+i)={2n+1\choose k}((2n+1)n-(4n-1)k+2k(k-1))$ and $0\leqslant k\leqslant n$.
  • To compute $s_0=\sum\limits_{k=0}^n{2n+1\choose k}$, note that $2s_0=\sum\limits_{k=0}^{2n+1}{2n+1\choose k}=2^{2n+1}$.
  • To compute $s_1=\sum\limits_{k=0}^n{2n+1\choose k}k$, note that ${2n+1\choose k}k={2n\choose k-1}(2n+1)$ hence $s_1=(2n+1)t_1$ with $t_1=\sum\limits_{k=0}^{n-1}{2n\choose k}$ and $2t_1+{2n\choose n}=\sum\limits_{k=0}^{2n}{2n\choose k}=2^{2n}$.
  • To compute $s_2=\sum\limits_{k=0}^n{2n+1\choose k}k(k-1)$, note that ${2n+1\choose k}k(k-1)={2n-1\choose k-2}(2n+1)(2n)$ hence $s_2=(2n+1)2nt_2$ with $t_2=\sum\limits_{k=0}^{n-2}{2n-1\choose k}$ and $2t_2+2{2n-1\choose n}=\sum\limits_{k=0}^{2n-1}{2n-1\choose k}=2^{2n-1}$.

Putting all these together yields that the sum $S$ to be evaluated is $$ S=ns_0-(4n-1)t_1+4nt_2, $$ that is, $$ S=n2^{2n}-(4n-1)\tfrac12\left(2^{2n}-\textstyle{{2n\choose n}}\right)+n\left(2^{2n}-4\textstyle{{2n-1\choose n}}\right), $$ and finally, $$ S=\frac12\left(2^{2n}-{2n\choose n}\right)=2^{2n-1}-{2n-1\choose n}. $$

share|cite|improve this answer

Maple 16 says $$ {\frac {{4}^{n} \left( \sqrt {\pi }\; \Gamma \left( n+1 \right) - \Gamma \left( n+1/2 \right) \right) }{2 \sqrt {\pi }\;\Gamma \left( n+1 \right) }} $$

EDIT: Oh, looks like there's a nicer form:

$$ 2^{2n-1} - {{2n-1} \choose {n}}$$


share|cite|improve this answer
+1 -- interesting -- surprisingly small sequence number at OEIS. – joriki Nov 29 '12 at 8: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.