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

Question

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?

Answer 1

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

Answer 2

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*}

Answer 3

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

Answer 4

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.

Answer 5

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?