# Evaluating $\sum_{r=0}^\infty { 2r \choose r} x^r$

I recently came across this question during a test

Evaluate the following $$\sum_{r=0}^ \infty \frac {1\cdot 3\cdot 5\cdots(2r-1)}{r!}x^r$$

I converted it to the follwing into $$\sum_{r=0}^\infty { 2r \choose r} x^r$$ Then I tried using Beta function to further expand the binomial coefficient and tried to write it as sum of integrals but a pesky "r" term ends up being multiplied

How can we evaluate this with and without using calculus?

• This may help: en.wikipedia.org/wiki/…
– Gary
Commented Sep 5, 2021 at 18:32
• Avoid the use of $*$ to denote multiplication. That's a common practice in programming, not in Mathematics. Commented Sep 5, 2021 at 18:32
• Hint: $\binom{n}{k}=\oint_{|z=1|}\frac{(1+z)^ndz}{2\pi iz^{k+1}}$.
– J.G.
Commented Sep 5, 2021 at 18:47

Note that $$\sum_{r=0}^{\infty} {2r \choose r} x^r=(1-4x)^{-1/2}~~~~(1)$$ Proof:

This is due to binomial expansion of $$(1-4x)^{-1/2}$$ in infinite series as $$(1-4x)^{-1/2}=\sum_{r=0}^{\infty} {-1/2 \choose r} x^r~~~~(2)$$ Use $$(1+z)^{p}=1+pz+p(p-1)z^2/2+p(p-1)(p-2)z^3/3!+\dots~,~ |z|<1.$$

Next use $${-q \choose k}=(-1)^k{n+q-1 \choose k}$$

So $$(1-4x)^{-1/2}=\sum_{r=0}^{\infty} (-1)^r{r+1/2-1 \choose r}(-4x)^r$$ $$\implies (1-4x)^{-1/2}=\sum_{r=0}^{\infty} 2^{2r} {r-1/2 \choose r} x^r$$ $$\implies (1-4x)^{-1/2} =\sum_{r=0}^{\infty} \frac{1\cdot2\cdot3\cdot 4\cdots(2r-1)\cdot 2r}{r!~ r!}x^r=\sum_{r=0}^{\infty} {2r \choose r} x^r$$

The following approach is somewhat like taking a sledgehammer to crack a nut, but it can also conveniently used in more challenging situations. We use the coefficient of operator $$[x^r]$$ to denote the coefficient of $$x^r$$ of a series. This way we can write \begin{align*} \binom{2r}{r}&=[x^{r}](1+x)^{2r}\tag{1}\\ \end{align*}

We now use a clever change of variables stated as rule 5 in section 1.2 of Integral Representation and the Computation of Combinatorial Sums by G. P. Egorychev. Rule 5 adapted for this special case is:

\begin{align*} [x^r]f^{r}(x) &=[y^r]\left.\frac{f(x)}{f(x)-xf^{\prime}(x)}\right|_{x=g(y)}\tag{2} \end{align*}

Here we have $$f(x)=(1+x)^2$$ and $$g=g(y)$$ is the inverse function of \begin{align*} \frac{x}{f(x)}=\frac{x}{(1+x)^2}=y \end{align*} We obtain \begin{align*} &yx^2+(2y-1)x+y=0\\ &x=\frac{1}{2y}\left(1-2y\pm\sqrt{1-4y}\right)\tag{3}\\ \end{align*} We take from (3) the root $$x$$ with the minus sign, since this one represents a power series.

We obtain from (1),(2) and (3) \begin{align*} \color{blue}{\binom{2r}{r}}&=[x^{r}](1+x)^{2r}\\ &=[y^r]\left.\frac{(1+x)^2}{(1+x)^2-x\cdot 2(1+x)}\right|_{x=\frac{1}{2y}\left(1-2y-\sqrt{1-4y}\right)}\\ &=[y^r]\left.\frac{1+x}{1-x}\right|_{x=\frac{1}{2y}\left(1-2y-\sqrt{1-4y}\right)}\\ &\,\,\color{blue}{=[y^r]\frac{1}{\sqrt{1-4y}}}\tag{4}\\ \end{align*}

Since we can write a power series $$A(x)=\sum_{r=0}^{\infty}a_r x^r$$ as \begin{align*} A(x)=\sum_{r=0}^{\infty}a_r x^r=\sum_{r=0}^{\infty}\left([y^r]A(y)\right) x^r \end{align*} we obtain from (4)

\begin{align*} \color{blue}{\sum_{r=0}^\infty { 2r \choose r} x^r} =\sum_{r=0}^\infty \left([y^r]\frac{1}{\sqrt{1-4y}}\right)x^r=\color{blue}{\frac{1}{\sqrt{1-4x}}} \end{align*}

• I really like this approach, it is essentially equivalent to the Lagrange(-Buhrmann) inversion theorem, which is usually invoked to get the generating function of Catalan numbers. Commented Sep 7, 2021 at 0:52
• @JackD'Aurizio: Many thanks for the comment and the upvote. Yes, you're right. In fact the Lagrange–Bürmann formula is explicitly stated as rule 6 in the referred section 1.2. :-) A two-dimensional application is given in this answer. Commented Sep 7, 2021 at 7:41

Use the Duplication formula for Gamma function $$\Gamma \left( {2\,z + 1} \right) = \Gamma \left( {2\,\left( {z + 1/2} \right)} \right) = 2^{\,2\,z} \frac{{\Gamma \left( {z + 1} \right)\Gamma \left( {z + 1/2} \right)}}{{\Gamma \left( {1/2} \right)}}$$

