Math Challenge - June 2021

  • #1
15,782
14,096
Summary: Lie algebras, Hölder continuity, gases, permutation groups, coding theory, fractals, harmonic numbers, stochastic, number theory.



1. Let ##\mathcal{D}_N:=\left\{x^n \dfrac{d}{dx},|\,\mathbb{Z}\ni n\geq N\right\}## be a set of linear operators on smooth real functions. For which values of ##N\in\mathbb{Z}\cup\{\pm \infty \}## do they generate a real Lie algebra and are there isomorphic ones among them? Note that any linear combination of basis vectors has only finitely many nonzero coefficients.


2. Let ##c\in (0,1)##. Show that the function ##f:[0,c]\longrightarrow \mathbb{R}##
$$
f(x)=\begin{cases} -\dfrac{1}{\log x}&\text{ if }0< x \leq c \\ 0&\text{ if }x=0\end{cases}
$$
is uniformly continuous, but not Hölder continuous.


3. Consider the equation ##pV-C(A-B\sqrt{p}+T)=0## where ##A,B,C## are constant parameters, ##p=p(T,V)## vapor pressure, ##V=V(T,p)## molar volume, and ##T=T(p,V)## absolute temperature. Prove by three different methods that
$$
\left(\dfrac{\partial V}{\partial T}\right)_p\cdot \left(\dfrac{\partial T}{\partial p}\right)_V\cdot \left(\dfrac{\partial p}{\partial V}\right)_T=-1
$$

4. Calculate
$$
\left(\dfrac{\partial V}{\partial T}\right)_p\text{ and }\left(\dfrac{\partial V}{\partial p}\right)_T
$$
for ##V=V(T,p)## from the equation of state $$
\left(p+\dfrac{a}{V^2}\right)(V-b)=R\cdot T\,; \,a,b,R>0
$$

5. Let ##\sigma \in \operatorname{Aut}(S_n)## be an automorphism of the symmetric group ##S_n\;(n\geq 4)## such that ##\sigma ## sends transpositions to transpositions, then prove that ##\sigma ## is an inner automorphism. Determine the inner automorphism groups of the symmetric and the alternating groups for ##n\geq 4.##


6. Consider a code ##C\subseteq \mathbb{F}_q^n## with minimal Hamming distance ##d>n\cdot \dfrac{q-1}{q}##.
Prove that the number of possible codewords is restricted by
$$
c:=\#C\leq \dfrac{d}{d-n \cdot \dfrac{q-1}{q}}
$$

7. Prove that the Cantor dust on the real line contains uncountable infinitely many points and that it is a fractal by calculating its Hausdorff-Besicovitch dimension.
Cantor_Dust.png



8. Define the harmonic number ##H(p)=1+\dfrac{1}{2}+\dfrac{1}{3}+\ldots +\dfrac{1}{p-1}=\dfrac{a}{b}.##
Show that ##p^2\,|\,a## for primes ##p>3##.


9. An ideal coin is thrown three times in a row and then an ideal dice is thrown twice in a row. Each time you toss a coin you get one point if the coin shows "tails" and two points if the coin shows "heads". If you add the total of the two dice rolls to this number of points, you get the total number of points. Furthermore, let A be the event "the total number of points achieved is odd", B be the event "the total of the two dice rolls is divisible by 5", and C the event "the number of points achieved in the three coin tosses is at least 5". Investigate whether A, B, C are pairwise stochastically independent. Also investigate whether A, B, C are stochastically independent.


10. Show
$$
C_n :=\binom{2n}{n}-\binom{2n}{n+1}=\prod_{k=1}^n \dfrac{4k-2}{k+1}
$$
and determine all primes in ##\{C_n\}.##




1606835746499-png-png-png-png-png.png


High Schoolers only (until 26th)



11.
Check whether there is a natural number ##n\in\mathbb{N}## such that ##\sqrt{n}+\sqrt{n+4}\in\mathbb{Q}.## Note that zero is no natural number.


12. Assume that ##n\in \mathbb{N}## is odd, and ##\{a_1,a_2,\ldots a_n\}=\{1,2,\ldots,n\}.##
Prove that
$$
(a_1-1)\cdot(a_2-2)\cdot \ldots \cdot (a_{n-1}-(n-1))\cdot (a_n-n)
$$
is always even.


13. Show that for every natural number ##n\in \mathbb{N}## there is a ##c=c(n)\in\mathbb{R}## such that for all real numbers ##a>0##
$$
a+a^2+a^3+\ldots +a^{2n-1}+a^{2n} \leq c(n)\cdot \left(1+a^{2n+1}\right).
$$
Show that there is a smallest solution among all possible values ##c(n)## and determine it.


14. Given an integer ##k,## determine all pairs ##(x,y)\in \mathbb{Z}^2## such that
$$
x^2+k\cdot y^2=4 \text{ and }k\cdot x^2 - y^2 =2
$$

