Is there any closed formula for $$ \sum_{k=0}^n\frac{\binom{2k}{k}^2}{2^{4k}} $$ ? This sum of is made out of the square of terms $a_{k}:=\frac{\binom{2k}{k}}{2^{2k}}$

I have been trying to verify that $$ \lim_{n\to\infty} (2n+1)\left[\frac{\pi}{4}-\sum_{k=0}^{n-1}\frac{\left(\sum_{j=0}^k a^2_{j}\right)}{(2k+1)(2k+2)}\right] -\frac{1}{2}{\sum_{k=0}^na^2_{k}}=\frac{1}{2\pi}, $$ which seems to be true numerically using Mathematica.

The question above is equivalent to finding some formula for $$b_{n}:=\frac{1}{2^{2n}}\sum_{j=0}^n\frac{\binom{2n+1}{j}}{2n+1-j}.$$ This is because one can verify that $$(2n+1)b_n=2nb_{n-1}+a_n,\qquad a_{n+1}=\frac{2n+1}{2n+2}a_n,$$ and combining these two we get $$(2n+2)a_{n+1}b_{n}-(2n)a_nb_{n-1}=a_n^2$$ Summing we get $$\sum_{k=0}^na_k^2=(2n+1)a_nb_n.$$

I also know that $$ \frac{\binom{2n}{n}}{2^{2n}}=\binom{-1/2}{n}, $$ so that $$ \sum_{k=0}^{\infty}\frac{\binom{2k}{k}}{2^{2k}}x^k=(1-x)^{-1/2},\quad |x|<1. $$ I have also seen the identity $$ \sum_{k=0}^n\frac{\binom{2k}{k}}{2^{2k}}=\frac{2n+1}{2^{2n}}\binom{2n}{n}. $$

  • $\begingroup$ I don't have my original reference (Melzak's Companion to Concrete Mathematics, IIRC) handy, but isn't there a variant of Hadamard convolution that produces the function $f(x) = \sum_n a_nb_nx^n$ from the two functions $g(x)=\sum_n a_nx^n$ and $h(x)=\sum_n b_nx^n$? $\endgroup$ – Steven Stadnicki May 16 '14 at 18:51
  • $\begingroup$ I will look into this. I have read the notes on combinatorial identities in H.W. Gould's website without success thus far. But there is a chapter on convolutions so I'll look into that. Thanks! $\endgroup$ – Erwin May 16 '14 at 21:27
  • $\begingroup$ I guess you must be already aware of related stuff like $\sum_{k=0}^\infty a_k^2/(2k+1) = 4G/\pi$, where $G$ is Catalan's constant... $\endgroup$ – Suvrit May 17 '14 at 1:03
  • $\begingroup$ also, Z.-W Sun: math.nju.edu.cn/~zwsun seems to be one of the masters of such sums---you may wish to contact him. $\endgroup$ – Suvrit May 17 '14 at 1:18
  • $\begingroup$ Suvrit, that is interesting, because in fact one gets from summation by parts that $$\sum_{k=0}^{n-1}\frac{\sum_{j=0}^k a_j^2}{(2k+1)(2k+3)}=\frac{1}{2}\sum_{k=0}^n\frac{a_k^2}{2k+1}-\frac{1}{2(2n+1)}\sum_{j=0}^na_j^2$$ which allows to write the limit in the form $\lim_{n\to\infty}(2n+1)\left(\frac{\pi}{4}-\frac{1}{2}\sum_{k=0}^n\frac{a_k^2}{2k+1}+\sum_{k=0}^{n-1} \frac{\sum_{j=0}^ka_j^2}{(2k+1)(2k+3)}-\sum_{k=0}^{n-1}\frac{\sum_{j=0}^ka_j^2}{(2k+1)(2k+2)}\right)$ but I don't know if this is better. Where can I see a proof of the identity you cite involving the Catalan constant? $\endgroup$ – Erwin May 17 '14 at 3:26

Mathematica says:

$$\sum_{k=0}^n \binom{2k}{k}^2 x^k = \frac{2 K(16 x)}{\pi }-\binom{2 (n+1)}{n+1}^2 x^{n+1} \, _3F_2\left(1,n+\frac{3}{2},n+\frac{3}{2};n+2,n+2;16 x\right).$$

(the previous answer had "pilot error", as Christian noticed), but in my defence, the OP does not square the binomial in most of his question.

Further $$2^{2 n} b_n = \frac{n \, _2F_1(-2 n-1,-2 n-1;-2 n;-1)-(2 n+1) \binom{2 n+1}{n+1} \, _3F_2(1,-n,-n;1-n,n+2;-1)}{n (2 n+1)}.$$

  • $\begingroup$ I had also entered it in Mathematica, but I am not sure if this expression will serve for what I need. I will add more to the question. Thanks!. $\endgroup$ – Erwin May 16 '14 at 21:29
  • 4
    $\begingroup$ Congratulations on your 1000th answer, Igor!!! $\endgroup$ – François G. Dorais May 17 '14 at 1:32
  • $\begingroup$ Did you actually sum $\binom{2n}{n}$ without squaring? I get your result with Sum[Binomial[2 k, k] /16^k, {k, 0, n}] $\endgroup$ – Christian Elsholtz May 17 '14 at 14:29

