Math Challenge - March 2020 (Part II)

[fresh_42]

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. (solved by @wrobel ) 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. (solved by @Not anonymous ) 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!"

 

[hilbert2]

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)

Spoiler

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.

 

[archaic]

Question 3:

Spoiler

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

 

[archaic]

Question 11:

Spoiler

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

 

[fresh_42]

Spoiler

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?

 

[fresh_42]

Question 11:

Spoiler

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.

 

[fresh_42]

Question 3:

Spoiler

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

 

[archaic]

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.

 

[fresh_42]

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

 

[archaic]

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.

 

[Adesh]

My attempt at question 11.

Spoiler

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]

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

 

[fresh_42]

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]

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?

 

[fresh_42]

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]

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]

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.

 

[Incand]

Fun challenge!

Spoiler: Question 9

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.

 

[Antarres]

Spoiler: Question #8

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.

 

[Infrared]

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

 

[Incand]

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, that's 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):

Spoiler

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.

 

[Antarres]

Spoiler: Question #2

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.

 

[Fred Wright]

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:

Spoiler

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

 

[fresh_42]

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!

 

[Not anonymous]

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

Spoiler: Question 12

We can prove by contradiction. We note that all numbers in the sequence are positive integers. Suppose there are some positive integers $a,b$ for which the sequence does not contain infinitely many non-prime numbers, or in other words the sequence has only a finite number of composite integers. Then there must be some integer $k \gt 1$ such that $\forall i \geq k, x_i$ is prime, i.e. all numbers in the subsequence, starting from $x_{k}$ (i.e. $x_{k}, x_{k+1}, ...$) are prime. We proceed to prove that there must be some positive integer $d$ for which $x_{k+d}$ must be a multiple of $x_{k}$ and therefore non-prime, a contradiction to earlier assumption of sequence being primes-only after $x_k$.

It is easy to show that for any positive integer $q$, $x_{k+q} = a^q x_k + b \sum_{i=0}^{q-1} a^{i}$. If $x_{k+q}$ is prime, then $x_{k+q} \neq 0 \mod x_k$. Since the sequence is infinitely long but modulo $x_k$ can take only a finite number of values $(1, .., x_{k}-1)$ (0 not considered because we want all numbers after $x_k$ too to be prime and therefore coprime w.r.t $x_k$), there must be 2 different values of $q$, say $q_1, q_2$ such that $x_{k+q_{2}} \mod x_k = x_{k+q_{1}} \mod x_k$. We may assume without loss of generality that $q_1 \lt q_2$

Therefore, $x_{k+q_{2}} - x_{k+q_{1}} = 0 \mod {x_k} \Rightarrow (a^{q_{2}}-a^{q_{1}})x_k + b \sum_{i=q_{1}}^{q_{2}-1} a^{i} = 0 \mod x_k \\ \Rightarrow b a_{q_{1}} \sum_{i=0}^{q_{2}-q_{1}-1} a^{i} = 0 \mod x_k$. Since $x_k = ax_{k-1}+b$, it must be the case that $1 \leq a, b \lt x_k$ and since $x_k$ is prime, $a \neq 0 \mod x_k$, $b \neq 0 \mod x_k$. Therefore $b a_{q_{1}} \sum_{i=0}^{q_{2}-q_{1}-1} a^{i} = 0 \mod x_k \Rightarrow \sum_{i=0}^{q_{2}-q_{1}-1} a^{i} = 0 \mod x_k$. So if we choose $d=q_{2}-q_{1}$, then $x_{k+d} \mod x_k = (a^d x_k + b \sum_{i=0}^{d-1} a^{i}) \mod {x_k} = 0$, meaning there must be a non-trivial multiple of $x_k$ in the sequence after $x_k$ and that multiple is therefore not prime. Since the initial assumption that the sequence has only primes from and after $x_{k}$ is contradicted for any positive integer values of $a,b$, it follows that there must be an infinite number of non-primes in the sequence.

 

[fresh_42]

Spoiler: Question 12