15. Prove for every natural number ##n\in \mathbb{N}##
$$
\dfrac{1\cdot 3\cdot 5 \cdot \ldots \cdot (2n-1)}{2\cdot 4 \cdot 6\cdot \ldots \cdot 2n}< \dfrac{1}{\sqrt{2n+1}}
$$
 

Answers and Replies

  • #3
218
27
$$\sqrt{n}+\sqrt{n+4}\in\mathbb{Q}$$
Let ##n=a^2## and ##n+4=b^2## where ##a,b\in\mathbb{Q}##
on putting the value of ##n## we get,
$$a^2+2^2=b^2$$
that means ##a,2,b## are pythagorean triplets, but we know that no such triplet is possible with 2,
Thus, there isn't a natural number ##n## for which ##\sqrt{n}+\sqrt{n+4}\in\mathbb{Q}.##
$$(a_1-1)\cdot(a_2-2)\cdot \ldots \cdot (a_{n-1}-(n-1))\cdot (a_n-n)$$
As we can see that the above expression is odd only when all the terms are odd,

And we know that for every term say, ##(a_i-i)## (where ##i## is an odd number), the value of ##a_i## should be even to make ##(a_i-i)## odd

So, ##\{a_i\}=\{2,4,\ldots,(n-1)\}##

Similarly, for every term, ##(a_j-j)## (where ##j## is an even number), the value of ##a_j## should be odd,

So, ##\{a_j\}=\{1,3,\ldots,(n)\}##

Now we can see that total number of terms of the type ##(a_i-i)## in the expression ##(a_1-1)\cdot(a_2-2)\cdot \ldots \cdot (a_{n-1}-(n-1))\cdot (a_n-n)## is ##\frac {(n+1)} {2}##, but the possible values of ##\{a_i\}=\{2,4,\ldots,(n-1)\}## is only ##\frac {(n-1)} {2}##

So, clearly we have to put one value of ##a_i## as odd, which will make ##(a_i-i)## even

That is why the expression,$$(a_1-1)\cdot(a_2-2)\cdot \ldots \cdot (a_{n-1}-(n-1))\cdot (a_n-n)$$
is always even
From the expression,$$k\cdot x^2 - y^2 =2$$
We can clearly see that ##k>0##

Now from, $$x^2+k\cdot y^2=4$$
We see that ##x,y<2## (as ##k## is a positive integer) And the question states that ##(x,y)\in \mathbb{Z}^2##

So, the only possible value of ##x## & ##y## should be ##x=y=1## which will give ##k=3##
 
Last edited:
  • #4
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,783
758
For 11, you assumed that ##\sqrt{n}## and ##\sqrt{n+4}\in \mathbb{Q}##. What if they are two irrational numbers that happen to add up to a rational number?

I'll take a look at the others later today.
 
  • #5
218
27
For 11, you assumed that ##\sqrt{n}## and ##\sqrt{n+4}\in \mathbb{Q}##. What if they are two irrational numbers that happen to add up to a rational number?

I'll take a look at the others later today.
if ##\sqrt n## and ##\sqrt {n+4}## were irrational but add up to a rational then they must be of the form, ##a+\sqrt b##
And if a number ##\sqrt c## was of the form ##a+\sqrt b## then we can write, (##a,b,c## are rational numbers)
$$\begin{align}
a+\sqrt b=\sqrt c\nonumber\\
a^2+b+2a\sqrt b=c\nonumber\\
\sqrt b=\frac {c-a^2-b} {2a}\nonumber
\end{align}$$
We can see that LHS is irrational but RHS is not, so, contradiction!

Edit: I noticed that I should simply say that if ##\sqrt a +\sqrt b=c## then on squaring both sides we reach contradiction by the same logic
 
Last edited:
  • #6
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,783
758
Sorry, when you say "they" must be in the form you specified, can you clarify what they are, and why they must be in that form?

It seems pretty straightforward that ##a+\sqrt{b}=\sqrt{c}## can be satisfied by ##a=0## and ##b=c## so I'm not sure what the final contradiction is.
 
  • #7
333
191
Problem #4
This is Van der Wall's correction to the ideal gas law for a gas of high density.
For
$$
\left (\frac{\partial V}{\partial T}\right )_p=\frac{1}{\left (\frac{\partial T}{\partial V}\right )_p}
$$
write
$$
T=\frac{(p + \frac{a}{V^2})-\frac{2a}{v^2}(V-b))}{R}
$$
Differentiating w.r.t. ##V## and omitting some algebra we find
$$
\left (\frac{\partial T}{\partial V}\right )_p=\frac{ pV^3-Va +2ab}{V^3R}
$$
and thus
$$
\left (\frac{\partial V}{\partial T}\right )_p=\frac{V^3R }{pV^3-Va +2ab}