So $$\begin{array}{l} \left( \begin{array}{c} 2r \\ r \\ \end{array} \right) = \frac{{2r!}}{{r!r!}} = \frac{{\Gamma \left( {2r + 1} \right)}}{{\Gamma \left( {r + 1} \right)\Gamma \left( {r + 1} \right)}} = \\ = 2^{\,2\,r} \frac{{\Gamma \left( {r + 1} \right)\Gamma \left( {r + 1/2} \right)}}{{\Gamma \left( {r + 1} \right)\Gamma \left( {r + 1} \right)}} = 4^{\,\,r} \frac{{\Gamma \left( {r + 1/2} \right)}}{{\Gamma \left( {r + 1} \right)\Gamma \left( {1/2} \right)}} = \\ = 4^{\,\,r} \frac{{\left( {r - 1/2} \right)!}}{{r!\left( { - 1/2} \right)!}} = 4^{\,\,r} \left( \begin{array}{c} r - 1/2 \\ r \\ \end{array} \right) = \\ \left| {\;0 \le r \in \Bbb{Z}} \right. \\ = \left( { - 1} \right)^{\,\,r} 4^{\,\,r} \left( \begin{array}{c} - 1/2 \\ r \\ \end{array} \right) \\ \end{array}$$

• Best and simplest answer here. Commented Sep 6, 2021 at 14:38

Yet another way.
Lemma 1: $$\int_{0}^{\pi/2}\left(\cos\theta\right)^{2n}\,d\theta = \frac{\pi}{2\cdot 4^n}\binom{2n}{n} \tag{1}$$ Proof of Lemma 1: by parity and De Moivre's formula $$\int_{0}^{\pi/2}(\cos\theta)^{2n}\,d\theta = \frac{1}{2}\int_{-\pi/2}^{\pi/2}\left(\frac{e^{i\theta}+e^{-i\theta}}{2}\right)^{2n}\,d\theta =\frac{1}{2\cdot 4^n}\sum_{k=0}^{2n}\binom{2n}{k}\int_{-\pi/2}^{\pi/2} e^{ki\theta} e^{-(2n-k)i\theta}\,d\theta$$ where the last integrals always equals zero, unless $$k=n$$.

Corollary:

$$\sum_{r\geq 0}\binom{2r}{r} x^r = \frac{2}{\pi}\sum_{r\geq 0}\int_{0}^{\pi/2}(4x\cos^2\theta)^{r}\,d\theta=\frac{2}{\pi}\int_{0}^{\pi/2}\frac{d\theta}{1-4x\cos^2\theta}.\tag{2}$$ Letting $$\theta=\arctan u$$ in the last integral we have $$\sum_{r\geq 0}\binom{2r}{r}x^r = \frac{2}{\pi}\int_{0}^{+\infty}\frac{du}{1+u^2-4x}\stackrel{u\mapsto v\sqrt{1-4x}}{=}\frac{2}{\pi\sqrt{1-4x}}\int_{0}^{+\infty}\frac{dv}{v^2+1}=\frac{1}{\sqrt{1-4x}}.\tag{3}$$

And another one. Since by Vandermonde's identity $$\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2$$ the Cauchy-Schwarz inequality gives $$\binom{2n}{n}\geq \frac{4^n}{n+1}$$. On the other hand $$\binom{2n}{n}\leq \sum_{k=0}^{n}\binom{2n}{k}=4^n$$, so the radius of convergence of our power series is exactly $$\frac{1}{4}$$. As a consequence, the radius of convergence of $$f(z)=\sum_{n\geq 0}a_n z^n\quad\text{with}\; a_n=\frac{1}{4^n}\binom{2n}{n}$$ is exactly one. The coefficients $$a_n$$ satisfy a nice recurrence relation: since $$\frac{1}{4^{n+1}}\binom{2n+2}{n+1} = \frac{(2n+2)(2n+1)}{4(n+1)^2}\binom{2n}{n}=\frac{(2n+1)}{2(n+1)}\binom{2n}{n}$$ we have $$2(n+1)a_{n+1}=(2n+1)a_n$$, which can be turned into a differential equation. Indeed $$f'(z) = \sum_{n\geq 0} (n+1) a_{n+1} z^{n},\qquad z\cdot f'(z)=\sum_{n\geq 1} n a_n z^n$$ hence $$2(1-z) f'(z) = f(z)$$ with $$f(0)=a_0=1$$. The last differential equation is a separable differential equation:

$$\frac{f'(z)}{f(z)}=\frac{1}{2(1-z)}\quad\Longrightarrow\quad \log f(x) = \int_{0}^{x}\frac{dz}{2(1-z)} = -\frac{1}{2}\log(1-x)$$ so by exponentiating both sides of the the last identity we get

$$\sum_{n\geq 0}\frac{1}{4^n}\binom{2n}{n}x^n = \frac{1}{\sqrt{1-x}}$$ as wanted.

Hint: Let $$f(x)=\sum_{r=0}^\infty \binom{2r}r x^r.$$ Then $$f(x)^2=\sum_{n=0}^\infty x^n\sum_{r+s=n}\binom{2r}r\binom{2s}s.$$ Can you combinatorially evaluate $$\sum_{r+s=n}\binom{2r}r\binom{2s}s,$$ and use it to figure out what $$f(x)^2$$ is?

• I think your "hint" only makes the problem harder. It is really hard to give a combinatorial proof for $\sum_{r+s=n} \binom{2r}{r}\binom{2s}s=4^n$. Commented Sep 5, 2021 at 18:48