# How would you show that the series $\sum_{n=1}^\infty \frac{(2n)!}{4^n (n!)^2}$ diverges?

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?

• Your title is at odds with the body of your question. Please correct this. – Deepak Aug 9 '16 at 22:42
• Why the "close"-vote? – Gottfried Helms Aug 11 '16 at 8:53

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

• Couldn't get any better than this! – DanielWainfleet Aug 10 '16 at 17:49
• I really enjoyed this answer. – Babak Aug 11 '16 at 5:51

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.

• Check again, the fourth term of the first series is 3/128 larger than the fourth term of the harmonic series. wolframalpha.com/input/?i=(2*+4)!+%2F+(+4!)%5E2+%2F+4%5E+(4)+-+1%2F+(4) – Adam Hughes Aug 9 '16 at 23:06
• @AdamHughes: ??? I am comparing the given series with the harmonic series less the first term. It should therefore be compared with $1/5$, not $1/4$. ¶ That being said, I asserted that each term of the first series is greater than the corresponding term of the second series, so I'm not sure what you're claiming the problem is with my demonstration. – Brian Tung Aug 9 '16 at 23:11
• I see where you're going I think. I don't think it's very clear from what you've posted though, but with a little clean-up and use of real variables and estimates (rather than intuition and a couple of cases) this could be very good if you can pin it down. Cheers! – Adam Hughes Aug 9 '16 at 23:22
• @AdamHughes: I know what you meant, no confusion! My point is only that different presentations are clearer to different people. – Brian Tung Aug 9 '16 at 23:29
• Very nice; hard to get more elementary than this! – Brian M. Scott Aug 10 '16 at 15:45

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

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.

• Although this is quite true, I'm not sure that it answers the question, which explicitly requests a non-Stirling proof. (I didn't vote on this answer). – user296602 Aug 9 '16 at 22:45
• I didn't even read the thing about Stirling, though I wouldn't call it "fancy". I don't really care who downvoted, though thank you for remarking it wasn't you. I shall let this as it is because I think it can help others. Whoever wants to downvote please knock yourselves out. – DonAntonio Aug 9 '16 at 22:48
• It certainly is the cleanest proof, and gives sharp asymptotics. I'm sorta surprised that the sharp estimate isn't all that far from the pretty crude but easier binomial coefficient estimate in another answer. – user296602 Aug 9 '16 at 22:50
• @T.Bongers Indeed so. I think Stirling's approximation is very good, as surprisinng as it is mixing numbers apparently so different as $\;\pi,\,e\;$ . With $\;n=5\;R the approximation is a little more that 98.33%, and with$\;n=6\;$it already is above 98.6%. Remarkable. – DonAntonio Aug 9 '16 at 22:56 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$$ 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. 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. • Very nice! So after I got the comparision of the$a_n$with$\frac12 \cdot \frac1n$and you got$\frac1{\sqrt{\pi}}\cdot \frac1n$which is farther from the harmonic series one can now think of a competition asking for an even higher low-bound multiple of the reciprocal numbers for the terms$a_n$... – Gottfried Helms Aug 11 '16 at 6:55 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. • The terms approach zero as you go towards infinity. – Adam Hughes Aug 9 '16 at 23:23 • You're right, I edited my argument. Thanks. – Vik78 Aug 9 '16 at 23:44 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.$$ 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}.$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: • Let$\displaystyle \qquad a_n = {1 \cdot 3 \cdot ... \cdot (2n-1)\over 2^n n!} $and$\displaystyle \qquad p_n = {1 \cdot 3 \cdot ... \cdot (2n-1)\over 2^{n-1} (n-1)!} $• Then$ \displaystyle \qquad p_n\gt1 \implies p_{n+1}=p_n \cdot {2n+1\over2n} \gt 1$• and because we know that$ \displaystyle \qquad p_2>1 $all parentheses$p_{n \gt 1} \gt 1$and all terms$a_{n \gt 1} \gt \frac1{2n}$and the series diverges. After @Cameron Williams has shown, that even$a_n \gt {1\over \sqrt{\pi} n} \approx {1\over 1.7724} \frac1n $I used regression to find an even tighter estimate for the$a_n$in relation to the harmonic numbers. If I did not have a stupid bug with this I found something like $$p_n ^2 \gt -0.317894293187 +1.27323781105n \approx {4n-1\over \pi} \\ \implies a_n \gt \sqrt{\small {4n-1\over \pi }} \cdot \frac1n$$ (The estimate${4n-1\over \pi}$is due to the comments of @Claude Leibovici) • Glad you fixed a minor typo in the last formula. By the way, did you notice that$1.27323781105\approx \frac 4 \pi$the quare root of which being the first term in the asymptotics I wrote in my update ? CHeers. – Claude Leibovici Aug 13 '16 at 2:53 • Hi @Claude - when I tried the W|A-facility for number-guessing it didn't find something trustworthy, so thanks for your hint! Do you have an idea about the -0.31789 - number? – Gottfried Helms Aug 13 '16 at 6:08 • It looks like$-\frac 1 \pi$! – Claude Leibovici Aug 13 '16 at 7:53 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.$• It is obvious that$\sqrt {1+1/n}<1+1/2n$for any positive real$n$. It is also useful to know that$\sqrt {1+1/n}>1+1/(n+1/2)$for any positive real$n$, which for$n\in \mathbb N$is equivalent to$B_{n+1}/B_n=[(2n+1)/(2n+2)]\sqrt {(n+1)/n}>1.$– DanielWainfleet Aug 10 '16 at 18:22 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}\$.