$$
For
$$
\left (\frac{\partial V}{\partial p}\right )_T=\frac{1}{\left (\frac{\partial p}{\partial V}\right )_T}
$$
write
$$
p=\frac{RT}{(V-b)}-\frac{a}{V^2}
$$
Differentiating w.r.t.##V##
$$
\left (\frac{\partial p}{\partial V}\right )_T=\frac{2a(V-b)^2-V^3 RT}{V^3 (V-b)^2}
$$
and thus
$$
\left (\frac{\partial V}{\partial p}\right )_T=\frac{V^3 (V-b)^2}{2a(V-b)^2-V^3 RT}

$$
 
  • #8
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,783
758
$$(a_1-1)\cdot(a_2-2)\cdot \ldots \cdot (a_{n-1}-(n-1))\cdot (a_n-n)$$
As we can see that the above expression is odd only when all the terms are odd,

And we know that for every term say, ##(a_i-i)## (where ##i## is an odd number), the value of ##a_i## should be even to make ##(a_i-i)## odd

So, ##\{a_i\}=\{2,4,\ldots,(n-1)\}##

Similarly, for every term, ##(a_j-j)## (where ##j## is an even number), the value of ##a_j## should be odd,

So, ##\{a_j\}=\{1,3,\ldots,(n)\}##

Now we can see that total number of terms of the type ##(a_i-i)## in the expression ##(a_1-1)\cdot(a_2-2)\cdot \ldots \cdot (a_{n-1}-(n-1))\cdot (a_n-n)## is ##\frac {(n+1)} {2}##, but the possible values of ##\{a_i\}=\{2,4,\ldots,(n-1)\}## is only ##\frac {(n-1)} {2}##

So, clearly we have to put one value of ##a_i## as odd, which will make ##(a_i-i)## even

That is why the expression,$$(a_1-1)\cdot(a_2-2)\cdot \ldots \cdot (a_{n-1}-(n-1))\cdot (a_n-n)$$
is always even
I find using i vs j to distinguish even vs odd indices to be a bit confusing, but this looks right.

From the expression,$$k\cdot x^2 - y^2 =2$$
We can clearly see that ##k>0##

Now from, $$x^2+k\cdot y^2=4$$
We see that ##x,y<2## (as ##k## is a positive integer) And the question states that ##(x,y)\in \mathbb{Z}^2##

So, the only possible value of ##x## & ##y## should be ##x=y=1## which will give ##k=3##
From just the equation ##x^2+ky^2=4##, I think you could have ##x=0, k=1## and ##y=2##? Obviously that's excluded by checking that first equation again but I think you threw out too much at once. Also, don't forget x and y can be negative too!

Fred, I'll check your solution to #4 tomorrow.
 
  • #9
218
27
Sorry, when you say "they" must be in the form you specified, can you clarify what they are, and why they must be in that form?

It seems pretty straightforward that ##a+\sqrt{b}=\sqrt{c}## can be satisfied by ##a=0## and ##b=c## so I'm not sure what the final contradiction is.
##a,b,c## were rational numbers which are not perfect squares (because ##\sqrt{b},\sqrt{c}## are irrational numbers), e.g., ##2+\sqrt 3## and yes ##a=0## and ##b=c## will satisfy ##a+\sqrt{b}=\sqrt{c}## I forgot about that case (the question forbids this case anyway), but the whole thing was meant to prove that ##\sqrt b+\sqrt c## (##b,c## are not perfect squares) will not add up to a rational number.

Because as you said,
What if they are two irrational numbers that happen to add up to a rational number?
I just wanted to show why in this particular question, two irrationals will not add up to a rational number.
 
Last edited:
  • #10
218
27
Also, don't forget x and y can be negative too!
I thought that ##(x,y)\in \mathbb{Z}^2## means that ##x,y## are squares of an integer? Because otherwise the question would have simply said that ##(x,y)\in \mathbb{Z}##. What is meant by ##\mathbb{Z}^2##??
 
  • #11
218
27
I thought that ##(x,y)\in \mathbb{Z}^2## means that ##x,y## are squares of an integer? Because otherwise the question would have simply said that ##(x,y)\in \mathbb{Z}##. What is meant by ##\mathbb{Z}^2##??
If ##(x,y)\in \mathbb{Z}##, then the value of ##k## still remains 3, and all possible ordered pairs of ##(x,y)## will be, ##(-1,-1);(-1,1);(1,-1);(1,1)## because ##(x^2,y^2)<4## should still hold true.
 
  • #12
218
27
From just the equation ##x^2+ky^2=4##, I think you could have ##x=0,k=1## and ##y=2##?
From the first equation ##kx^2-y^2=2##, we must have ##x,y\neq 0##
I missed to write that in my attempt.
 
  • #13