The limit I want to verify is $$ \lim_{n\to\infty} (2n+1)\left[\frac{\pi}{4}-\sum_{k=0}^{n-1}\frac{\left(\sum_{j=0}^k a^2_{j}\right)}{(2k+1)(2k+2)}\right] -\frac{1}{2}{\sum_{k=0}^na^2_{k}}=\frac{1}{2\pi} $$

For this it is sufficient to prove that the above expression under the limit is bounded above. I know this is true because of the original problem this limit is coming from, but I do not have a short prove. Then, given that such expression is bounded, we can argue as follows: using summation by parts we see that $$ \sum_{k=0}^{n-1}\left(\frac{1}{2k+1}-\frac{1}{2k+3}\right)\sum_{j=0}^ka^2_{j}=\sum_{k=0}^n\frac{a^2_{k}}{2k+1}-\frac{1}{2n+1}\sum_{k=0}^na^2_{k} $$ and so we can write the limit as \begin{align*} \lim_{n\to\infty} (2n+1)\left[\frac{\pi}{4}-\frac{1}{2}\sum_{k=0}^n\frac{a^2_{k}}{2k+1}-\sum_{k=0}^{n-1}\frac{\sum_{j=0}^ka^2_{j}}{(2k+1)(2k+2)(2k+3)}\right] \end{align*} Since the limit of the bracket must be zero in under for the whole expression to remain bounded above, $\pi/4$ must equal the series (sum from $k=0$ up to $\infty$) and since \begin{align*} a_{n}:=\frac{1}{2^{2n}}&\binom{2n}{n}= \frac{\Gamma(1/2)\Gamma(n+1/2)}{\pi\Gamma(n+1)}= \frac{1+O(1/n)}{\sqrt{\pi n}} \end{align*} the limit becomes \begin{align*} &\lim_{n\to\infty}(2n+1)\left[\frac{1}{2}\sum_{k=n+1}^\infty\frac{a^2_{k}}{2k+1}+\sum_{k=n}^{\infty}\frac{\sum_{j=0}^ka^2_{j}}{(2k+1)(2k+2)(2k+3)}\right]\\ =&\lim_{n\to\infty} \frac{(2n+1)}{2\pi}\sum_{k=n+1}^\infty\frac{1+O(1/k)}{k(2k+1)}+ (2n+1)O\left(\sum_{k=n}^{\infty}\frac{\sum_{j=0}^k\frac{1}{j}}{(2k+1)(2k+2)(2k+3)}\right)\\ =&\frac{1}{2\pi}. \end{align*}


(Not yet an answer, but too long for a comment).

The expression $\frac{\binom{2n}{n}^2}{16^n}$ occur in random walks on lattice grids in the plane, (going back to Polya). See e.g. http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter12.pdf and Doyle and Snell: http://arxiv.org/pdf/math/0001057 section 2.3.3.

The fact that the infinite sum diverges is Polya's result that the random walk will almost surely return.

Mathematica Sum[Binomial[2 k, k]^2/16^k, {k, 0, n}] gives an expression which is hard to read/interpret, but links to some difference equation, Maybe this helps...

  Function[{\[FormalY], \[FormalN]}, {(1 +
         2 \[FormalN])^2 \[FormalY][\[FormalN]] + (-5 -
         12 \[FormalN] - 8 \[FormalN]^2) \[FormalY][1 + \[FormalN]] +
      4 (1 + \[FormalN])^2 \[FormalY][2 + \[FormalN]] ==
     0, \[FormalY][0] == 0, \[FormalY][1] == 1}]][1 + n]

Also of interest is maybe:

Sum[Binomial[2 k, k]^2 x^k, {k, 0, n}]

(2 EllipticK[16 x])/\[Pi] - 
 x^(1 + n) Binomial[2 (1 + n), 
   1 + n]^2 HypergeometricPFQ[{1, 3/2 + n, 3/2 + n}, {2 + n, 2 + n}, 
   16 x]

(if anybody can display/interpret this in a better form, please do)


The generating function for $b_n$ can be expressed as \begin{split} \sum_{n\geq 0} b_n z^{2n} &= \frac{2}{z(z+2)}\cdot\log\frac{1+z-\sqrt{1-z^2}}z \\ &+ \frac{2}{z(z-2)}\cdot\log\frac{\sqrt{1-z^2}-1+z}z\\ &- \frac{4}{(z-2)(z+2)}\cdot\log\frac{1+\sqrt{1-z^2}}2. \end{split}

Just in case, here is numerical verification in Maple:

> seq( add( binomial(2*n+1,j) / (2*n+1-j), j=0..n ) / 2^(2*n), n=0..6 );
                 11  287  5989   114859  4215377   188220881
              1, --, ---, -----, ------, --------, ----------
                 24  960  26880  645120  28385280  1476034560

> series( 2/(z+2)/z*ln( (1+z-sqrt(1-z^2))/z ) +  2/(z-2)/z*ln( (sqrt(1-z^2)-1+z)/z ) - 4/(z-2)/(z+2)*ln( (1+sqrt(1-z^2))/2 ), z, 14);
    11  2   287  4   5989   6   114859  8   4215377   10   188220881   12      14
1 + -- z  + --- z  + ----- z  + ------ z  + -------- z   + ---------- z   + O(z  )
    24      960      26880      645120      28385280       1476034560

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.