Math Challenge - June 2021

  • #1
fresh_42
Mentor
Insights Author
2021 Award
17,239
17,223
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
kshitij
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
2021 Award
5,219
1,170
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
kshitij
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
2021 Award
5,219
1,170
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
Fred Wright
362
214
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
2021 Award
5,219
1,170
$$(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
kshitij
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
kshitij
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
kshitij
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
kshitij
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,414
501
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
2021 Award
5,219
1,170
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
kshitij
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
kshitij
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
kshitij
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
699
184
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
2021 Award
5,219
1,170
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
kshitij
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
kshitij
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
699
184
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
kshitij
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
2021 Award
5,219
1,170
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
699
184
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.
 
  • #26
kshitij
218
27
Looking at the solution to 13 first, I think I'm confused by the first couple steps.


This is actually not immediately obvious to me.
My thinking behind writing "for smallest solution... equality holds" was that, suppose we are given
$$x \leq y$$
And we have to find the minimum possible value of ##y## for which the above relation is true for all possible values of ##x## (both ##x,y\in \mathbb{R}## are variables)
Now clearly in this case for every value of ##x## there are infinite values of ##y## but to find the minimum value of ##y## we have to first find the maximum value of ##x## and then we can say that if ##y## is equal to that value of ##x##, then the inequality ##x \leq y## will always be satisfied no matter what value ##x## takes.
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).
Yes, you right, I was horribly wrong there, instead the second line should be,
$$
\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-1} a^{2n-r}&=c(n)\cdot \left(1+a^{2n+1}\right)\nonumber\end{align}
$$
I don't understand what happened in this step. Are you trying to differentiate with respect to n?
Yes, I differentiated both sides w.r.t ##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, ddx∫0xxtdt≠∫0xtdt, you can't just move the differentiation inside the integral when the bounds include the variable)
I didn't think about all these, I just differentiated both sides hoping that everything should be fine but now I feel stupid 😅.

I'll give that problem a second try, but is my first thinking correct? i.e., for the smallest solution of ##c(n)## we first maximize (somehow) the L.H.S, and then equate both sides?
 
  • #27
kshitij
218
27
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.
\begin{align*}
\frac{1}{2} \cdot \frac{2n+1}{n+1} < \sqrt{\frac{2n+1}{2n+3}}
\end{align*}
Now, since both sides are positive, we can square both sides,
\begin{align*}
\frac{1}{4} \cdot \frac{(2n+1)^2}{(n+1)^2} &< {\frac{2n+1}{2n+3}}\\
\frac{1}{4} \cdot \frac{(2n+1)^2}{(n+1)^2} - {\frac{2n+1}{2n+3}}&<0\\
\frac{1}{4} \cdot \frac{(2n+1)^2({2n+3})-4(2n+1)(n+1)^2}{(n+1)^2(2n+3)} &< 0\\
\frac{1}{4} \cdot \frac{(2n+1)\left((2n+1)({2n+3})-4(n+1)^2\right)}{(n+1)^2(2n+3)} &< 0\\
\frac{1}{4} \cdot \frac{(2n+1)\left(4n^2+8n+3-4n^2-8n-4\right)}{(n+1)^2(2n+3)} &< 0\\
\frac{1}{4} \cdot \frac{-(2n+1)}{(n+1)^2(2n+3)} &< 0
\end{align*}
And as ##n>0## the above inequality is hence true.
 
Last edited:
  • #28
kshitij
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}##
@julian can I ask what was the mistake in this attempt (Its not particularly clear to me)?

I think that according to you until here,
$$\dfrac{\binom {2n+1} {n}}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+3}}$$
the above expression is correct, but after that why can't we write,
$$\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}}$$
We know that
$$\binom {2n} {n}<\binom {2n+1} {n}$$
So, why cant we write,
$$\dfrac{\binom {2n} {n}}{2^{2n+1}}<\dfrac{\binom {2n+1} {n}}{2^{2n+1}}$$
Similarly,
$$\dfrac{1}{\sqrt{2n+3}}< \dfrac{1}{\sqrt{2n+1}}$$
So, on combining them we should get,
$$\dfrac{\binom {2n} {n}}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+1}}$$
 
  • #29
kshitij
218
27
@julian can I ask what was the mistake in this attempt (Its not particularly clear to me)?