We can prove by contradiction. We note that all numbers in the sequence are positive integers. Suppose there are some positive integers $a,b$ for which the sequence does not contain infinitely many non-prime numbers, or in other words the sequence has only a finite number of composite integers. Then there must be some integer $k \gt 1$ such that $\forall i \geq k, x_i$ is prime, i.e. all numbers in the subsequence, starting from $x_{k}$ (i.e. $x_{k}, x_{k+1}, ...$) are prime. We proceed to prove that there must be some positive integer $d$ for which $x_{k+d}$ must be a multiple of $x_{k}$ and therefore non-prime, a contradiction to earlier assumption of sequence being primes-only after $x_k$.

It is easy to show that for any positive integer $q$, $x_{k+q} = a^q x_k + b \sum_{i=0}^{q-1} a^{i}$. If $x_{k+q}$ is prime, then $x_{k+q} \neq 0 \mod x_k$. Since the sequence is infinitely long but modulo $x_k$ can take only a finite number of values $(1, .., x_{k}-1)$ (0 not considered because we want all numbers after $x_k$ too to be prime and therefore coprime w.r.t $x_k$), there must be 2 different values of $q$, say $q_1, q_2$ such that $x_{k+q_{2}} \mod x_k = x_{k+q_{1}} \mod x_k$. We may assume without loss of generality that $q_1 \lt q_2$

Therefore, $x_{k+q_{2}} - x_{k+q_{1}} = 0 \mod {x_k} \Rightarrow (a^{q_{2}}-a^{q_{1}})x_k + b \sum_{i=q_{1}}^{q_{2}-1} a^{i} = 0 \mod x_k \\ \Rightarrow b a_{q_{1}} \sum_{i=0}^{q_{2}-q_{1}-1} a^{i} = 0 \mod x_k$. Since $x_k = ax_{k-1}+b$, it must be the case that $1 \leq a, b \lt x_k$ and since $x_k$ is prime, $a \neq 0 \mod x_k$, $b \neq 0 \mod x_k$. Therefore $b a_{q_{1}} \sum_{i=0}^{q_{2}-q_{1}-1} a^{i} = 0 \mod x_k \Rightarrow \sum_{i=0}^{q_{2}-q_{1}-1} a^{i} = 0 \mod x_k$. So if we choose $d=q_{2}-q_{1}$, then $x_{k+d} \mod x_k = (a^d x_k + b \sum_{i=0}^{d-1} a^{i}) \mod {x_k} = 0$, meaning there must be a non-trivial multiple of $x_k$ in the sequence after $x_k$ and that multiple is therefore not prime. Since the initial assumption that the sequence has only primes from and after $x_{k}$ is contradicted for any positive integer values of $a,b$, it follows that there must be an infinite number of non-primes in the sequence.

Well, done. Just a hint: "Since the sequence is infinitely long ..." is better seen by the remark, that the sequence is strictly monotone increasing.

 

[Not anonymous]

16. Extra Puzzle. Decrypt the affine encrypted "Ara gtynd hdm hvcrsnd mthvtjph!"

I think I got the correct decrypted text but I did not solve this puzzle in a mathematical way and also took help from an online tool so this post does not qualify to be considered a solution in any math challenge . I am posting the answer only because I spent some time reading about affine encryption and experimenting with different values for the keys to get the answer. Rote work but at least I managed to make it less rote by using just the 1st word to find the correct encryption keys

Spoiler: Question 16

The decrypted text is "Non vitae sed scholae discimus!", a Latin phrase that I got to know through this puzzle. The encryption keys are $a=17, b=13$ and the affine encryption formula is $f(x) = (ax + b) \mod 26 = (17x + 13) \mod 26$, where $x$ is the numeric position (zero-based) of the letter in the English/Latin alphabetical sequence, i.e. letter a maps to 0, letter b to 1 and so on till letter z mapping to 25.

 

[fresh_42]

