MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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: 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)}.$$

share|cite|improve this answer
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*}

share|cite|improve this answer

(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. and Doyle and Snell: 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)

share|cite|improve this answer

Your Answer


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.