I think that according to you until here,
$$\dfrac{\binom {2n+1} {n}}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+3}}$$
the above expression is correct, but after that why can't we write,
$$\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}}$$
We know that
$$\binom {2n} {n}<\binom {2n+1} {n}$$
So, why cant we write,
$$\dfrac{\binom {2n} {n}}{2^{2n+1}}<\dfrac{\binom {2n+1} {n}}{2^{2n+1}}$$
Similarly,
$$\dfrac{1}{\sqrt{2n+3}}< \dfrac{1}{\sqrt{2n+1}}$$
So, on combining them we should get,
$$\dfrac{\binom {2n} {n}}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+1}}$$
I though it was like saying if$$a<b$$
And $$b<c$$
Then$$a<c$$
 
  • #30
kshitij
218
27
@kshitij For #12, when you get to c2=(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?
I shouldn't write ##c^2=(k-2)(k+2)## I should have directly wrote that from ##c^2+2^2=k^2## the only solution we get is ##c=0## and ##k=2## (as there are no pythagorean triplets with 2), I was thinking something else when I wrote ##c^2=(k-2)(k+2)##.

I don't like that solution anyway, maybe I can think a better one later.
 
  • #31
julian
Gold Member
699
184
\begin{align*}
\frac{1}{2} \cdot \frac{2n+1}{n+1} < \sqrt{\frac{2n+1}{2n+3}}
\end{align*}
Now, since both sides are positive, we can square both sides,
\begin{align*}
\frac{1}{4} \cdot \frac{(2n+1)^2}{(n+1)^2} &< {\frac{2n+1}{2n+3}}\\
\frac{1}{4} \cdot \frac{(2n+1)^2}{(n+1)^2} - {\frac{2n+1}{2n+3}}&<0\\
\frac{1}{4} \cdot \frac{(2n+1)^2({2n+3})-4(2n+1)(n+1)^2}{(n+1)^2(2n+3)} &< 0\\
\frac{1}{4} \cdot \frac{(2n+1)\left((2n+1)({2n+3})-4(n+1)^2\right)}{(n+1)^2(2n+3)} &< 0\\
\frac{1}{4} \cdot \frac{(2n+1)\left(4n^2+8n+3-4n^2-8n-4\right)}{(n+1)^2(2n+3)} &< 0\\
\frac{1}{4} \cdot \frac{-(2n+1)}{(n+1)^2(2n+3)} &< 0
\end{align*}
And as ##n>0## the above equality is hence true.
Correct, if a bit difficult to read. You used the essential point that ##(2n+1) (2n+3) - 4 (n+1)^2 < 0##.

For clarity you could have written

\begin{align*}
(2n+1) (2n+3) < 4 (n+1)^2
\end{align*}

and then divided both sides by ##4 (n+1)^2 (2n+3)## and multiplied both sides by ##(2n+1)## to obtain

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

and then taken the square root of both sides. But that doesn't really matter.

----------------------------------

Remember to prove the base case! You need to show that

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

holds when ##n = 1##. Once you do that your inductive argument will be complete!

-------------------------------------

I'll answer you other question later on.
 
  • #32
kshitij
218
27
Remember to prove the base case! You need to show that
Sorry, I forgot that,

For ##n=1##
$$\begin{align*}
\frac{\binom{2n}{n}}{2^{2n}} < \frac{1}{\sqrt{2n+1}}\\
\frac{\binom{2}{1}}{2^{2}} < \frac{1}{\sqrt{2+1}}\\
\frac{2}{4}<\frac{1}{\sqrt{2+1}}\\
\frac1 2<\frac{1}{\sqrt3}\\
2>\sqrt3
\end{align*}$$
 
  • #33
julian
Gold Member
699
184
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}}\qquad \qquad \qquad (1) \nonumber\\
\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}}\qquad \qquad \qquad \qquad (2) \nonumber\\
\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}##
Hi @kshitij . Sorry, for the delay. I've been seriously preoccupied.

OK, 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*}

This condition, ##(**)##, is the final statement. You start with the final statement and what you do is you keep making changes that until something comes up, which together with the use ##(*)##, is true. But the changes that you make along the way must result in equivalent conditions so that finally you can write them down in the backward direction and end up with ##(**)##.

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

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

However, you didn't give a valid justificiation as to why the condition:

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