I think I got the correct decrypted text but I did not solve this puzzle in a mathematical way and also took help from an online tool so this post does not qualify to be considered a solution in any math challenge . I am posting the answer only because I spent some time reading about affine encryption and experimenting with different values for the keys to get the answer. Rote work but at least I managed to make it less rote by using just the 1st word to find the correct encryption keys

Spoiler: Question 16

The decrypted text is "Non vitae sed scholae discimus!", a Latin phrase that I got to know through this puzzle. The encryption keys are $a=17, b=13$ and the affine encryption formula is $f(x) = (ax + b) \mod 26 = (17x + 13) \mod 26$, where $x$ is the numeric position (zero-based) of the letter in the English/Latin alphabetical sequence, i.e. letter a maps to 0, letter b to 1 and so on till letter z mapping to 25.

I think I used $x \longmapsto 17(x-1)+14$ counting from one, but the answer is correct! Seneca wrote this ("We learn for school not for life!") to a student mocking about the usual version: "We learn for life, not for school!".

 

[Not anonymous]

13. 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.

I am unsure if I understood the question correctly as I haven't studied theory of infinite series (except for introduction to Taylor and Maclaurin series) and convergence. With my limited knowledge on this subject, I think it is not possible for the series $\sum_{k=1}^\infty a_k$ to be convergent if $a_{k+1}/a_k \geq 2$ for all values of $k$ as the sum will then tend to infinity (I think this is particularly obvious when $a_k$ is required to be positive). So I interpret "$a_{k+1}/a_k \geq 2$ holds infinitely often" to mean that there should be an infinite number of non-overlapping pairs $a_k, a_{k+1}$ in the series that meet the condition on lower-bound of ratio. If the expected solution is a "named" series (such as the Maclaurin series expansion of "standard" trigonometric functions and not that of some well-defined but non-standard function such as $2 \sin (x^2 + 1)$) then I haven't found a solution yet.

Spoiler: Question 13

Consider the series whose $a_k$ values are defined as follows:
$$
a_k = \begin{cases}
x^{\frac {k-1} {2}} & \text{if } k \text{ is odd} \\
2x^{\frac {k-2} {2}} & \text{if } k \text{ is even} \\
\end{cases}
$$
where $x \in (0,1)$. All $a_k$ values are positive in this series.

Then, the summation $\sum_{k=1}^\infty a_k$ is equal to $$
S = 1 + 2 + x + 2x + x^2 + 2x^2 + x^3 + 2x^3 +\ldots
= (1 + x + x^2 + x^3 + \ldots) + 2(1 + x + x^2 + x^3 + \ldots)
= 3(1 + x + x^2 + x^3 + \ldots) = \frac {3} {1-x}
$$

The series is therefore convergent and the condition $a_{k+1}/a_k \geq 2$ is met for all odd values of $k$ since all those ratios are of the form $\frac {2x^p} {x^p} = 2$, thus giving an infinite number of pairs of consecutive elements where the condition on ratio is met.

 

[fresh_42]

I am unsure if I understood the question correctly

You did. The example should show that the quotient criterion for convergence and divergence of series needs all its strong restrictions.

 

[StoneTemplePython]

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!

for problem (6a)
there's actually a very nice probabilistic proof of this that completely abstracts away from binomial coefficients and works for just about any symmetric walk on the integers (where position at time n is given by $\sum_{i=1} ^n X_i$ where $X_i$ are iid and symmetric and $E\big[\vert X_i\vert^3 \big]\lt \infty$). The technique uses characteristic functions to get the so called 'local central limit theorem'. I'm pretty sure this is what Polya used to originally prove recurrence of simple random walk in 2-d and transcience in higher dimensions. There's a lot of interlocking parts but I'm going to try to write a high level coherent walk-though without getting bogged down in every detail. It's actually a really nice use of symmetry and basic complex analysis.

 

[mathwonk]

