3

How will you solve

$$\sum_{i=1}^{n}{2i \choose i}\;?$$

I tried to use Coefficient Method but couldn't get it! Also I searched for Christmas Stocking Theorem but to no use ...

Brian M. Scott
  • 616,228
Bakshinder
  • 39

2 Answers2

4

This is OEIS A006134; the generating function is

$$g(x)=\frac1{(1-x)\sqrt{1-4x}}\;,$$

but no closed form is given. There is an approximation

$$a(n)\sim\frac{2^{2n+2}}{3\sqrt{\pi n}}\;.$$

Correction: It’s one less than the sequence from OEIS, whose terms include $\binom00=1$.

Brian M. Scott
  • 616,228
  • Can I apply Chu-Vandermonde Identity here? – Bakshinder Feb 14 '13 at 07:24
  • @Bakshinder: I don’t see how. By the way, if you replace the central binomial coefficients with the Catalan numbers, you get OEIS A014137, which also appears to be quite intractable. – Brian M. Scott Feb 14 '13 at 07:28
  • Can you guide me how to approach these types of sequences? Elementary guidelines. – Bakshinder Feb 14 '13 at 07:34
  • 2
    @Bakshinder: Judging from the OEIS entries and the rather ugly closed form in Robert Israel’s answer, I don’t think that elementary methods will take you very far with these sequences. Frankly, when I get one that gives me trouble, I do what I did here: calculate a few terms and look it up in OEIS. – Brian M. Scott Feb 14 '13 at 07:39
  • It is actually A066796 and double A079309 – Henry Feb 14 '13 at 08:10
  • @Henry: It also isn’t the right sequence. The OP is adding central binomial coefficients. – Brian M. Scott Feb 14 '13 at 08:14
  • @Brian I think it is ${2 \choose 1},{2 \choose 1}+{4 \choose 2},{2 \choose 1}+{4 \choose 2}+{6 \choose 3},...$ i.e. $2,2+6,2+6+20,...$ i.e. $2,8,28,...$. What do you think it is? – Henry Feb 14 '13 at 09:32
  • @Henry: Exactly what you think it is, which isn’t A079309. Your comment didn’t mention A066796 when I responded to it; it identified the sequence as A079309. The sequence is of course A066796; it is also one less than A006134. – Brian M. Scott Feb 14 '13 at 09:35
  • @Brian - We may as well stop here. When you replied, my comment said "It is actually http://oeis.org/A066796" which I then corrected as I had messed up the link markdown – Henry Feb 14 '13 at 09:38
  • @Henry: You misunderstood me. I’m not talking about the mistyped link. I’m talking about the comment that now reads It is actually A066796 and double A079309. That comment did not mention A066796 when I first saw and responded to it; it mentioned only A079309 and said nothing about double. I assume that you made an edit that was quick enough to beat the 5-minute deadline but slow enough that I didn’t see it until you brought it to my attention with your I think it is comment. – Brian M. Scott Feb 14 '13 at 09:40
  • @Brian I am certain you are wrong about what happened (I am sure I mentioned A066796 on its own initially), and you seem equally certain I am wrong. It isn't helpful and it does not matter now. – Henry Feb 14 '13 at 09:55
1

Maple gives a "closed form" involving a hypergeometric function: $$ -1-{2\,n+2\choose n+1}\; {\mbox{$_2$F$_1$}(1,n+\frac32;\,n+2;\,4)}-\frac{i \sqrt {3}}{3} $$

Robert Israel
  • 448,999