is equivalent to ##(***)##, and so you can't work backwards from ##(****)## to ##(***)##. That's the problem.
 
Last edited:
  • #34
BWV
1,202
1,312
Here is a stab at #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.

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.

T=total = (5:18)

Probabilities:

A = P(odd) =½ (even number of integer outcomes)

B= P(div by 5)=19/96 or 19.8%

coin totalDice total
5​
3​
1/8​
2​
1/36​
4​
3/8​
5​
3/8​
6​
1/8​
Prob=
1/288​
10​
3​
1/8​
7​
1/6​
16.67%​
4​
3/8​
6​
5/36​
13.89%​
5​
3/8​
5​
1/9​
11.11%​
6​
1/8​
4​
1/12​
8.33%​
Prob=
1/8​
15​
3​
1/8​
12​
1/36​
2.78%​
4​
3/8​
11​
1/18​
5.56%​
5​
3/8​
10​
1/12​
8.33%​
6​
1/8​
9​
1/9​
11.11%​
Prob=
5/72​
Total P(div by 5)​
19/96​
19.8%​
C=Pcoin(>=5)= ½ (see B for odds of flips)



Two events independent if P(A∩B)= P(A)P(B) or, alternatively P(A|B)=P(A) and P(B|A)=P(B)

A and B not independent as there are two odd outcomes divisible by 5 and one even

P(B|A)=P(A|B)P(B)/P(A)= (1/288 + 5/72)(1/2)/(1/2) <> P(B)

A and C independent as

P(A)P(C)=1/4 = P(A∩C)=P(A|C)P(C)=1/4

B and C not independent as

P(B∩C)=7/72 (see below) <> P(B)P(C)=19/192

coin totalDice total
5​
2​
1/36​
5​
3/8​
6​
1/8​
Prob=
0​
10​
7​
1/6​
16.67%​
6​
5/36​
13.89%​
5​
3/8​
5​
1/9​
11.11%​
6​
1/8​
4​
1/12​
8.33%​
Prob=
5/96​
15​
12​
1/36​
2.78%​
11​
1/18​
5.56%​
5​
3/8​
10​
1/12​
8.33%​
6​
1/8​
9​
1/9​
11.11%​
Prob=
13/288​
Total P(div by 5)​
7/72​
9.7%​


As AB and BC not independent A,B,C not independent
 
  • #35
BWV
1,202
1,312
Realized I read the condition for B as the whole total, rather than the dice total, here is the updated reply
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.

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.

T=total = (5:18)

Probabilities:

A = P(odd) =½ (even number of integer outcomes, symmetrical prob)

B= P(Dice total div by 5)=1/9+1/12=7/36

C=Pcoin(>=5)= ½ (p(6)=1/8+p(5)=3/8)



Two events independent if P(A∩B)= P(A)P(B) or, alternatively P(A|B)=P(A) and P(B|A)=P(B)

A and B not independent as

P(A)=1/2, P(A|B)=7/72

DicePCoinP
3​
1/8​
5​
1/9​
4​
3/8​
5​
3/8​
10​
1/12​
6​
1/8​
SumpOdd?
8​
1/72​
FALSE​
0​
9​
1/24​
TRUE​
1/24​
10​
1/24​
FALSE​
0​
11​
1/72​
TRUE​
1/72​
13​
1/96​
TRUE​
1/96​
14​
1/32​
FALSE​
0​
15​
1/32​
TRUE​
1/32​
16​
1/96​
FALSE​
0​
7/72​


A and C independent as

P(A)P(C)=1/4 = P(A∩C)=P(A|C)P(C)=1/4

B and C independent as

P(B)P(C)=7/72 = P(B∩C)=P(B|C)P(C)=7/72

A,B,C not jointly independent as A,B not independent
 

Suggested for: Math Challenge - June 2021

  • Last Post
3
Replies
88
Views
6K
  • Last Post
2
Replies
42
Views
4K
  • Last Post
2
Replies
61
Views
5K
  • Last Post
3
Replies
100
Views
4K
  • Last Post
3
Replies
93
Views
4K
  • Last Post
4
Replies
114
Views
4K
  • Last Post
3
Replies
102
Views
5K
  • Last Post
2
Replies
56
Views
5K
  • Last Post
2
Replies
67
Views
6K
  • Last Post
3
Replies
86
Views
8K
Top