HINT: Re #4, the only solution I know seems a bit sophisticated, and shows further that there is no (finite dimensional) real division algebra whose dimension has an odd factor. I will not give it, in hopes some young person will find an original solution of the problem as asked. But the idea is that for an algebra to be a division algebra, equivalently to have no zero divisors, requires a certain system of homogeneous equations to have no non - zero solution. On the other hand there is a generalization of the basic calculus result that all (non constant) polynomials of odd degree have real solutions, that says that all real systems of n homogeneous polynomials in n+1 variables, in which all equations have odd degree, does have a non zero real solution. Even with this theorem, some clever tweaks are needed to get the result, but maybe the weaker result as asked follows without these tweaks.

 

[Infrared]

@mathwonk There are some easy topological arguments too. A division algebra structure on $\mathbb{R}^n$ gives a topological group structure on the unit sphere $S^{n-1}$ by $a\odot b= ab/|ab|$, and this can only happen in odd dimension by degree considerations.

I can confirm that @fresh_42 has an elementary solution in mind though ;)

 

[Not anonymous]

14. For natural numbers $1\leq k\leq 2n$ show that
$$
{{2n+1}\choose{k−1}} + {{2n+1}\choose{k+1}} ≥ 2⋅\dfrac{n+1} {n+2}⋅ {{2n+1}\choose{k}}
$$

Spoiler: Question 14

Let $S$ denote the sum on LHS of the inequality.
$$
S = {{2n+1}\choose{k−1}} + {{2n+1}\choose{k+1}} = \dfrac{(2n+1)!}{(k-1)!(2n-k+2)!} + \dfrac{(2n+1)!}{(k+1)!(2n-k)!} = \dfrac{(2n+1)!}{k!(2n-k+1)!} . \left( \dfrac{k}{2n-k+2} + \dfrac{2n-k+1}{k+1} \right) \\
= {{2n+1}\choose{k}} . \left( \dfrac{k}{2n-k+2} + \dfrac{2n-k+1}{k+1} \right)
$$

The inequality in the question is therefore equivalent to $s = \dfrac {S}{{2n+1}\choose{k}} \geq 2⋅\dfrac{n+1} {n+2}$

$s = \dfrac {S}{{2n+1}\choose{k}} = \left( \dfrac{k}{2n-k+2} + \dfrac{2n-k+1}{k+1} \right)$

For a fixed value of positive integer $n$, $s$ can be viewed as a function of $k$, i.e. $s(k)$. We may temporarily drop the question's requirement that $k$ be an integer since $s$ is defined for all real values of $k \in [0,2n]$.

$$
\frac {ds}{dk} = \frac{1}{2n-k+2} + \frac{k}{(2n-k+2)^2} - \frac{1}{k+1} - \frac{2n-k+1}{(k+1)^2} = \\
(2n+2) . \left( \frac{1}{(2n-k+2)^2} - \frac{1}{(k+1)^2} \right)
$$

It is easy to see that
$$
\frac {ds}{dk} \text{ is } \begin{cases}\\
= 0 & \text{if } k = n+\frac{1}{2} \\
\lt 0 & \text{if } k < n+\frac{1}{2} \\
\gt 0 & \text{if } k > n+\frac{1}{2} \\
\end{cases}
$$

Therefore, $s$ is strictly decreasing for $0 \leq k \lt (n+\frac{1}{2})$ and strictly increasing for $(n+\frac{1}{2}) \lt k \lt 2n$ and attains it minimum at $k=n+\frac{1}{2}$. This and the fact that $s(k)$ is symmetric around $n+\frac{1}{2}$ (it is easy to see that i.e. $s(k) = s(2n+1-k)$) implies that if we consider only integer values of $k \in [0, 2n]$, $s(k)$ reaches its minimum at $k=n$ and $k=n+1$. This minimum value is $s_{min} = s(n) = \left( \dfrac{n}{n+2} + \dfrac{n+1}{n+1} \right) = \dfrac{2n+2}{n+2} = 2 . \dfrac{n+1}{n+2}$. It follows that $s \geq \dfrac{2n+2}{n+2} = 2 . \dfrac{n+1}{n+2}$ for natural numbers $1 \leq k \leq 2n$ proving the inequality in the question