Math Challenge - March 2020 (Part II)

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #1
12,647
9,166

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)


1580532399366-png-png.png



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:

Answers and Replies

  • #2
hilbert2
Science Advisor
Insights Author
Gold Member
1,339
414
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.
 
  • #3
363
85
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$$
 
  • #4
363
85
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##.
 
  • #5
12,647
9,166
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?
 
  • #6
12,647
9,166
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.
 
  • #7
12,647
9,166
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?
 
  • #8
363
85
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.
 
  • #9
12,647
9,166
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)##
 
  • #10
363
85
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.
 
  • #11
344
56
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##.
 
  • #12
hilbert2
Science Advisor
Insights Author
Gold Member
1,339
414
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##.
 
  • #13
12,647
9,166
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.
 
  • #14
hilbert2
Science Advisor
Insights Author
Gold Member
1,339
414
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?
 
  • #15
12,647
9,166
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.
 
  • #16
Infrared
Science Advisor
Gold Member
541
230
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}.##
 
  • #17
hilbert2
Science Advisor
Insights Author
Gold Member
1,339
414
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.
 
  • #18
332
46
Fun challenge!
We look for integer solutions to
\begin{equation}
x^3=y^2+21.
\end{equation}
We note that if x is even then y must be odd and vice versa.

Case I: Let x=2n, y=2m-1. Then
\begin{equation}
8n^3 = 4m^2-4m+1+21 \Leftrightarrow 2n^3 = m(m-1)+11/2
\end{equation}
which do not have an integer solution.

Case II: Let x=2n-1, y=2m. Then
\begin{equation}
8n^3-12n^2+6n-1 = 4m^2+21 \Leftrightarrow n(4n^2-6n+3) = 2m^2+11.
\end{equation}
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
\begin{equation}
512k^3+192k^2+24k+1 = 21 + 4 m^2 \Leftrightarrow 128k^3+48k^2+6k=m^2+11/2,
\end{equation}
which do not have an integer solution.
 
  • #19
148
69
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:
  • #20
Infrared
Science Advisor
Gold Member
541
230
...
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
\begin{equation}
512k^3+192k^2+24k+1 = 21 + 4 m^2
\end{equation}
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:
  • #21
332
46
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
\begin{equation}x^3=y^2+1\end{equation}
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.
 
  • #22
148
69
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.
 
  • #23
202
83
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:biggrin:$$\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}
$$
 
  • #24
Cthugha
Science Advisor
1,918
267
Question 16:
Hey Jude (well, not literally, but...you know what I mean ;) )
 
  • #25
12,647
9,166
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:biggrin:$$\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:

Related Threads on Math Challenge - March 2020 (Part II)

  • Sticky
  • Last Post
4
Replies
77
Views
3K
Replies
107
Views
6K
Replies
64
Views
5K
Replies
97
Views
13K
Replies
6
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
20
Views
7K
Replies
18
Views
2K
Replies
40
Views
10K
Replies
86
Views
12K
Top