6
$\begingroup$

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.

  • 0
    [WA doesn't seem to give a nice formula...](http://www.wolframalpha.com/input/?i=summation+C%282n%2Cn-k%29*%282k%5E2%2Bk%29%2F%28n%2Bk%2B1%29+from+k+%3D+0+to+n)2012-11-29
  • 0
    But that is without the other part of the sum and infinite.....2012-11-29
  • 0
    Ah, never mind, the link wasn't working properly at first. I have been told there is a nice exact form though2012-11-29

2 Answers 2

5

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

3

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

  • 0
    +1 -- interesting -- surprisingly small sequence number at OEIS.2012-11-29