kith
Science Advisor
1,397
491
I thought that ##(x,y)\in \mathbb{Z}^2## means that ##x,y## are squares of an integer?
No, ##\mathbb{Z}^2## is a Cartesian product. A very common example of this notation is ##\mathbb{R}^3## for ordinary three-dimensional Euclidean space.
 
  • #14
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,783
758
Edit: I noticed that I should simply say that if ##\sqrt a +\sqrt b=c## then on squaring both sides we reach contradiction by the same logic

I just noticed this edit. I think this is the right direction, could you write up a nice solution for the other readers of this thread?

Fred, your solution to #4 looks good to me. The answer guide has a very different looking answer (computed a different way), but it's basically just substituting RT in your denominator.
 
  • #15
218
27
Problem 12

Let ##\sqrt{n}## and ##\sqrt{n+4}\not\in\mathbb{Q}##, but ##\sqrt{n}+\sqrt{n+4}\in\mathbb{Q}##

So, we can write,
$$\begin{align}
\sqrt{n}+\sqrt{n+4}&=b \space \text{(where b is a rational number)}\nonumber\\
n+n+4+2\sqrt{n}\cdot\sqrt{n+4}&=b^2\nonumber\\
\sqrt{n}\cdot\sqrt{n+4}&=\frac {b^2} {2}-n-2\nonumber\\
\end{align}$$
We see that L.H.S is a irrational number (as ##\sqrt{n}## and ##\sqrt{n+4}\not\in\mathbb{Q}##) but R.H.S is a rational number. Which is a contradiction.

##\therefore\sqrt{n}## and ##\sqrt{n+4}\in\mathbb{Q}##
##\therefore\sqrt{n}=a## and ##\sqrt{n+4}=b## where ##a,b\in\mathbb{Q}##

From these we get, ##a^2+2^2=b^2## which means that ##a,b,2## must be pythagorean triplets, but no such triplet is possible with 2. Which is again a contradiction.

Hence we see that ##\sqrt{n}+\sqrt{n+4}\not\in\mathbb{Q}## where ##n\in\mathbb{N}##
 
  • #16
218
27
No, ##\mathbb{Z}^2## is a Cartesian product. A very common example of this notation is ##\mathbb{R}^3## for ordinary three-dimensional Euclidean space.
Can you please explain to me the difference between writing ##(x,y)\in\mathbb{Z}^2## and ##x,y\in\mathbb{Z}##. Do both notations mean the same thing, i.e., ##x## and ##y## are integers?

Is it that because when we are writing ##(x,y)## and not simply ##x,y## then we mean that ##x## and ##y## are the coordinates of a point in x-y plane and not simply two variable numbers?

But then why in problem 14 ##(x,y)## have to be the coordinates of a point and not simply two numbers?
 
  • #17
218
27
Problem 13
$$a+a^2+a^3+\ldots +a^{2n-1}+a^{2n} \leq c(n)\cdot \left(1+a^{2n+1}\right)$$
For the smallest solution of ##c(n)##, the above equality must hold
$$\begin{align}
a+a^2+a^3+\ldots +a^{2n-1}+a^{2n}&=c(n)\cdot \left(1+a^{2n+1}\right)\nonumber\\
\sum_{r=0}^{2n} a^{2n-r}&=c(n)\cdot \left(1+a^{2n+1}\right)\nonumber\\
\sum_{r=0}^{2n} 2a^{2n-r}\cdot \ln a&=c'(n)\cdot \left(1+a^{2n+1}\right)+2c(n)\cdot a^{2n+1}\cdot \ln a\nonumber\\
2\ln a\cdot \sum_{r=0}^{2n} a^{2n-r}\cdot &=c'(n)\cdot \left(1+a^{2n+1}\right)+2c(n)\cdot a^{2n+1}\cdot \ln a\nonumber\\
2\ln a\cdot c(n)\cdot \left(1+a^{2n+1}\right)&=c'(n)\cdot \left(1+a^{2n+1}\right)+2c(n)\cdot a^{2n+1}\cdot \ln a\nonumber\\
2\ln a\cdot c(n)\cdot \left(1+a^{2n+1}-a^{2n+1}\right)&=c'(n)\cdot \left(1+a^{2n+1}\right)\nonumber\\
\frac {2\ln a\cdot c(n)}{\left(1+a^{2n+1}\right)}&=c'(n)\nonumber
\end{align}$$
For ##c'(n)=0##, ##a## must be 1, hence we get,
$$c(n)=n$$
This should be the smallest solution of ##c(n)## for which,
$$a+a^2+a^3+\ldots +a^{2n-1}+a^{2n} \leq c(n)\cdot \left(1+a^{2n+1}\right)$$
is true for all real numbers ##a>0##
 
  • #18
julian
Gold Member
661
149
Problem #10:

\begin{align*}
C_n & = \frac{(2n)!}{n! n!} - \frac{(2n)!}{(n+1)! (n-1)!}
\nonumber \\
& = \frac{1}{(n+1)!} \left[ \frac{(2n)!}{n!} (n+1) - \frac{(2n)!}{n!} n \right]
\nonumber \\
& = \frac{1}{(n+1)!} \cdot \frac{(2n)!}{n!}
\end{align*}

It is easy to prove that ##(2n)! / n! = \prod_{k=1}^n (4k - 2) \equiv 2^n \prod_{k=1}^n (2k - 1)##:

\begin{align*}
\frac{(2n)!}{n!} & = \frac{2n (2n - 1) (2n-2) \cdots 2 \cdot 1}{n!}
\nonumber \\
& = 2^n (2n - 1) (2n -3) \cdots 1 .
\end{align*}

So altogether we have:

\begin{align*}
C_n & = \frac{1}{(n+1)!} \cdot \frac{(2n)!}{n!}
\nonumber \\
& = \prod_{k=1}^n \frac{4k - 2}{k + 1} .
\end{align*}

For ##C_2##:

\begin{align*}
C_2 & = \prod_{k=1}^n \frac{2}{2} \cdot \frac{6}{3} = 2 .
\end{align*}

For ##C_3##:

\begin{align*}
C_3 & = \prod_{k=1}^n \frac{2}{2} \cdot \frac{6}{3} \cdot \frac{10}{4} = 5 .
\end{align*}

These are the only primes, there are no more prime after this, which we now proceed to prove. In the following we take ##n > 3##. The ##C_n## are obviously integers by the initial formula. We have that

\begin{align*}
C_n = \frac{(2n)!}{(n + 1)! n!}
\end{align*}

or

\begin{align*}
(n+1)! n! C_n = (2n)!
\end{align*}

If ##C_n## were a prime it would have to divide an individual integer on the RHS. Also, as 2 is the only even prime number, if ##C_n## were a prime number it couldn't be equal to ##2n##. Therefore, if ##C_n## were prime then ##C_n \leq 2n -1##. If we can show that ##C_n > 2n - 1## for ##n > 3## we will have proved the result. So we consider:

\begin{align*}
\frac{(2n)!}{(n+1)! n!} > 2n - 1
\end{align*}

which can be rewritten as:

\begin{align*}
(2n) (2n-1) (2n-2)! > n (2n - 1) [(n-1)! (n+1)!]
\end{align*}

Dividing out ##n (2n - 1)## gives:

\begin{align*}
2 (2n-2)! > (n-1)! (n+1)!
\end{align*}

We prove this by induction. The base case is ##n = 4##:

\begin{align*}
2 \cdot 6! = 1440 > 720 = 3! 5!
\end{align*}

We suppose the inequality holds for ##n## and demonstrate that holds for ##n + 1##. We are aiming to prove:

\begin{align*}
2 (2n)! > (n)! (n+2)!
\end{align*}

or

\begin{align*}
(2n) (2n - 1) \cdot 2 (2n - 2)! > n (n + 2) \cdot (n - 1)! (n+1)!
\end{align*}

This follows from

\begin{align*}
(2n) (2n - 1) = n (4n - 2) = n (n + 2) + n (3n - 4) > n (n + 2) \quad \text{for } n > 3
\end{align*}

and the inductive hypothesis. Proving the result.

(Edit note: I could have deduced that if ##C_n## were prime then ##C_n \leq 2n - 1## from ##(n + 1)! C_n = 2^n \prod_{k=1} (2k - 1)## but that is a minor point).

 
Last edited:
  • #19
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,783
758
Can you please explain to me the difference between writing ##(x,y)\in\mathbb{Z}^2## and ##x,y\in\mathbb{Z}##. Do both notations mean the same thing, i.e., ##x## and ##y## are integers?

Is it that because when we are writing ##(x,y)## and not simply ##x,y## then we mean that ##x## and ##y## are the coordinates of a point in x-y plane and not simply two variable numbers?

But then why in problem 14 ##(x,y)## have to be the coordinates of a point and not simply two numbers?

This notation basically means the same thing, and I think you are overthinking things a bit. But it's an important notion in math that functions take one thing as an input, and give one thing as the output. So ##f(x,y)=x^2-y^2## you could think of as a function that takes two inputs and gives one output, but it turns out to be a lot more powerful when you think of it as taking one input, a point ##(x,y)\in \mathbb{R}^2##. This lets you talk about sets of inputs, which lets you start to talk about the topology of the domain etc. If you are stuck thinking of x and y as separate numbers that don't form a single object, it becomes a lot harder to talk about important concepts we care about.

I think for problem 12 we are still missing something. The product of two irrational numbers can be rational. For example ##\sqrt{2}\sqrt{8}=4##.

I'll take a look at the solutions to 10 and 13 tomorrow.
 
  • #20
218
27
Problem 12 (second third attempt)

Let ##\sqrt{n}## and ##\sqrt{n+4}\not\in\mathbb{Q}##, but ##\sqrt{n}+\sqrt{n+4}\in\mathbb{Q}##

So, we can write,
$$\begin{align}
\sqrt{n}+\sqrt{n+4}&=m \space \text{(where m is a rational number)}\nonumber\\
n+n+4+2\sqrt{n}\cdot\sqrt{n+4}&=m^2\nonumber\\
\sqrt{n}\cdot\sqrt{n+4}&=\frac {m^2} {2}-n-2\nonumber\\
\end{align}$$
We see that if L.H.S were to be equal to R.H.S then ##\sqrt{n}\cdot\sqrt{n+4}## must be a rational number. That would mean that,
$$\begin{align}
\sqrt{n}\cdot\sqrt{n+4}&=c \space \text{(where c is a rational number)}\nonumber\\
n(n+4)&=c^2\nonumber\\
n^2+4n-c^2&=0\nonumber\\
n=&\frac {-4 \pm \sqrt{16 +4c^2}} {2}\nonumber\\
n=&-2+ \sqrt{4+c^2} \space \text{(rejecting the negative sign as n>0)}\nonumber
\end{align}$$
But, as ##n## is a natural number, so, ##\sqrt{4+c^2}\in\mathbb{Q}##, which gives ##2^2+c^2=k^2## (##k\in\mathbb{Q}##) which means that $$c^2=(k-2)(k+2)$$ Only way this is possible is when ##c=(k-2)=(k+2)## or ##c=0, k=2## which gives ##c=0## but if ##c## is 0 then ##n## is 0 which is not possible.

##\therefore\sqrt{n}## and ##\sqrt{n+4}\in\mathbb{Q}##
##\therefore\sqrt{n}=a## and ##\sqrt{n+4}=b## where ##a,b\in\mathbb{Q}##

From these we get, ##a^2+2^2=b^2##, again only solution here is when ##a=n=0## which is not possible as ##n\in\mathbb{N}##

Hence we see that ##\sqrt{n}+\sqrt{n+4}\not\in\mathbb{Q}## where ##n\in\mathbb{N}##
 
Last edited:
  • #21
218
27
Problem 15 (if this attempt is correct then credit goes to @julian )

$$\begin{align}
\dfrac{1\cdot 3\cdot 5 \cdot \ldots \cdot (2n-1)}{2\cdot 4 \cdot 6\cdot \ldots \cdot 2n}< \dfrac{1}{\sqrt{2n+1}}\nonumber\\
\dfrac{1\cdot 2\cdot 3\cdot 4\cdot 5 \cdot \ldots \cdot (2n-1) \cdot2n}{(2\cdot 4 \cdot 6\cdot \ldots \cdot 2n)^2}< \dfrac{1}{\sqrt{2n+1}}\nonumber\\
\dfrac{2n!}{2^{2n}\cdot (1\cdot 2 \cdot 3\cdot \ldots \cdot n)^2}< \dfrac{1}{\sqrt{2n+1}}\nonumber\\
\dfrac{2n!}{2^{2n}\cdot (n!)^2}< \dfrac{1}{\sqrt{2n+1}}\nonumber\\
\dfrac{\binom {2n} n}{2^{2n}}< \dfrac{1}{\sqrt{2n+1}}
\end{align}$$
We see that equation (1) is true for ##n=1##, so, we assume that equation (1) is true for some ##n##, we must now prove that it is true for ##(n+1)## by replacing ##n\rightarrow(n+1)##
$$\begin{align}
\dfrac{\binom {2n+2} {n+1}}{2^{2n+2}}< \dfrac{1}{\sqrt{2n+3}}\nonumber\\
\dfrac{(2n+2)\cdot \binom {2n+1} {n}}{2(n+1)\cdot 2^{2n+1}}< \dfrac{1}{\sqrt{2n+3}}\nonumber\\
\dfrac{\binom {2n+1} {n}}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+3}}\nonumber\\
\dfrac{\binom {2n} {n}}{2^{2n+1}}<\dfrac{\binom {2n+1} {n}}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+3}}< \dfrac{1}{\sqrt{2n+1}}\nonumber\\
\dfrac{\binom {2n} {n}}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+1}}
\end{align}$$
Now from equation (1) we have,
$$\begin{align}
\dfrac{\binom {2n} n}{2^{2n}}< \dfrac{1}{\sqrt{2n+1}}\nonumber\\
\dfrac{\binom {2n} n}{2^{2n+1}}< \dfrac{1}{2\sqrt{2n+1}}< \dfrac{1}{\sqrt{2n+1}}\nonumber\\
\dfrac{\binom {2n} n}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+1}}\nonumber\\
\end{align}$$
Hence, we proved that equation (2) is true if equation (1) is true, i.e.,$$\dfrac{1\cdot 3\cdot 5 \cdot \ldots \cdot (2n-1)}{2\cdot 4 \cdot 6\cdot \ldots \cdot 2n}< \dfrac{1}{\sqrt{2n+1}}$$ for every natural number ##n\in \mathbb{N}##
 
