How would you show that the series $$\sum_{n=1}^\infty \frac{(2n)!}{4^n (n!)^2}$$ diverges? Wolfram Alpha says it diverges "by comparison", but I'd like to know to what you would compare it? I've tried some basic things to no avail: The ratio test is inconclusive, comparing with something "smaller" which I know diverges is proving difficult. If possible, I'd like to show this without using anything fancy (such as Stirling's approximation).
Can you do this with a "basic" comparison?
On
You can use Stirling's approximation for the factorial:
$$\frac{(2n)!}{4^n(n!)^2}\sim\frac{\sqrt{2\pi2n}\left(\frac{2n}e\right)^{2n}}{4^n\cdot2\pi n\left(\frac ne\right)^{2n}}=\frac{(2n)^{2n}e^{2n}}{4^n\sqrt{\pi n}\,n^{2n}e^{2n}}=\frac1{\sqrt{\pi n}}$$
and the last part's series diverges.
On
Note that the terms of your series are
$$ \frac{1}{2}, \quad \frac{1}{2} \times \frac{3}{4}, \quad \frac{1}{2} \times \frac{3}{4} \times \frac{5}{6}, \quad \cdots $$
Compare this with the sequence
$$ \frac{1}{2}, \quad \frac{1}{3}, \quad \frac{1}{4}, \quad \cdots $$
which can be rewritten
$$ \frac{1}{2}, \quad \frac{1}{2} \times \frac{2}{3}, \quad \frac{1}{2} \times \frac{2}{3} \times \frac{3}{4}, \quad \cdots $$
Since the first terms are equal, and the ratios between successive terms are always larger in the first series than in the second, it follows that the sum of the first series (if it exists) must be larger than the sum of the second. Since the second diverges (it is simply the harmonic series minus the first term), so must the first.
On
Note that $\frac{(2n)!}{(n!)^2} = \binom{2n}{n}.$ We have that $\binom{2n}{n} = \frac{2n(2n-1)}{n^2} \binom{2(n-1)}{n-1}$.
By the above recurrence for the middle binomial coefficient we have that $4^{-n} \binom{2n}{n}$ = $\binom{0}{0} \prod_{k=1}^n \frac{2k(2k-1)}{4k^2} = \prod_{k=1}^n \frac{2k-1}{2k} = \frac 12 *\frac 34 * \frac 56 *...*\frac{2n-1}{2n} = \frac 32 * \frac 54 * \frac 76 *...*\frac{2n-1}{2n-2} * \frac{1}{2n} \ge \frac{1}{2n}.$ So the series diverges by comparison with the harmonic series.
On
From the well-known identity
$$\binom{2n}{n}= \sum_{k=0}^{n}\binom{n}{k}^2 $$
and Cauchy-Schwarz inequality it follows that
$$ 4^n = \left(\sum_{k=0}^{n}1\cdot\binom{n}{k}\right)^2 \leq (n+1)\sum_{k=0}^{n}\binom{n}{k}^2 = (n+1)\binom{2n}{n} $$
hence:
$$ \frac{1}{4^n}\binom{2n}{n} = \frac{(2n)!}{4^n n!^2}\geq \frac{1}{n+1} $$
and $\sum_{n\geq 1}\frac{1}{n+1}$ is divergent by Cauchy's condensation test, for instance.
Another chance is given by noticing that
$$\frac{1}{4^n}\binom{2n}{n}=\frac{(2n-1)!!}{(2n)!!}=\prod_{k=1}^{n}\left(1-\frac{1}{2k}\right)=\frac{1}{2}\sqrt{\prod_{k=2}^{n}\left(1-\frac{1}{k}+\frac{1}{4k^2}\right)}$$
so:
$$\left(\frac{1}{4^n}\binom{2n}{n}\right)^2 = \frac{1}{4n}\prod_{k=2}^{n}\left(1-\frac{1}{(2k-1)^2}\right)^{-1}=\frac{1}{4n}\prod_{k=2}^{n}\left(1+\frac{1}{4k^2-4k}\right) $$
together with Wallis product can be used to prove the more accurate inequality:
$$ \frac{1}{\sqrt{\pi\left(n+\frac{1}{2}\right)}}\leq \frac{(2n)!}{4^n n!^2}\leq \frac{1}{\sqrt{\pi n}}.$$
On
For the case where the ratio test is inconclusive as in this case, you could use Raabe's test
$$\lim_{n\to\infty} n\left(\left|\frac{a_n}{a_{n+1}}\right|-1\right)=R$$ $$a_n=\frac{(2n)!}{4^n (n!)^2}\implies \frac{a_n}{a_{n+1}}=\frac{2n+2}{2 n+1}$$ $$n\left(\left|\frac{a_n}{a_{n+1}}\right|-1\right)=n\left(\frac{2n+2}{2 n+1}-1\right)=\frac{n}{2 n+1}\implies R=\frac 12$$ so divergence.
Update
Since the gamma function has been invoked in @Cameron Williams's answer, let us recall that $$S_p=\sum_{n=1}^p \frac{(2n)!}{4^n (n!)^2}=\frac 2 {\sqrt \pi}\frac{ \Gamma \left(p+\frac{3}{2}\right)}{ \Gamma (p+1)}-1$$ Using the asymptotics of the gamma function, for large values of $p$, $$S_p=\frac{2 }{\sqrt{\pi }}\sqrt{p}-1+\frac{3 }{4 \sqrt{\pi p }}+O\left(\frac{1}{p^{3/2}}\right)$$ For illustration purposes, $$S_{10}=\frac{707825}{262144}\approx 2.70014$$ while the above approximation gives $$-1+2 \sqrt{\frac{10}{\pi }}+\frac{3}{4 \sqrt{10 \pi }}\approx 2.70206$$
On
By the generalized binomial theorem we have that $$\sum_{n\geq0}\frac{\left(2n\right)!}{n!n!}x^{n}=\sum_{n\geq0}\frac{\left(2n\right)\left(2n-1\right)\cdots\left(n+1\right)}{n!}x^{n}=\sum_{n\geq0}\frac{\left(2n-1\right)\left(2k-3\right)\cdots3\cdot1}{n!}2^{n}x^{n} =\sum_{n\geq0}\frac{\left(-\frac{1}{2}\right)_{n}}{n!}4^{n}x^{n}=\frac{1}{\sqrt{1-4x}} $$ hence taking $x\rightarrow\frac{1}{4} $ we have $$\sum_{n\geq1}\frac{\left(2n\right)!}{n!^{2}}\frac{1}{4^{n}}=\lim_{x\rightarrow1/4}\left(\frac{1-\sqrt{1-4x}}{\sqrt{1-4x}}\right)=\infty.$$
On
Here is my attempt:
$a_n=\dfrac{(2n)!}{4^n(n!)^2}$
First i expanded factorial terms:
$a_n=\dfrac{2n(2n-1)(2n-2)\cdots 3\cdot 2\cdot 1}{4^n n(n-1)(n-2)\cdots 2\cdot 1\cdot n(n-1)(n-2)\cdots 2\cdot 1}$
At the numerator, rearrange the $n$ even factors and the $n$ odd factors (not necessary but useful for my description)
$a_n=\dfrac{2n(2n-2)(2n-4)\cdots 4\cdot 2\cdot (2n-1)(2n-3)(2n-5)\cdots 5\cdot 3\cdot 1}{4^n n^2(n-1)^2(n-2)^2\cdots 2^2\cdot 1^2}$
From the $n$ even factors collect $2$:
$a_n=\dfrac{2^n n(n-1)(n-2)\cdots 2\cdot 1 \cdot (2n-1)(2n-3)(2n-5)\cdots 5\cdot 3\cdot 1}{4^n n^2(n-1)^2(n-2)^2\cdots 2^2\cdot 1^2}$
Now you can simplify the square factors at the denominator with the terms $n(n-1)(n-2)\cdots 2\cdot 1$ obtained from collecting $2$; you have:
$a_n=\dfrac{2^n (2n-1)(2n-3)(2n-5)\cdots 5\cdot 3\cdot 1}{4^n n(n-1)(n-2)\cdots 2\cdot 1}$
Obviously you can simplify $\dfrac{4^n}{2^n}$; so:
$a_n=\dfrac{(2n-1)(2n-3)(2n-5)\cdots 5\cdot 3\cdot 1}{2^n n(n-1)(n-2)\cdots 2\cdot 1}$
Now consider the factors at the numerator:
$(2n-1)\geq (2n-2)$
$(2n-3)\geq (2n-4)$
$(2n-5)\geq (2n-6)$
and so on.
You have:
$a_n\geq \dfrac{(2n-2)(2n-4)(2n-6)\cdot 4\cdot 2}{2^n n!}$
Again collect a factor $2$ at the numerator:
$a_n\geq\dfrac{2^n (n-1)(n-2)\cdots 4\cdot 2}{2^n n!}$
Simplify the terms $2^n$ and note that the numerator is $(n-1)!$; so:
$a_n\geq\dfrac{(n-1)!}{n!}=\dfrac{1}{n}$
We know that $\sum_{n=1}^\infty\dfrac{1}{n}$ diverges; so by comparison our series:
$\sum_{n=1}^{\infty}a_n$ diverges.
Hope this help.
On
Let $$(2n)!!=\displaystyle\prod_{\substack{2\le x\le 2n\\ x\equiv 0 \pmod 2}} x$$and $$(2n)!!^\ast=\displaystyle\prod_{\substack{2\le x\le 2n\\ x\equiv 1 \pmod 2}} x\tag{1}$$ Then, $$(2n)!!=2^n n!$$ Hence, $$\dfrac{(2n)!}{4^n(n!)^2}=\dfrac{(2n)!}{((2n)!!)^2}=\dfrac{(2n)!!^\ast}{(2n)!!}\ge \left(\dfrac{2n-1}{2n-2}\right)^{n-1}\cdot\dfrac{1}{2n}\ge \dfrac{1}{2n}\tag{2}$$Consequently, $$\displaystyle\sum_{n=1}^\infty\dfrac{(2n)!}{4^n(n!)^2}\ge \displaystyle\sum_{n=1}^\infty\dfrac{1}{2n}$$But the series $\displaystyle\sum_{n=1}^\infty\dfrac{1}{2n}$ diverges and we are done. (Can you prove $(1)$ and $(2)$?)
Remarks. You may also use the method of this answer to show that $\displaystyle\sum_{n=1}^\infty\dfrac{(2n)!}{4^n(n!)^2}\ge \displaystyle\sum_{n=1}^\infty\dfrac{1}{2n}$.
On
For $n>0 $ let $A_n=(2n)!/4^n(n!)^2 $ and $B_n=A_n\sqrt n. \;$ Then $(B_n)_n$ is increasing because $B_{n+1}/B_n=\frac {2n+1}{2n+2} \sqrt {\frac {n+1}{n}}=\sqrt {\frac {(2n+1)^2(n+1)}{(2n+2)^2n}}=\sqrt {\frac {4n^3+8n^2+5n+1}{4n^3+8n^2+4n}}>1.$ Hence for $n\geq 1$ we have $$A_n=\frac {B_n}{\sqrt n}\geq \frac {B_1}{\sqrt n}=\frac {1}{2\sqrt n}.$$ So $\sum_nA_n$ diverges by comparison with $\sum_n1/\sqrt n.$
On
After the great answer of Adam Hughes one likely needs no more...
However, I like the following comparision-test, at which I arrived after some fiddling.
We compare $\sum a_n $ with $\sum \frac1{2n}$ and show by induction, that always $a_n>\frac1{2n}$ and the series diverges by comparision with the harmonic series.
Let's denote the series
$$ s=\sum_{k=0}^\infty a_n = 1+ \frac12+\frac12\frac34+\frac12\frac34\frac56 + \frac12\frac34\frac56\frac78 + ...\\
$$
Rewritten in the spirit of the said comparision this is
$$ s =1+ \frac12\left[(1)1 +\left({3\over2}\right)\frac12+\left({ 3 \cdot 5\over 2\cdot 4}\right)\frac13+\left({ 3 \cdot 5 \cdot 7\over 2\cdot 4 \cdot 6}\right)\frac14 + ... \right] \\
$$
and we want to show, that all parentheses have value greater than 1.
Induction as follows: we observe that this is true for the parenthese $p_2= \left( \frac32\right)$ at $a_2$: $\left({ 3\over2}\right) \gt 1$
The next parenthese is the previous postmultiplied by $\frac54$ so also this must be greater than 1. And this is obviously the case for all following parentheses.
Formally:
all parentheses $p_{n \gt 1} \gt 1$ and all terms $a_{n \gt 1} \gt \frac1{2n}$ and the series diverges.
On
I'm going to appeal to the gamma function since it also gives a nice solution. It may be beyond the OP, but the technique may be of interest or use to others. We have that
$$\Gamma\left(n+\frac{1}{2}\right) = \frac{(2n)!\sqrt{\pi}}{4^n n!}$$
and so
$$ \frac{(2n)!}{4^n(n!)^2} = \frac{1}{\sqrt{\pi}} \frac{\Gamma\left(n+\frac{1}{2}\right)}{n!}.$$
Using the fact that the gamma function is monotone on $[2,\infty)$ and $\Gamma(n) = (n-1)!$ for $n\in\Bbb N$, we can get a lower bound:
$$ \frac{1}{\sqrt{\pi}n} = \frac{1}{\sqrt{\pi}}\frac{\Gamma(n)}{n!} \le \frac{1}{\sqrt{\pi}} \frac{\Gamma\left(n+\frac{1}{2}\right)}{n!} = \frac{(2n)!}{4^n (n!)^2}.$$
Therefore
$$\sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi}n} \le \sum_{n=1}^{\infty} \frac{(2n)!}{4^n (n!)^2}.$$
The first sum diverges as it is the harmonic series and so we get that the series in question also diverges. Note that the above does not give a sharp estimate for the individual terms unlike Stirling and the other estimates but the claims above are simply proved.
On
The sum $\sum_{n=1}^\infty\frac{(2n)!}{4^n(n!)^2}=\sum_{n=1}^\infty\binom{2n}n(\frac12)^{2n}$ is the expected number of returns to the origin in a symmetric random walk on the integers. [*] Instead of trying to show analytically that the series diverges, let's try to use direct probabilistic reasoning to see why the expectation is infinite. Equivalently, we wish to show that, at any point, the probability of returning to the origin is one.
Let $a_0=1$ and, for $n\gt0,$ let $a_n$ be the probability of returning to the origin from a point at a distance of $n$ units from the origin. Since the walk is symmetric, for $n\gt0$ we have $a_n=\frac12a_{n-1}+\frac12a_{n+1},$ i.e., $a_{n-1},a_n,a_{n+1}$ are in arithmetic progression. Hence the sequence $a_0,a_1,a_2,\dots$ is an infinite arithmetic progression. Since the terms $a_n$ are probabilities, the progression is confined to the interval $[0,1],$ so it can only be a constant sequence. Since $a_0=1,$ we must have $a_n=1$ for all $n,$ Q.E.D.
[*] Consider an infinite sequences of independent fair coin tosses. Let the indicator variable $X_n$ take the value $1$ if we have equal numbers of heads and tails in the first $2n$ tosses, $0$ otherwise. Then the number of returns to the origin is the random variable $X=\sum_{n=0}^\infty X_n,$ and by linearity $E(X)=\sum_{n=1}^\infty E(X_n)=\sum_{n=1}^\infty P(X_n=1)=\sum_{n=1}^\infty\binom{2n}n(\frac12)^{2n}.$
Note ${2n\choose n} >{2^{2n}\over 2n+1}$ because it is the largest binomial coefficient and so is bigger than the average (= sum / total number) and compare to
$$\sum_n{1\over 2n+1}$$