Challenge Math Challenge - June 2021

fresh_42
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
2024 Award
Messages
20,627
Reaction score
27,771
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}}
$$
 
  • Like
Likes bhupesh
Physics news on Phys.org
$$\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:
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.
 
Office_Shredder said:
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:
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.
 
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}

$$
 
kshitij said:
$$(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.
 
Office_Shredder said:
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,
Office_Shredder 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
Office_Shredder said:
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 said:
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
Office_Shredder said:
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
kshitij said:
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
kshitij said:
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
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
kith said:
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
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
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:
  • Like
Likes kshitij
  • #19
kshitij said:
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 let's you talk about sets of inputs, which let's 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.
 
  • Like
Likes kshitij
  • #20
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
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
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 don't 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
julian said:
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 don't 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
Looking at the solution to 13 first, I think I'm confused by the first couple steps.

kshitij said:
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?
kshitij said:
\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)##.

kshitij said:
$$\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).##
julian said:
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
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.
 
  • Like
Likes kshitij
  • #26
Office_Shredder said:
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.
Office_Shredder said:
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}
$$
Office_Shredder said:
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##.
Office_Shredder said:
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
julian said:
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:
  • Like
Likes julian
  • #28
kshitij said:
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 can't 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 said:
@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 can't 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
Office_Shredder said:
@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
kshitij said:
\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.
 
  • Like
Likes kshitij
  • #32
julian said:
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*}$$
 
  • Like
Likes julian
  • #33
kshitij said:
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
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
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
 
  • #36
kshitij said:
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.
You only claimed to know c and k are rational. ##(5/2)^2=(3/2)^2+2^2##

I think problem 15 has been pieced together correctly, but I think it's important to understand why the first attempt failed on the last line. If you still aren't sure please post here again.

@BWV I think A and B are independent. I haven't checked carefully what you wrote but consider the outcome of the sum being odd after you fix both die rolls (which completely determines B) and also two of the coins just for fun. What is the probability of event A? Any event that is determined just by the die rolls must be independent of A because of this.

That leaves the fun part of checking the triple.
 
Last edited:
  • #37
You are right - need to divide the 7/72 by P(B) which gives 1/2 so they are independent
 
  • #38
Ok one last shot (maybe can delete the previous?)
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 independent as

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

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​
7/72 / 7/36 = 1/2

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
P(A)P(B)P(C)=(1/2)(1/2)(7/36) = 7/144 <> P(C|AB) (only outcomes =11,15 above on A and B)= 1/72+1/32 = 13/288
 
  • #39
Hölder continuous implies uniformly continuous. So, we'll show that these conditions are not equivalent.

The set [0,c] is compact and -\frac{1}{ \ln x}\to 0 = f(0) as x\to 0+. Hence f is uniformly continuous.

Assume for a contradiction f is Hölder continuous. That is, there exist 0&lt; \alpha \leqslant 1 and M&gt;0 such that
<br /> \forall x,x&#039;\in [0,c],\quad \left| f(x) - f(x&#039;)\right| \leqslant M |x-x&#039;|^\alpha.<br />
In particular (taking x&#039;=0) we have for every 0\leqslant x\leqslant c that
\left | \frac{1}{\ln x} \right| \leqslant M |x|^\alpha \Leftrightarrow 1\leqslant M|x^\alpha\ln x|.
But |x^\alpha \ln x| \to 0 as x\to 0+. E.g apply L'Hopital to \frac{\ln x}{x^{-\alpha}} as x\to 0+. This is a contradiction, so f cannot be Hölder continuous.
 
Last edited:
  • #40
I have two ways for problem 3, but can't think of a third right now.
i) by direct substitution:\begin{align*}
p \dfrac{\partial V}{\partial T} \bigg{)}_{p} - C = 0 \quad &\implies \quad \dfrac{\partial V}{\partial T} \bigg{)}_{p} = \frac{c}{p} \\

V + \frac{CB}{2\sqrt{p}} - C \dfrac{\partial T}{\partial p} \bigg{)}_{V} = 0 \quad &\implies \quad \dfrac{\partial T}{\partial p} \bigg{)}_{V} = \frac{V + \frac{CB}{2\sqrt{p}}}{C} \\

