Math Challenge - June 2021

In summary: Problem #9I don't know what "stochastically independent" means, but it's clear that$$P(A)=\frac{7}{8} \quad P(B)=\frac{1}{6} \quad P(C)=\frac{7}{8}+ \frac{1}{2} -\frac{1}{6} = \frac{2}{3}$$and$$P(A\cap B)=\frac{1}{8} \quad P(A\cap C)=\frac{3}{8} \quad P(B\cap C)=\frac{1}{6}-\frac{1}{8}=\frac{1}{24}$$
  • #1
fresh_42
Mentor
Insights Author
2023 Award
19,043
24,106
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
  • #3
$$\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
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
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:
  • #6
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
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
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.
 
  • #9
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
 

Similar threads

  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Math Proof Training and Practice
4
Replies
114
Views
6K
  • Math Proof Training and Practice
2
Replies
61
Views
7K
  • Math Proof Training and Practice
3
Replies
86
Views
9K
  • Math Proof Training and Practice
2
Replies
67
Views
8K
  • Math Proof Training and Practice
2
Replies
42
Views
6K
  • Math Proof Training and Practice
3
Replies
93
Views
10K
  • Math Proof Training and Practice
2
Replies
56
Views
7K
  • Math Proof Training and Practice
2
Replies
61
Views
9K
  • Math Proof Training and Practice
2
Replies
60
Views
8K
Back
Top