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.

I am trying to find an exact formula for the following:

$\sum\limits_{i=0}^{n}{\binom{2n}{n-i}\frac{2i^2+i}{n+i+1}}$

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

share|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
add comment

2 Answers

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

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}}$$

See http://oeis.org/A000346

share|improve this answer
    
+1 -- interesting -- surprisingly small sequence number at OEIS. –  joriki Nov 29 '12 at 8:06
add comment

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.