p + V \dfrac{\partial p}{\partial V} \bigg{)}_{T} + \frac{CB}{2\sqrt{p}} \dfrac{\partial p}{\partial V} \bigg{)}_{T} = 0 \quad &\implies \quad \dfrac{\partial p}{\partial V} \bigg{)}_{T} = \frac{-p}{V + \frac{CB}{2\sqrt{p}}}
\end{align*}then ##\dfrac{\partial V}{\partial T} \bigg{)}_{p} \dfrac{\partial T}{\partial p} \bigg{)}_{V} \dfrac{\partial p}{\partial V} \bigg{)}_{T} = \dfrac{C}{p} \cdot \dfrac{V + \frac{CB}{2\sqrt{p}}}{C} \cdot \dfrac{-p}{V + \frac{CB}{2\sqrt{p}}} = -1##.

ii) Given ##f(p,V,T) = 0## for some ##f## then if ##f_p \neq 0## at some point then by the implicit function theorem there's some neighbourhood where ##p = p(V,T)## and so ##f(p(V,T),V,T) = 0##. Then ##f_V + f_p \dfrac{\partial p}{\partial V} \bigg{)}_T = 0 \implies \dfrac{\partial p}{\partial V} \bigg{)}_T = -f_V / f_p##. Similarly writing ##V = V(p,T)## gives ##\dfrac{\partial V}{\partial p} \bigg{)}_T = -f_p/f_V##, which proves the reciprocity relation ##\dfrac{\partial p}{\partial V} \bigg{)}_T \dfrac{\partial V}{\partial p} \bigg{)}_T = 1## [and same for the other two combinations].

Now given ##dV = \dfrac{\partial V}{\partial p} \bigg{)}_{T} dp + \dfrac{\partial V}{\partial T} \bigg{)}_{p} dT## write\begin{align*}
dp &= \dfrac{\partial p}{\partial V} \bigg{)}_{T} dV + \dfrac{\partial p}{\partial T} \bigg{)}_{V} dT \\

dp &= \dfrac{\partial p}{\partial V} \bigg{)}_{T} \left\{ \dfrac{\partial V}{\partial p} \bigg{)}_{T} dp + \dfrac{\partial V}{\partial T} \bigg{)}_{p} dT \right\} + \dfrac{\partial p}{\partial T} \bigg{)}_{V} dT \\

dp &= dp + \dfrac{\partial p}{\partial V} \bigg{)}_{T} \dfrac{\partial V}{\partial T} \bigg{)}_{p} dT + \dfrac{\partial p}{\partial T} \bigg{)}_{V} dT
\end{align*}hence ##\dfrac{\partial p}{\partial V} \bigg{)}_{T} \dfrac{\partial V}{\partial T} \bigg{)}_{p} = - \dfrac{\partial p}{\partial T} \bigg{)}_{V} \implies \dfrac{\partial p}{\partial V} \bigg{)}_{T} \dfrac{\partial V}{\partial T} \bigg{)}_{p} \dfrac{\partial T}{\partial p} \bigg{)}_{V} = -1##.
 
  • #41
@BWV that looks good to me now.

I think this is just a complicated version of you flip 2 coins which give values 1 if tails and 2 if heads, and let A= coin 1 is even, B= coin 2 is even, C=coin1+coin2 is even. If you want a simpler example in your toolbox :)

nuuskur said:
Hölder continuous implies uniformly continuous. So, we'll show that these conditions are not equivalent.

The set [0,c] is compact and -\frac{1}{ \ln x}\to 0 = f(0) as x\to 0+. Hence f is uniformly continuous.

Assume for a contradiction f is Hölder continuous. That is, there exist 0&lt; \alpha \leqslant 1 and M&gt;0 such that
<br /> \forall x,x&#039;\in [0,c],\quad \left| f(x) - f(x&#039;)\right| \leqslant M |x-x&#039;|^\alpha.<br />
In particular (taking x&#039;=0) we have for every 0\leqslant x\leqslant c that
\left | \frac{1}{\ln x} \right| \leqslant M |x|^\alpha \Leftrightarrow 1\leqslant M|x^\alpha\ln x|.
But |x^\alpha \ln x| \to 0 as x\to 0+. E.g apply L'Hopital to \frac{\ln x}{x^{-\alpha}} as x\to 0+. This is a contradiction, so f cannot be Hölder continuous.
This looks good. An exercise for the reader I guess is to show that any continuous function on a compact interval is uniformly continuous.

ergospherical said:
I have two ways for problem 3, but can't think of a third right now.
i) by direct substitution:\begin{align*}
p \dfrac{\partial V}{\partial T} \bigg{)}_{p} - C = 0 \quad &\implies \quad \dfrac{\partial V}{\partial T} \bigg{)}_{p} = \frac{c}{p} \\

