# Math Challenge - March 2020 (Part II)

• Challenge
• Featured
Mentor

## Summary:

This is an extra round of questions, because the ones in part I had been solved so fast. However, we still have some easy ones here. They are from calculus, abstract algebra, algebraic geometry, and topology. (Authors: Infrared - IR; fresh_42 - FR)

## Main Question or Discussion Point

Questions

1.
(solved by @hilbert2 ) Let $\sum_{k=1}^\infty a_k$ be a given convergent series with $|a_{k+1}|\leq |a_k|$ for all $k$. Assume we use a computer to sum its value until the partial sum is closer than $\varepsilon$ to the actual value of the series. Does it make sense to use $|a_n|<\varepsilon$ as a stopping criterion for the loop? Please justify your answer. (FR)

2. (solved by @Antarres ) "Every absolutely convergent series converges." Now why is its proof so complicated, couldn't we just say:
Given an absolute convergent series $\sum_{k=1}^{\infty} |a_k|$ then we have for the sequence $R_n :=\sum_{k=n+1}^\infty a_k$
$$|R_n| = \left|\sum_{k=n+1}^\infty a_k\right| \leq \sum_{k+1}^\infty |a_k|$$
with the remainder of a convergent series on the right, hence a null sequence. Thus $R_n$ is a null sequence, too, and the series is convergent. (FR)

3. (solved by @archaic ) Calculate the limit ($i$ being the imaginary unit): (FR)
$$\lim_{n \to \infty} \operatorname{Arg}\left(\sum_{k=0}^n \dfrac{1}{k+ i }\right)$$

4. Show that there is no odd ($>1$) dimensional real division algebra $D$. (FR)

5. Let $R:=\mathbb{Z}_{(5)}=\left\{\left.{\dfrac{a}{b}}\ \right\vert \ 5\nmid b\right\}$ the ring of rational numbers which don't have a factor $5$ in their denominator, $M\neq \{0\}$ a finitely generated $R-$module, and $I:=\left\{\left.{\dfrac{a}{b}}\in R\ \right\vert \ 25\mid a\right\}\,.$
Prove that $I$ is an ideal contained in the Jacobson radical of $R$ and that $IM\neq M\,.$ The Jacobson radical $J=J(R)$ is defined as the intersection of all maximal ideals. (FR)

Edit: Definition of ideal $I$ corrected to make it one. The mistake didn't affect the central statement.

6. Calculate (FR)
$$\lim_{n \to \infty}\dfrac{\sqrt{n\pi}}{2^{2n}}\cdot \binom{2n}{n}$$
a.) (solved by @Fred Wright ) without using Stirling's formula.
b.) by using Stirling's formula, with accurate remainder terms, i.e. not simply $\sim$.

7. Find the minimal real number $A$ such that if $f:[0,1]\to\mathbb{R}$ is any $C^1$ function satisfying $f(0)=0$ and $\int_0^1 f'(x)^2 dx\leq 1$, then $\int_0^1 f(x) dx\leq A.$ If possible, find a function that gives equality. (IR)

8. (solved by @Antarres ) Let $n$ be a positive integer. Show that $\binom{2n}{n}$ is a multiple of $4$ if and only if $n$ is not a power of $2$. (IR)

9. Show that there are no integer solutions to $x^3=y^2+21.$ (IR)

10. Let $f:S^5\to S^3\times S^2$ be a surjective smooth map. Show that $f$ has critical values on every "slice" $S^3\times\{p\}$ for $p\in S^2.$ (IR)

High Schoolers only

11.
(solved by @Adesh ) Prove that if for $x\in \mathbb{R}-\{0\}$ the number $x+\dfrac{1}{x}$ is an integer, then $x^n+\dfrac{1}{x^n}$ with $n\in \mathbb{N}$ are integers, too.

12. (solved by @Not anonymous ) We define for positive integers $a,b$ the following sequence
$$x_n :=\begin{cases}1 & \text{ if }n=1 \\ ax_{n-1}+b& \text{ if }n>1\end{cases}$$
Show that the sequence contains infinitely many numbers. which are not prime, for any choice of $a,b\,.$

13. (solved by @Not anonymous ) Name a convergent series $\sum_{k=1}^\infty a_k$ with positive $a_k$, where $a_{k+1}/a_k \geq 2$ holds infinitely often.