Last edited:
  • #22
julian
Gold Member
661
149
Hi @kshitij. It doesn't follow from

\begin{align*}
\frac{\binom{2n}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+1}}
\end{align*}

that

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}

must be true.

But you are so nearly there. Go back to:

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}

And do what I did - you dont want a line of three "<"'s, you just want one "<" - I don't want to give you too much of a hint! (also, remember to prove the base case as well).
 
  • #23
218
27
Hi @kshitij. It doesn't follow from

\begin{align*}
\frac{\binom{2n}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+1}}
\end{align*}

that

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}

must be true.

But you are so nearly there. Go back to:

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}

And do what I did - you dont want a line of three "<"'s, you just want one "<" - I don't want to give you too much of a hint! (also, remember to prove the base case as well).
Are you talking something like this,
\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}\\
\frac{\binom{2n+1}{n+1}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}\\
\frac{(2n+1)\cdot \binom{2n}{n}}{(n+1)\cdot 2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}
But as,
\begin{align*}
1<\frac {2n+1}{n+1}\\
\frac{\binom{2n}{n}}{2^{2n+1}}<\frac {2n+1}{n+1}\cdot \frac{\binom{2n}{n}}{2^{2n+1}}
\end{align*}
From this I'm again getting the same result,
\begin{align*}
\frac{\binom{2n}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+1}}
\end{align*}
 
  • #24
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,783
758
Looking at the solution to 13 first, I think I'm confused by the first couple steps.

Problem 13
$$a+a^2+a^3+\ldots +a^{2n-1}+a^{2n} \leq c(n)\cdot \left(1+a^{2n+1}\right)$$
For the smallest solution of ##c(n)##, the above equality must hold

This is actually not immediately obvious to me. For example suppose it instead asked to show for all real numbers ##a > 0##, and all ##n\in \mathbb{N}##, show there is some ##c=c(n)## such that ##1+an > 1+c(n)##, and find ##c(n)## which is maximal.
Then ##c(n)=0## is the largest solution, since you can pick ##a## to make ##1+an## arbitrarily close to ##0##. But equality is never achieved, for any ##a>0## and any ##n\geq 1##, we get ##1+an > 1##. Is there something special here that guarantees equality?
\begin{align}
a+a^2+a^3+\ldots +a^{2n-1}+a^{2n}&=c(n)\cdot \left(1+a^{2n+1}\right)\nonumber\\
\sum_{r=0}^{2n} a^{2n-r}&=c(n)\cdot \left(1+a^{2n+1}\right)\nonumber\end{align}
The sum in the first line has ##a## as its lowest degree term, but the sum in the second line on the left has a ##1## I think? I think the right hand side is unchanged but the left hand side you just added 1 to it? (this isn't super crippling, if you add ##1## to the left hand side and still get that it's equal to the right hand side, then that's pretty good, but not obviously minimizing ##c(n)##.

$$\sum_{r=0}^{2n} 2a^{2n-r}\cdot \ln a=c'(n)\cdot \left(1+a^{2n+1}\right)+2c(n)\cdot a^{2n+1}\cdot \ln a$$
I don't understand what happened in this step. Are you trying to differentiate with respect to n? I don't understand what ##c'(n)## is - ##c(n)## only takes values on the natural numbers, so isn't differentiable? Not to mention that I don't know how you differentiate the sum being from ##0## to ##2n##, even if this is kind of handwavy it feels like you need to do something about the fact the bounds are expanding (to take a more rigorous example, ##\frac{d}{dx} \int_{0}^x xt dt \neq \int_{0}^x t dt##, you can't just move the differentiation inside the integral when the bounds include the variable).##


Problem #10:

\begin{align*}
C_n & = \frac{(2n)!}{n! n!} - \frac{(2n)!}{(n+1)! (n-1)!}
\nonumber \\
& = \frac{1}{(n+1)!} \left[ \frac{(2n)!}{n!} (n+1) - \frac{(2n)!}{n!} n \right]
\nonumber \\
& = \frac{1}{(n+1)!} \cdot \frac{(2n)!}{n!}
\end{align*}

It is easy to prove that ##(2n)! / n! = \prod_{k=1}^n (4k - 2) \equiv 2^n \prod_{k=1}^n (2k - 1)##:

\begin{align*}
\frac{(2n)!}{n!} & = \frac{2n (2n - 1) (2n-2) \cdots 2 \cdot 1}{n!}
\nonumber \\
& = 2^n (2n - 1) (2n -3) \cdots 1 .
\end{align*}

So altogether we have:

\begin{align*}
C_n & = \frac{1}{(n+1)!} \cdot \frac{(2n)!}{n!}
\nonumber \\
& = \prod_{k=1}^n \frac{4k - 2}{k + 1} .
\end{align*}

For ##C_2##:

\begin{align*}
C_2 & = \prod_{k=1}^n \frac{2}{2} \cdot \frac{6}{3} = 2 .
\end{align*}

For ##C_3##:

\begin{align*}
C_3 & = \prod_{k=1}^n \frac{2}{2} \cdot \frac{6}{3} \cdot \frac{10}{4} = 5 .
\end{align*}

These are the only primes, there are no more prime after this, which we now proceed to prove. In the following we take ##n > 3##. The ##C_n## are obviously integers by the initial formula. We have that

\begin{align*}
C_n = \frac{(2n)!}{(n + 1)! n!}
\end{align*}

or

\begin{align*}
(n+1)! n! C_n = (2n)!
\end{align*}

If ##C_n## were a prime it would have to divide an individual integer on the RHS. Also, as 2 is the only even prime number, if ##C_n## were a prime number it couldn't be equal to ##2n##. Therefore, if ##C_n## were prime then ##C_n \leq 2n -1##. If we can show that ##C_n > 2n - 1## for ##n > 3## we will have proved the result. So we consider:

\begin{align*}
\frac{(2n)!}{(n+1)! n!} > 2n - 1
\end{align*}

which can be rewritten as:

\begin{align*}
(2n) (2n-1) (2n-2)! > n (2n - 1) [(n-1)! (n+1)!]
\end{align*}

Dividing out ##n (2n - 1)## gives:

\begin{align*}
2 (2n-2)! > (n-1)! (n+1)!
\end{align*}

We prove this by induction. The base case is ##n = 4##:

\begin{align*}
2 \cdot 6! = 1440 > 720 = 3! 5!
\end{align*}

We suppose the inequality holds for ##n## and demonstrate that holds for ##n + 1##. We are aiming to prove:

\begin{align*}
2 (2n)! > (n)! (n+2)!
\end{align*}

or

\begin{align*}
(2n) (2n - 1) \cdot 2 (2n - 2)! > n (n + 2) \cdot (n - 1)! (n+1)!
\end{align*}

This follows from

\begin{align*}
(2n) (2n - 1) = n (4n - 2) = n (n + 2) + n (3n - 4) > n (n + 2) \quad \text{for } n > 3
\end{align*}

and the inductive hypothesis. Proving the result.

(Edit note: I could have deduced that if ##C_n## were prime then ##C_n \leq 2n - 1## from ##(n + 1)! C_n = 2^n \prod_{k=1} (2k - 1)## but that is a minor point).


This looks good to me.

For #15, I agree the solution doesn't look complete yet, but it's not obvious to me immediately what julian is looking for. That said, I always find these kind of problems super confusing and just an uninspired mess of algebra that you hope ends up looking like something useful at the end. That said the results are always super powerful, and I am in awe of people who can figure it out.

@kshitij For #12, when you get to ##c^2=(k-2)(k+2)##, I think you only know that ##k## and ##c## are rational, not integers (or at least, that's all you claimed in your post), so how do you reduce the possible solutions so quickly?
 
Last edited:
  • #25
julian
Gold Member
661
149
Hi @kshitij. So you were assuming that

\begin{align*}
\frac{\binom{2n}{n}}{2^{2n}} < \frac{1}{\sqrt{2n+1}} \qquad (*)
\end{align*}

holds and you wanted to show that it follows that

\begin{align*}
\frac{\binom{2n+2}{n+1}}{2^{2n+2}} < \frac{1}{\sqrt{2n+3}} \qquad (**)
\end{align*}

is true.

You correctly deduced that condition ##(**)## is equivalent to the condition:

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}

Just rewrite this as:

\begin{align*}
\left( \frac{1}{2} \cdot \frac{2n+1}{n+1} \right) \cdot\frac{\binom{2n}{n}}{2^{2n}} < \sqrt{\frac{2n+1}{2n+3}} \cdot \frac{1}{\sqrt{2n+1}} \qquad (***)
\end{align*}

Then all you have to do to demonstrate that this

\begin{align*}
\frac{1}{2} \cdot \frac{2n+1}{n+1} < \sqrt{\frac{2n+1}{2n+3}}
\end{align*}

holds. You can then use this together with the inductive hypothesis ##(*)## to deuce that ##(***)## is in fact correct, which in turn means that ##(**)## is true.
 

Related Threads on Math Challenge - June 2021

  • Last Post
5
Replies
114
Views
3K
Replies
102
Views
4K
Replies
100
Views
2K
Replies
86
Views
6K
Replies
61
Views
2K
Replies
93
Views
3K
Replies
56
Views
4K
  • Last Post
2
Replies
42
Views
1K
  • Sticky
  • Last Post
Replies
15
Views
315
Replies
67
Views
4K
Top