V + \frac{CB}{2\sqrt{p}} - C \dfrac{\partial T}{\partial p} \bigg{)}_{V} = 0 \quad &\implies \quad \dfrac{\partial T}{\partial p} \bigg{)}_{V} = \frac{V + \frac{CB}{2\sqrt{p}}}{C} \\

p + V \dfrac{\partial p}{\partial V} \bigg{)}_{T} + \frac{CB}{2\sqrt{p}} \dfrac{\partial p}{\partial V} \bigg{)}_{T} = 0 \quad &\implies \quad \dfrac{\partial p}{\partial V} \bigg{)}_{T} = \frac{-p}{V + \frac{CB}{2\sqrt{p}}}
\end{align*}then ##\dfrac{\partial V}{\partial T} \bigg{)}_{p} \dfrac{\partial T}{\partial p} \bigg{)}_{V} \dfrac{\partial p}{\partial V} \bigg{)}_{T} = \dfrac{C}{p} \cdot \dfrac{V + \frac{CB}{2\sqrt{p}}}{C} \cdot \dfrac{-p}{V + \frac{CB}{2\sqrt{p}}} = -1##.

ii) Given ##f(p,V,T) = 0## for some ##f## then if ##f_p \neq 0## at some point then by the implicit function theorem there's some neighbourhood where ##p = p(V,T)## and so ##f(p(V,T),V,T) = 0##. Then ##f_V + f_p \dfrac{\partial p}{\partial V} \bigg{)}_T = 0 \implies \dfrac{\partial p}{\partial V} \bigg{)}_T = -f_V / f_p##. Similarly writing ##V = V(p,T)## gives ##\dfrac{\partial V}{\partial p} \bigg{)}_T = -f_p/f_V##, which proves the reciprocity relation ##\dfrac{\partial p}{\partial V} \bigg{)}_T \dfrac{\partial V}{\partial p} \bigg{)}_T = 1## [and same for the other two combinations].

Now given ##dV = \dfrac{\partial V}{\partial p} \bigg{)}_{T} dp + \dfrac{\partial V}{\partial T} \bigg{)}_{p} dT## write\begin{align*}
dp &= \dfrac{\partial p}{\partial V} \bigg{)}_{T} dV + \dfrac{\partial p}{\partial T} \bigg{)}_{V} dT \\

dp &= \dfrac{\partial p}{\partial V} \bigg{)}_{T} \left\{ \dfrac{\partial V}{\partial p} \bigg{)}_{T} dp + \dfrac{\partial V}{\partial T} \bigg{)}_{p} dT \right\} + \dfrac{\partial p}{\partial T} \bigg{)}_{V} dT \\

dp &= dp + \dfrac{\partial p}{\partial V} \bigg{)}_{T} \dfrac{\partial V}{\partial T} \bigg{)}_{p} dT + \dfrac{\partial p}{\partial T} \bigg{)}_{V} dT
\end{align*}hence ##\dfrac{\partial p}{\partial V} \bigg{)}_{T} \dfrac{\partial V}{\partial T} \bigg{)}_{p} = - \dfrac{\partial p}{\partial T} \bigg{)}_{V} \implies \dfrac{\partial p}{\partial V} \bigg{)}_{T} \dfrac{\partial V}{\partial T} \bigg{)}_{p} \dfrac{\partial T}{\partial p} \bigg{)}_{V} = -1##.

This looks good to me. I think you might have made your second method too complicated. Once you have ##\dfrac{\partial p}{\partial V} \bigg{)}_T = -f_V/f_p##, then you also have by just copying the symbols in the same pattern
$$
\dfrac{\partial p}{\partial V} \bigg{)}_T \dfrac{\partial V}{\partial T} \bigg{)}_p
\dfrac{\partial T}{\partial p} \bigg{)}_V
= \frac{-f_V}{f_p} \frac{-f_T}{f_V} \frac{-f_p}{f_T} = -1$$.

Fresh provided three methods that were implicit function theorem, and implicit differentiation to solve for the derivatives. I feel like the third method from here is a little non-obvious, so I'll just say it's computing the actual functions ##V(T)##, ##p(V)## and ##T(p)## directly before taking any derivatives.
 
  • Like