14. (solved by @Not anonymous ) For natural numbers $1\leq k\leq 2n$ show that
$$\binom{2n+1}{k-1}+\binom{2n+1}{k+1} \geq 2\cdot \dfrac{n+1}{n+2}\cdot \binom{2n+1}{k}$$

15. The year on the Earth-like planet Trappist-1e has $365$ days divided into months of $28,30,31$ days. How many months does its year have and how many months with (i) $28$, (ii) $30$, (iii) $31$ days?

16. (solved by @Not anonymous ) Extra Puzzle. Decrypt the affine encrypted "Ara gtynd hdm hvcrsnd mthvtjph!"

Last edited:

hilbert2
Gold Member
1. Let $\sum_{k=1}^\infty a_k$ be a given convergent series with $|a_{k+1}|\leq |a_k|$ for all $k$. Assume we use a computer to sum its value until the partial sum is closer than $\varepsilon$ to the actual value of the series. Does it make sense to use $|a_n|<\varepsilon$ as a stopping criterion for the loop? Please justify your answer. (FR)
This is only valid if the series $\sum_{k=1}^\infty a_k$ is alternating, i.e. $(\text{sgn }a_k ) * (\text{sgn }a_{k+1}) = -1 \hspace{10pt}\forall \hspace{5pt}k\in\mathbb{N}$.

For instance, the difference of $\sum\limits_{k=0}^{100}\frac{1}{k^2}$ and $\sum\limits_{k=0}^{\infty}\frac{1}{k^2}=\frac{\pi^2}{6}$ is much more than $\frac{1}{100^2}$, as easily checked with Wolfram Alpha.

