# Combinatorial identity involving the square of $\binom{2n}{n}$

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

• 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$? – Steven Stadnicki May 16 '14 at 18:51
• 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! – Erwin May 16 '14 at 21:27
• 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... – Suvrit May 17 '14 at 1:03
• 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. – Suvrit May 17 '14 at 1:18
• 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? – 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)}.$$

• 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!. – Erwin May 16 '14 at 21:29
• Congratulations on your 1000th answer, Igor!!! – François G. Dorais May 17 '14 at 1:32
• Did you actually sum $\binom{2n}{n}$ without squaring? I get your result with Sum[Binomial[2 k, k] /16^k, {k, 0, n}] – 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...

DifferenceRoot[
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