Likes ergospherical and BWV
  • #42
Problem 12

Let ##\sqrt{n}+\sqrt{n+4}=p## such that ##p\in\mathbb{Q}##

So we get,
$$\begin{align}
\sqrt{n}+\sqrt{n+4}&=p\nonumber\\
n+n+4+2\sqrt{n}\cdot\sqrt{n+4}&=p^2\nonumber\\
\sqrt{n}\cdot\sqrt{n+4}=\frac{p^2-2n-4}{2}&=q\space\text{(say)}\nonumber
\end{align}$$
We can see that ##q\in\mathbb{Q}## as ##n\in\mathbb{N}##

Now let ##\sqrt{n}## and ##\sqrt{n+4}## be the roots of the quadratic equation
$$x^2-px+q=0$$
Putting the value of ##x## in the above equation as ##\sqrt{n}##, we get
$$\begin{align}
n-p\sqrt{n}+q&=0\nonumber\\
\sqrt{n}=\frac{n+q}{p}&=a\space\text{(say)}\nonumber
\end{align}$$
Similarly, putting the value of ##x## as ##\sqrt{n+4}##, we get
$$\begin{align}
n+4-p\sqrt{n+4}+q&=0\nonumber\\
\sqrt{n+4}=\frac{n+q+4}{p}&=b\space\text{(say)}\nonumber
\end{align}$$
As we can see that ##a## and ##b## are also rational numbers, moreover, as ##n## is a natural number, ##a## and ##b## should also be natural numbers

So, we get,
\begin{align*}
\sqrt{n}=a\\
n=a^2
\end{align*}
And
$$n+4=b^2$$
Putting that value of ##n##,
\begin{align*}
a^2+4=b^2\\
4=b^2-a^2\\
2^2=(b-a)(b+a)
\end{align*}
Now, ##2^2=2^2\cdot 2^0## and ##2^2=2^1\cdot 2^1## are the only possible ways of writing ##2^2## as a product of two natural numbers,

So, the only solutions are
##b-a=b+a=2## from this we get ##a=0## which is not possible
##b-a=1## and ##b+a=4## from this ##b=\frac5 2## and ##a=\frac3 2## which is again not possible
##b-a=4## and ##b+a=1## which gives ##b=\frac5 2## and ##a=\frac{-3} 2## which is also not possible

So, ##\sqrt{n}+\sqrt{n+4}## cannot be a rational number if ##n## is a natural number.
 
  • #43
julian said:
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.
Hey @julian, Thanks for your reply, but I still have the same question,

you said that,
\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}} \qquad (*)
\end{align*}
is correct

But as we have,
\begin{align*}
\binom{2n}{n} &< \binom{2n+1}{n}\\
\dfrac{\binom {2n} {n}}{2^{2n+1}}&<\dfrac{\binom {2n+1} {n}}{2^{2n+1}} \qquad(**)
\end{align*}
Similarly,$$\dfrac{1}{\sqrt{2n+3}}< \dfrac{1}{\sqrt{2n+1}} \qquad(***)$$

Now if we have a relation like,
##b<c##, ##a<b## and ##c<d##
Then we can write ##a<d##
because the order between ##a,b,c,d## is ##a<b<c<d##

So, in our case, we have ##a=\frac{\binom{2n}{n}}{2^{2n+1}} ##, ##b=\dfrac{\binom {2n+1} {n}}{2^{2n+1}}##, ##c=\dfrac{1}{\sqrt{2n+3}}## and ##d=\dfrac{1}{\sqrt{2n+1}}##

From ##(*)## we had ##b<c##, from ##(**)## we got ##a<b## and from ##(***)## we got ##c<d##

So, again the order between ##a,b,c,d## is ##a<b<c<d##

That gives
\begin{align*}
a&<d\\
\dfrac{\binom {2n} {n}}{2^{2n+1}}&<\dfrac{1}{\sqrt{2n+1}} \qquad(****)
\end{align*}
So, from ##(*)## we deduced that ##(****)## is true, then why is this wrong?
 
  • #44
julian said:
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.
I do agree with what you said here, I also agree with your solution which was discussed earlier in this thread, but I think that there is another method of doing this problem which is with the use of orders ##a<b<c<d## which I mentioned above.

julian said:
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 (∗∗).
But this statement is confusing for me.

If the problem involved only equalities, e.g., from $$b=c \qquad(*)$$ we had to prove that $$a=d \qquad(**)$$
Then in this case we can always work backwards from ##(**)## to ##(*)##
We just have to show that ##a=d=k##, ##b=k## and ##c=k##
this would give us the only possibility, i.e., ##a=d=b=c=k##

But if the question involves inequalities, e.g., from $$b<c \qquad(*)$$ we had to prove that $$a<d \qquad(**)$$
Then in this case how can we always work backwards from ##(**)## to ##(*)##

unlike the first case, even if could have shown that ##a<d<k##, ##b<k## and ##c<k##
then that doesn't mean that ##b<c## if ##a<d##
because there are multiple possible orders between ##a,b,c,d,k## like
##a<d<b<c<k##, ##a<c<d<b<k##, ##a<c<b<d<k##, etc
and all of them satisfy ##a<d<k##, ##b<k## and ##c<k##

In case of equality there is only one possibility i.e., ##a=b=c=d## but in case of inequalities there are multiple numbers between them so there are multiple possible orders between them

In other words we cannot do anything only using the relation ##a<d## by which we will end up with a fixed possible order between ##a,b,c,d##

So, how can we work backwards in this case if there are multiple possibilities?

Even in your solution, I cannot think how to work backwards from,
\begin{align*}

\frac{1}{2} \cdot \frac{2n+1}{n+1} < \sqrt{\frac{2n+1}{2n+3}}

\end{align*}
to get,
\begin{align*}

\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}

\end{align*}
 
Last edited:
  • #45
kshitij said:
I do agree with what you said here, I also agree with your solution which was discussed earlier in this thread, but I think that there is another method of doing this problem which is with the use of orders ##a<b<c<d## which I mentioned above.But this statement is confusing for me.

If the problem involved only equalities, e.g., from $$b=c \qquad(*)$$ we had to prove that $$a=d \qquad(**)$$
Then in this case we can always work backwards from ##(**)## to ##(*)##
We just have to show that ##a=d=k##, ##b=k## and ##c=k##
this would give us the only possibility, i.e., ##a=d=b=c=k##

But if the question involves inequalities, e.g., from $$b<c \qquad(*)$$ we had to prove that $$a<d \qquad(**)$$
Then in this case how can we always work backwards from ##(**)## to ##(*)##

unlike the first case, even if could have shown that ##a<d<k##, ##b<k## and ##c<k##
then that doesn't mean that ##b<c## if ##a<d##
because there are multiple possible orders between ##a,b,c,d,k## like
##a<d<b<c<k##, ##a<c<d<b<k##, ##a<c<b<d<k##, etc
and all of them satisfy ##a<d<k##, ##b<k## and ##c<k##

As ##a,d## are not equal so there are multiple numbers in between them, similarly for ##b,c## as well

In case of equality there is only one possibility i.e., ##a=b=c=d## but in case of inequalities there are multiple numbers between them so there are multiple possible orders between them

In other words we cannot do anything only using the relation ##a<d## by which we will end up with a fixed possible order between ##a,b,c,d##

So, how can we work backwards in this case if there are multiple possibilities?

Even in your solution, I cannot think how to work backwards from,
\begin{align*}

\frac{1}{2} \cdot \frac{2n+1}{n+1} < \sqrt{\frac{2n+1}{2n+3}}

\end{align*}
to get,
\begin{align*}

\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}

\end{align*}
On rereading, I get this feeling that may be I'm doing something wrong here, but I'm confused as we are dealing with inequalities here, if we had been dealing with equalities then everything you said makes sense to me.
 
  • #46
I think the simplest way to think about the 15 attempt is to actually just flip the order of everything. You wanted to prove (*) and took a bunch of steps to get from (*) to (****). But your actual goal was to start with (****) and get to (*). Often if you can go in one direction you can go in the other direction but it's not always true.

As a dumb example if ##x=y## then ##x^2=y^2## but the other direction is not true. There's nothing special about inequalities here.

If the steps are actually reversible, you should just reverse them. Start with (****) and get to (*) at the end.

I'll check your new 12 attempt later today.
 
Last edited:
  • #47
I think I figured out what was wrong

(refer to my first attempt of problem 15)

I wanted to show that $$b<c$$
I knew that $$e<f$$
is true.

I assumed that ##b<c## is also true

First I showed that ##a<b## and then I showed ##c<d##
so I concluded that $$a<d$$
Now I did the same process with ##e,f## i.e., I first showed that ##a<e## and then ##f<d## by which I concluded that,
$$a<d$$
which is the same result that I got with ##b,c##

And here I concluded that since I got the same result with both the relations ##e<f## (this is known to be true) and ##b<c## (this I assumed to be true) then they both must be true!

However, when I do the same thing but this time assuming that $$c<b$$ ##a<b## and ##c<d## can still be true.

To elaborate, see the image below,
diagram-20210625.png

Lets say that ##b<c## and then after showing that ##a<b## and ##c<d##, I can say that,$$a<d$$

Now see the situation of ##e,f##,
diagram-20210625 6.png

It is known that ##e<f## and I showed again using ##a<e## and ##f<d## that $$a<d$$
But unlike the previous case ##e<f## is known to be true, so ##a<d## must be true as well.

Now what if ##c<b##?
diagram-20210625 5.png

You can clearly see that everything I did assuming ##b<c## can also be done using ##c<b## because still we can see that ##a<b## and ##c<d##

So, even though whatever I did with ##a,b,c,d## might be correct and even the relation $$a<d$$ is also correct, but that clearly didn't give us a relation between ##b## and ##c##!
And that is why the first attempt is incomplete (infact I achieved nothing new, I just played around with ##a,b,c,d##)
 
  • #48
kshitij said:
I think I figured out what was wrong

(refer to my first attempt of problem 15)

I wanted to show that $$b<c$$
I knew that $$e<f$$
is true.

I assumed that ##b<c## is also true

First I showed that ##a<b## and then I showed ##c<d##
so I concluded that $$a<d$$
Now I did the same process with ##e,f## i.e., I first showed that ##a<e## and then ##f<d## by which I concluded that,
$$a<d$$
which is the same result that I got with ##b,c##

And here I concluded that since I got the same result with both the relations ##e<f## (this is known to be true) and ##b<c## (this I assumed to be true) then they both must be true!

However, when I do the same thing but this time assuming that $$c<b$$ ##a<b## and ##c<d## can still be true.

To elaborate, see the image below,
View attachment 285014
Lets say that ##b<c## and then after showing that ##a<b## and ##c<d##, I can say that,$$a<d$$

Now see the situation of ##e,f##,
View attachment 285015
It is known that ##e<f## and I showed again using ##a<e## and ##f<d## that $$a<d$$
But unlike the previous case ##e<f## is known to be true, so ##a<d## must be true as well.

Now what if ##c<b##?
View attachment 285016
You can clearly see that everything I did assuming ##b<c## can also be done using ##c<b## because still we can see that ##a<b## and ##c<d##

So, even though whatever I did with ##a,b,c,d## might be correct and even the relation $$a<d$$ is also correct, but that clearly didn't give us a relation between ##b## and ##c##!
And that is why the first attempt is incomplete (infact I achieved nothing new, I just played around with ##a,b,c,d##)
Now this looks quiet confusing to read as a third person who doesn't know what's going in my head, but to me it makes perfect sense!

Still if someone wants to read that, then the case ##e<f## was in the original attempt (see post #21 of this thread) ##\dfrac{\binom {2n} n}{2^{2n}}< \dfrac{1}{\sqrt{2n+1}}##
And the case ##b<c## was ##\dfrac{\binom {2n+2} {n+1}}{2^{2n+2}}< \dfrac{1}{\sqrt{2n+3}}##
And finally ##a<d## was ##\dfrac{\binom {2n} n}{2^{2n+1}}< \dfrac{1}{\sqrt{2n+1}}##

And yes ##d## and ##f## are basically the same thing but that doesn't make much difference in the process which I was explaining
 
Last edited:
  • #49
Office_Shredder said:
As a dumb example if x=y then x2=y2 but the other direction is not true. There's nothing special about inequalities here.
How do you consistently come up with an example that I overlook? 😅
 
  • #50
I really like that solution to 11* Writing that quadratic equation is pretty cool.
 
  • Like
Likes kshitij

Similar threads

3
Replies
100
Views
11K
3
Replies
114
Views
10K
2
Replies
61
Views
11K
2
Replies
86
Views
13K
2
Replies
67
Views
11K
Replies
42
Views
10K
2
Replies
56
Views
10K
2
Replies
61
Views
12K
2
Replies
93
Views
14K
2
Replies
60
Views
11K
Back
Top