Question 3:
$$z=\frac{1}{k+i}=\frac{k}{1+k^2}-i\frac{1}{1+k^2}$$
\begin{align*} \lim_{n \to \infty} \mathrm{Arg}\left(\sum_{k=0}^n \dfrac{1}{k+ i }\right)&= \lim_{n \to \infty} \mathrm{Arg}\left(\sum_{k=0}^n \frac{k}{1+k^2}+i\sum_{k=0}^n-\frac{1}{1+k^2}\right)\\ &=\lim_{n \to \infty} \arctan\left(\frac{\sum_{k=0}^n-\frac{1}{1+k^2}}{\sum_{k=0}^n \frac{k}{1+k^2}}\right) \end{align*}
The sum in the denominator diverges:
$$\frac{k}{1+k^2}\underset{\infty}{\sim}\frac{1}{k}$$
The sum in the nominator converges absolutely (I could've gotten the minus outside the sum but eh..):
$$\left|-\frac{1}{1+k^2}\right|=\frac{1}{1+k^2}\underset{\infty}{\sim}\frac{1}{k^2}$$
So the limit inside $\arctan$ is $0$, giving us:
$$\lim_{n \to \infty} \mathrm{Arg}\left(\sum_{k=0}^n \dfrac{1}{k+ i }\right)=0$$

Question 11:
Let $x=2k+r$ where $r\in\{0,\,1\}$ then:
$$x+\frac{1}{x}=\frac{(2k+r)^2+1}{2k+r}$$
If $k\neq0$, then whether $x$ is odd or even would get us to a division between an even and an odd number, so this cannot be the case.
If $k=0$, then we get:
$$x+\frac{1}{x}=\frac{r^2+1}{r}$$
We can see that $r$ cannot be $0$ so $x=1$, and, because $1^n=1$ and $1/1=1$, we have that $x+1/x=x^n+1/x^n$.

Mentor
This is only valid if the series $\sum_{k=1}^\infty a_k$ is alternating, i.e. $(\text{sgn }a_k ) * (\text{sgn }a_{k+1}) = -1 \hspace{10pt}\forall \hspace{5pt}k\in\mathbb{N}$.

For instance, the difference of $\sum\limits_{k=0}^{100}\frac{1}{k^2}$ and $\sum\limits_{k=0}^{\infty}\frac{1}{k^2}=\frac{\pi^2}{6}$ is much more than $\frac{1}{100^2}$, as easily checked with Wolfram Alpha.
One can even find a series to any given constant $C$ such that $|a_N|< \varepsilon$ but $\sum_{k=N+1}^\infty a_k > C$. Do you know an example for this?

Mentor
Question 11:
Let $x=2k+r$ where $r\in\{0,\,1\}$ then:
$$x+\frac{1}{x}=\frac{(2k+r)^2+1}{2k+r}$$
If $k\neq0$, then whether $x$ is odd or even would get us to a division between an even and an odd number, so this cannot be the case.
If $k=0$, then we get:
$$x+\frac{1}{x}=\frac{r^2+1}{r}$$
We can see that $r$ cannot be $0$ so $x=1$, and, because $1^n=1$ and $1/1=1$, we have that $x+1/x=x^n+1/x^n$.
$x$ is supposed to be real number, not necessarily an integer.

Mentor
Question 3:
$$z=\frac{1}{k+i}=\frac{k}{1+k^2}-i\frac{1}{1+k^2}$$
\begin{align*} \lim_{n \to \infty} \mathrm{Arg}\left(\sum_{k=0}^n \dfrac{1}{k+ i }\right)&= \lim_{n \to \infty} \mathrm{Arg}\left(\sum_{k=0}^n \frac{k}{1+k^2}+i\sum_{k=0}^n-\frac{1}{1+k^2}\right)\\ &=\lim_{n \to \infty} \arctan\left(\frac{\sum_{k=0}^n-\frac{1}{1+k^2}}{\sum_{k=0}^n \frac{k}{1+k^2}}\right) \end{align*}
The sum in the denominator diverges:
$$\frac{k}{1+k^2}\underset{\infty}{\sim}\frac{1}{k}$$
The sum in the nominator converges absolutely (I could've gotten the minus outside the sum but eh..):
$$\left|-\frac{1}{1+k^2}\right|=\frac{1}{1+k^2}\underset{\infty}{\sim}\frac{1}{k^2}$$
So the limit inside $\arctan$ is $0$, giving us:
$$\lim_{n \to \infty} \mathrm{Arg}\left(\sum_{k=0}^n \dfrac{1}{k+ i }\right)=0$$
Why are you allowed to swap limit and summation?

Why are you allowed to swap limit and summation?
From my calculus 1 course I know that I can take the limit "inside" the function if that is what you are referring to.

Mentor
From my calculus 1 course I know that I can take the limit "inside" the function if that is what you are referring to.
Yes, but you cannot always do this. E.g. consider the function $s$ which assigns the sign of a value:
$$s(x) := \begin{cases} 1 &\text{ if }x>0 \\ 0&\text{ if }x=0\\ -1&\text{ if }x<0\end{cases}$$
and the sequence defined by $a_n:=(-1)^n\cdot \frac{1}{n}$. Then $\lim_{n \to \infty} s(a_n)\neq s(\lim_{n \to \infty}a_n)$

Yes, but you cannot always do this. E.g. consider the function $s$ which assigns the sign of a value:
$$s(x) := \begin{cases} 1 &\text{ if }x>0 \\ 0&\text{ if }x=0\\ -1&\text{ if }x<0\end{cases}$$
and the sequence defined by $a_n:=(-1)^n\cdot \frac{1}{n}$. Then $\lim_{n \to \infty} s(a_n)\neq s(\lim_{n \to \infty}a_n)$
I first thought of the continuity of $\arctan$, then asked elsewhere for a hint, but someone just answered that it was continuity. Well, continuity then.

My attempt at question 11.

Given : $x + \frac{1}{x}$ is an integer.

We want to prove that $x^n + \frac{1}{x^n}$ are integers too for all $n \in \mathbb N$.

Let's do some induction.

Base case: for $n=1$ we have $x^n + \frac{1}{x^n} = x+ \frac{1}{x}$ which is an integer (it's given to be true).

Inductive step : Let's assume that for $n =k$ we have $x^k + \frac{1}{x^k}$ is an integer, (and by Strong induction it is assumed for all values of $n$ less than $k$ we would have $x^n + \frac{1}{x^n}$ as an integer under our assumption, keeping in mind that $n \in \mathbb N$).

$$\left ( x^k + \frac{1}{x^k} \right) \times \left( x + \frac{1}{x}\right) \in \mathbb Z$$ because the product of two integers is always an integer. Let's assume that the above product is equal to some $Z$.

$$x^{k+1} + \frac{1}{x^{k-1}} + x^{k-1} + \frac{1}{x^{k+1}} = Z \\ x^{k+1} + \frac{1}{x^{k+1}} = Z - \left ( x^{k-1} + \frac{ 1} {x^{k-1}} \right)$$ Since, $Z$ is an integer and $x^{k-1} + \frac{1}{x^{k-1}}$ is also an integer by our Strong Induction argument, and difference of two integers is always an integer. Therefore, $$x^{k+1} + \frac{1}{x^{k+1}} \in \mathbb Z$$.
This proves our inductive step.

Hence, $x^n + \frac{1}{x^n}$ are integers for all values of $n \in \mathbb N$.

hilbert2
Gold Member
One can even find a series to any given constant $C$ such that $|a_N|< \varepsilon$ but $\sum_{k=N+1}^\infty a_k > C$. Do you know an example for this?
If it doesn't even have to converge, then multiply the harmonic series with $\epsilon N/2$.

Mentor
If it doesn't even have to converge, then multiply the harmonic series with $\epsilon N/2$.
Of course it has to converge. It is an easy question, so I think the solution should be a bit more detailed than WolframAlpha.

hilbert2
Gold Member
Of course it has to converge. It is an easy question, so I think the solution should be a bit more detailed than WolframAlpha.
Then multiply the harmonic series with that $\epsilon N/2$ and replace the remaining terms with zeroes after the partial sum is greater than $C$. Are the $C$ and $N$ independent or are they functions of one another?

Mentor
I thought of an example like this
$$R_n=\sum_{k=n+1}^{\infty}q^k=\sum_{k=0}^{\infty}q^{k+n+1}=q^{n+1}\sum_{k=0}^{\infty}q^k \approx \dfrac{0.001}{1-q} \stackrel{q\to 1-0}{\longrightarrow} +\infty$$
or a variation of your Wallis series. The goal was to illustrate the situation. We have many high schoolers who read this thread. Giving a trivial example teaches nothing.

Infrared
Gold Member
This is only valid if the series $\sum_{k=1}^\infty a_k$ is alternating, i.e. $(\text{sgn }a_k ) * (\text{sgn }a_{k+1}) = -1 \hspace{10pt}\forall \hspace{5pt}k\in\mathbb{N}$.

For instance, the difference of $\sum\limits_{k=0}^{100}\frac{1}{k^2}$ and $\sum\limits_{k=0}^{\infty}\frac{1}{k^2}=\frac{\pi^2}{6}$ is much more than $\frac{1}{100^2}$, as easily checked with Wolfram Alpha.
You don't even need WA here: the difference between $\sum\limits_{k=0}^{100}\frac{1}{k^2}$ and $\sum\limits_{k=0}^{\infty}\frac{1}{k^2}$ is $\sum_{k=101}^\infty\frac{1}{k^2}>\int_{101}^{\infty}\frac{dx}{x^2}=\frac{1}{101}.$

hilbert2
Gold Member
You don't even need WA here: the difference between $\sum\limits_{k=0}^{100}\frac{1}{k^2}$ and $\sum\limits_{k=0}^{\infty}\frac{1}{k^2}$ is $\sum_{k=101}^\infty\frac{1}{k^2}>\int_{101}^{\infty}\frac{dx}{x^2}=\frac{1}{101}.$
Yeah, and you can even demonstrate the inadequacy of the convergence criterion $|a_n | \leq \epsilon$ by forming a series $\sum\limits_{n=1}^{\infty}a_n$ with terms

$a_n = \left\{\begin{array}{c}\delta,\hspace{30pt}when\hspace{5pt}n<N\\0,\hspace{30pt}when\hspace{5pt}n\geq N\end{array}\right.$

and making the constant $\delta$ small enough and $N$ large enough.

Fun challenge!
We look for integer solutions to

x^3=y^2+21.

We note that if x is even then y must be odd and vice versa.

Case I: Let x=2n, y=2m-1. Then

8n^3 = 4m^2-4m+1+21 \Leftrightarrow 2n^3 = m(m-1)+11/2

which do not have an integer solution.

Case II: Let x=2n-1, y=2m. Then

8n^3-12n^2+6n-1 = 4m^2+21 \Leftrightarrow n(4n^2-6n+3) = 2m^2+11.

The right side is odd. We also have that (4n^2-6n+3) is odd which means that $n$ must also be odd for the equation to be satisfied. Thus set n=2k+1 i.e. x=4k+1. Expanding this gives

512k^3+192k^2+24k+1 = 21 + 4 m^2 \Leftrightarrow 128k^3+48k^2+6k=m^2+11/2,

which do not have an integer solution.

We transform a bit:
$${2n \choose n} = \frac{(2n)!!(2n-1)!!}{(n!)^2} = \frac{2^n(2n-1)!!}{n!}$$
So we want to know which power of 2 divides $n!$, in order to see which power of two divides the expression above, since the double factorial consists only of odd factors.
We can find it by the following algorithm.
If we divide $n$ by 2, and take the floor function of the quotient(for example $\lfloor 2.5\rfloor = 2$), we will get the number of even factors in $n!$. Then if we divide this number further by 2, and take the floor function of the result, we find the number of factors that are divisible by four. We can continue like this until we end up with 1. Sum of the numbers given by this algorithm then provides the total number of factors of 2, in the expression of $n!$, because all numbers before $n$ appear in it, and each step in the algorithm makes sure that every number that is divisible by a higher power of 2 is counted the correct amount of times. This sum is the power of 2 which divides $n!$.
If $n$ is itself a power of 2, this number($N$) will be equal to:
$$n = 2^k \Rightarrow N = \frac{n}{2} + \frac{n}{4} + \dots + \frac{n}{2^k} = 1 + 2 + 4 \dots + 2^{k-1} = 2^k - 1= n-1$$
Therefore, $n! = 2^N * k$, for some odd integer $k$, and we have:`
$${2n \choose n} = \frac{2^n(2n-1)!!}{2^{n-1}k} = 2\frac{(2n-1)!!}{k}$$
This is not divisible by 4, but it is even.
In case $n$ is not a power of 2, then the sum $N$ must be lower than $n-1$, because every step in the algorithm can either give the exact quotient, or a number that is lower than the exact quotient(the exact quotient happens obviously, when the number we're dividing by 2 is even), and if $n$ is not a power of 2, at least once the floor function will return a smaller number than the quotient gotten in the step of the algorithm(this will obviously happen after the step that amounts to dividing $n$ by the highest power of 2 it is divisible with).
Then we take $N = n-m$ in this case, where $m\geq 2$. We find:
$${2n \choose n} = \frac{2^n(2n-1)!!}{2^Nk} = 2^m\frac{(2n-1)!!}{k}$$
Since $m \geq 2$, the above expression is surely divisible by 4. Thus we prove the equivalence that is asked in the exercise.

Last edited:
Infrared
Gold Member
...
The right side is odd. We also have that (4n^2-6n+3) is odd which means that $n$ must also be odd for the equation to be satisfied. Thus set n=2k+1 i.e. x=4k+1
I agree with everything until here. Let me just rephrase your argument in terms of modular arithmetic. If $x$ is even and $y$ is odd, then the LHS is a multiple of $4$ and the RHS is $2$ mod $4$, so it must be the other way around. If $y$ is even, then the LHS is $1$ mod $4$. For $x^3$ to be $1$ mod $4$, we must have that $x$ is $1$ mod $4$. This is the same as your argument but without some of the algebra.

Expanding this gives

512k^3+192k^2+24k+1 = 21 + 4 m^2
How did you get this? If $x=4k+1$, then $x^3=64k^3+48k^2+12k+1$, which is not what you have- it looks like you expanded $(8k+1)^3$ instead..

@Antarres Very nice argument! It looks all correct to me.

Last edited:
How did you get this? If $x=4k+1$, then $x^3=64k^3+48k^2+12k+1$, which is not what you have.
Nicely spotted, thats a factor 4 wrong right there. Actually there is another error on that line, one which together with the other one sadly makes the argument as it is not work anymore. Perhaps I get back to repairing it tomorrow.

I also wrote down your argument with mod 4 in my own words (mostly for my own benefit):
Mod 4 the equation is
$$x^3=y^2+1$$
Mod 4 the values of x^3 can be: 0,1,3 and y^2:0,1. Testing those we see only (x^3,y^2)=(1,0) works.

We conclude that y=2m.
x^3=1 (mod 4) only when x=1 mod 4. Thus x=4n+1. And we arrive at the same point as in the first attempt.

From what I see, the mistake is in the inequality, because in order for it to be applicable for infinite sums, the series under absolute value has to converge, which is what we're trying to prove.

Problem 6
$$\lim_{n\to\infty} \frac{\sqrt{n\pi}}{2^{2n}} \left( \begin{array}{c} 2n \\ n \end{array} \right) =\lim_{n\to\infty}\frac{\sqrt{n\pi}}{2^{2n}}\frac{(2n)!}{(n!)^2} \\$$
I approximate the limit by the "method of steepest descent". First, express $n!$ in terms of the gamma function,$$n!=\int_0^{\infty}x^ne^{-x}dx$$Now make the substitution$y=\frac{x}{n}$,$$n!=n^{n+1}\int_0^{\infty}e^{nf(y)}dy \\ f(y)=ln(y)-y$$I note that $f(y)$ is convex and that multiplying it by large n makes it sharply peaked about its maximum. I expand $f(y)$ two third order about it's maximum ($f'(y)=0$).$$\frac{df(y)}{dy}=\frac{1}{y}-1=0\\$$$y=1$ at the maximum of $f(y)$$$\frac{d^2f(y)}{(dy)^2}=\frac{-1}{y^2}\\ \frac{d^3f(y)}{(dy)^3}=\frac{2}{y^3}\\ f(y)\approx -1 -\frac{1}{2}(y-1)^2 + \frac{1}{3}(y-1)^3\\$$Thus an integral approximation for $n!$,$$n!\approx n^{n+1}e^{-n}\int_0^{\infty}e^{\frac{-n}{2}(y-1)^2 + \frac{n}{3}(y-1)^3}dy$$I approximate the second term to first order in the exponential,$$e^{\frac{n}{3}(y-1)^3}\approx 1+ \frac{n}{3}(y-1)^3\\ n!\approx n^{n+1}e^{-n}\int_0^{\infty}e^{\frac{-n}{2}(y-1)^2}[1+ \frac{n}{3}(y-1)^3]dy$$I make the substitution $u=\sqrt{\frac{n}{2}}(y-1)$ to get,$$n!\approx n^{n+1}e^{-n}\sqrt {\frac{2}{n}}\int_0^{\infty}e^{u^2}[1+\frac{2}{3}\sqrt{\frac{2}{n}}u^3]du$$From the wolfram Gaussian integral page$$\int_0^{\infty}e^{-u^2}du=\sqrt{\pi}\\ \int_0^{\infty}u^3e^{-u^2}du=\frac{1}{2}$$
$$n! \approx n^{n}e^{-n}\sqrt{2\pi n}+ \frac{4}{3}n^ne^{-n}\int_0^{\infty}u^3e^{-u^2}du\\ n!\approx n^{n}e^{-n}[\sqrt{2\pi n} + \frac{2}{3}]\\$$Observe that the first term in the sum is Poisson's approximation and the second term is a first order correction. I write the original expression in its approximate form,
$$\frac{\sqrt{n\pi}}{2^{2n}}\frac{(2n)!}{(n!)^2}\approx \sqrt{\pi n}\frac{(2n)^{2n}e^{-2n}(\sqrt{4\pi n}+\frac{2}{3})}{2^{2n}(n)^{2n}e^{-2n}(\sqrt{2\pi n}+\frac{2}{3})^2}\\ =\sqrt{\pi n}\frac{(\sqrt{4\pi n}+\frac{2}{3})}{(\sqrt{2\pi n}+\frac{2}{3})^2}\\$$
Evaluating the limit by employing l'Hopital's rule,
$$\lim_{n\to\infty}\frac{\sqrt{n\pi}}{2^{2n}}\frac{(2n)!}{(n!)^2}\approx \lim_{n\to\infty}\sqrt{\pi n}\frac{(\sqrt{4\pi n}+\frac{2}{3})}{(\sqrt{2\pi n}+\frac{2}{3})^2}=\frac{1}{2}$$

Cthugha
Question 16:
Hey Jude (well, not literally, but...you know what I mean ;) )

Mentor
Problem 6
$$\lim_{n\to\infty} \frac{\sqrt{n\pi}}{2^{2n}} \left( \begin{array}{c} 2n \\ n \end{array} \right) =\lim_{n\to\infty}\frac{\sqrt{n\pi}}{2^{2n}}\frac{(2n)!}{(n!)^2} \\$$
I approximate the limit by the "method of steepest descent". First, express $n!$ in terms of the gamma function,$$n!=\int_0^{\infty}x^ne^{-x}dx$$Now make the substitution$y=\frac{x}{n}$,$$n!=n^{n+1}\int_0^{\infty}e^{nf(y)}dy \\ f(y)=ln(y)-y$$I note that $f(y)$ is convex and that multiplying it by large n makes it sharply peaked about its maximum. I expand $f(y)$ two third order about it's maximum ($f'(y)=0$).$$\frac{df(y)}{dy}=\frac{1}{y}-1=0\\$$$y=1$ at the maximum of $f(y)$$$\frac{d^2f(y)}{(dy)^2}=\frac{-1}{y^2}\\ \frac{d^3f(y)}{(dy)^3}=\frac{2}{y^3}\\ f(y)\approx -1 -\frac{1}{2}(y-1)^2 + \frac{1}{3}(y-1)^3\\$$Thus an integral approximation for $n!$,$$n!\approx n^{n+1}e^{-n}\int_0^{\infty}e^{\frac{-n}{2}(y-1)^2 + \frac{n}{3}(y-1)^3}dy$$I approximate the second term to first order in the exponential,$$e^{\frac{n}{3}(y-1)^3}\approx 1+ \frac{n}{3}(y-1)^3\\ n!\approx n^{n+1}e^{-n}\int_0^{\infty}e^{\frac{-n}{2}(y-1)^2}[1+ \frac{n}{3}(y-1)^3]dy$$I make the substitution $u=\sqrt{\frac{n}{2}}(y-1)$ to get,$$n!\approx n^{n+1}e^{-n}\sqrt {\frac{2}{n}}\int_0^{\infty}e^{u^2}[1+\frac{2}{3}\sqrt{\frac{2}{n}}u^3]du$$From the wolfram Gaussian integral page$$\int_0^{\infty}e^{-u^2}du=\sqrt{\pi}\\ \int_0^{\infty}u^3e^{-u^2}du=\frac{1}{2}$$
$$n! \approx n^{n}e^{-n}\sqrt{2\pi n}+ \frac{4}{3}n^ne^{-n}\int_0^{\infty}u^3e^{-u^2}du\\ n!\approx n^{n}e^{-n}[\sqrt{2\pi n} + \frac{2}{3}]\\$$Observe that the first term in the sum is Poisson's approximation and the second term is a first order correction. I write the original expression in its approximate form,
$$\frac{\sqrt{n\pi}}{2^{2n}}\frac{(2n)!}{(n!)^2}\approx \sqrt{\pi n}\frac{(2n)^{2n}e^{-2n}(\sqrt{4\pi n}+\frac{2}{3})}{2^{2n}(n)^{2n}e^{-2n}(\sqrt{2\pi n}+\frac{2}{3})^2}\\ =\sqrt{\pi n}\frac{(\sqrt{4\pi n}+\frac{2}{3})}{(\sqrt{2\pi n}+\frac{2}{3})^2}\\$$
Evaluating the limit by employing l'Hopital's rule,
$$\lim_{n\to\infty}\frac{\sqrt{n\pi}}{2^{2n}}\frac{(2n)!}{(n!)^2}\approx \lim_{n\to\infty}\sqrt{\pi n}\frac{(\sqrt{4\pi n}+\frac{2}{3})}{(\sqrt{2\pi n}+\frac{2}{3})^2}=\frac{1}{2}$$
Have you checked with Stirling's formula?

Edit:
Sorry, I first only looked at your result. $\dfrac{1}{2}$ is wrong. However, it isn't your proof which is wrong, but your calculation of the limit:
$$\lim_{n\to\infty}\sqrt{\pi n}\frac{(\sqrt{4\pi n}+\frac{2}{3})}{(\sqrt{2\pi n}+\frac{2}{3})^2}= \lim_{n \to \infty} \dfrac{2\pi n +\frac{2}{3}\sqrt{\pi n}}{2\pi n + \frac{4}{3}\sqrt{2\pi n} +\frac{4}{9}} =\lim_{n \to \infty} \dfrac{2 +\frac{2}{3\sqrt{\pi n}}}{2 + \frac{4\sqrt{2}}{3\sqrt{\pi n}} +\frac{4}{9 \pi n}} = \dfrac{2}{2}=1$$
which is the correct number.

There are easier ways, e.g. with Stirling's formula, although the above solution seems to use the proof of Stirling. However, it can be used directly with appropriate error terms. Another possibility is the use of Wallis' series. So the problem still allows attempts of solutions!

Last edited: