Proving $\lg^2 n=o(2^{\sqrt{2 \lg n}})$ and $2^{2^{n+1}}=\omega(2^{2^n})$

[evinda]

Hello! (Wave)

I want to prove the following sentences:

• $ \displaystyle{ \lg^2 n=o(2^{\sqrt{2 \lg n}})}$
  
• $ \displaystyle{ 2^{2^{n+1}}=\omega(2^{2^n})}$
  

Do I have to suppose that the sentences stand and then prove that it is actually like that or is there a better way to do it?

That's what I have tried :

• We suppose that: $\lg^2 n=o(2^{\sqrt{2 \lg n}})$.
  $$$$
  So, $\forall c>0, \exists n_0 \geq 1$ such that $\forall n \geq n_0$:
  $$\lg^2 n<c \cdot 2^{\sqrt{2 \lg n}}$$
  $$$$
  Do I have to find now a $n_0$ ? If so,how can I do this? (Thinking)
  $$$$
• We suppose that $2^{2^{n+1}}=\omega(2^{2^n})$.
  $$$$
  Then, $\forall c>0, \exists n_0 \geq 1$ such that $\forall n \geq n_0$:
  $$c \cdot 2^{2^{2^n}}<2^{2^{n+1}} \\ \Rightarrow c \cdot 2^{2^{2^n}}<2^{2^n \cdot 2} \\ \Rightarrow c \cdot 2^{2^{2^n}}<(2^{2^n})^2 \\ \Rightarrow c<2^{2^n}\\ \Rightarrow \lg c<2^n \\ \Rightarrow n>\lg (\lg c), \text{ if c>1}$$
  $$$$
  Now I found a restriction for $c$, but the relation should stand for each $c$. So, have I done something wrong? (Sweating)

 

[I like Serena]

$$\lg^2 n<c \cdot 2^{\sqrt{2 \lg n}}$$
$$$$
Do I have to find now a $n_0$ ? If so,how can I do this? (Thinking)

Let's start by taking the $\lg$ of each side shall we? (Wink)

Then, $\forall c>0, \exists n_0 \geq 1$ such that $\forall n \geq n_0$:
$$n>\lg (\lg c), \text{ if c>1}$$

Now I found a restriction for $c$, but the relation should stand for each $c$. So, have I done something wrong? (Sweating)

You're quite okay.

If we pick some $c>0$, we need to find an $n_0$ for which the equation holds.

So let's pick an $n_0$ such that $n_0 >\lg (\lg c)$.
Then the required equation follows. (Whew)

 

[Evgeny.Makarov]

Do I have to suppose that the sentences stand and then prove that it is actually like that or is there a better way to do it?

I assume you mean that you want to expand the definition of small-o in your statement and see if it holds, i.e., if you can indeed find an $n_0$ for each $c>0$. The way you phrased it sounds very strange: if you assume that a statement $P$ holds, then proving $P$ is trivial since $P\to P$ is a tautology. It's like instead of earning some money you borrow it and present it as earned. You still owe that sum.

 

[evinda]

Let's start by taking the $\lg$ of each side shall we? (Wink)

I took the $\lg$ of each side, and that's what I got: $\lg (\lg^2 n)< \lg c+ \sqrt{2 \lg n}$

How could we continue to find a $n_0$ ? (Thinking)

You're quite okay.

If we pick some $c>0$, we need to find an $n_0$ for which the equation holds.

So let's pick an $n_0$ such that $n_0 >\lg (\lg c)$.
Then the required equation follows. (Whew)

Couldn't we pick $n_0= \lfloor \lg (\lg c) \rfloor+1$ ? (Thinking)

- - - Updated - - -

I assume you mean that you want to expand the definition of small-o in your statement and see if it holds, i.e., if you can indeed find an $n_0$ for each $c>0$. The way you phrased it sounds very strange: if you assume that a statement $P$ holds, then proving $P$ is trivial since $P\to P$ is a tautology. It's like instead of earning some money you borrow it and present it as earned. You still owe that sum.

How could I prove the sentences otherwise? (Thinking)

 

[I like Serena]

I took the $\lg$ of each side, and that's what I got: $\lg (\lg^2 n)< \lg c+ \sqrt{2 \lg n}$

How could we continue to find a $n_0$ ? (Thinking)

Let's define and substitute:
$$y=\lg n$$
What do you get? (Wondering)

Couldn't we pick $n_0= \lfloor \lg (\lg c) \rfloor+1$ ? (Thinking)

Didn't you have a condition that $n_0 \ge 1$? (Wondering)
What if we pick for instance $c=1.1$?
Or $c=0.1$?

How could I prove the sentences otherwise? (Thinking)

Your phrasing of "We suppose that ..." is a bit unfortunate.
That phrase means that you assume that what you want to prove is true to begin with.
That makes it an invalid proof.

A better way to phrase it, would be: "We want to prove that ...". (Wasntme)

 

[evinda]

Let's define and substitute:
$$y=\lg n$$
What do you get? (Wondering)

That's what I got:

$$\lg (y^2)<\lg c+ \sqrt{2y} \Rightarrow \lg \left ( \frac{y^2}{c}\right )< \sqrt {2y }$$

How can I continue? (Thinking)

Didn't you have a condition that $n_0 \ge 1$? (Wondering)
What if we pick for instance $c=1.1$?
Or $c=0.1$?

Since $\lg (\lg c)$ is well-defined, it must stand $\lg c>0 \Rightarrow \lg c> \lg 1 \Rightarrow c>1$

$$n> \lg (\lg c), n \geq n_0 \geq 1 \Rightarrow \lg (\lg c) \geq 1 \Rightarrow \lg (\lg c) \geq \lg 2 \Rightarrow \lg c \geq 2 \Rightarrow c \geq 4$$

Or have I done something wrong? (Thinking)

Your phrasing of "We suppose that ..." is a bit unfortunate.
That phrase means that you assume that what you want to prove is true to begin with.
That makes it an invalid proof.

A better way to phrase it, would be: "We want to prove that ...". (Wasntme)

So, could I phrase like that?

We want to prove that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, so we want to prove that:
$$\forall c>0, \exists n_0 \geq 1 \text{ such that } \forall n \geq n_0: \\ \lg^2 n < c \cdot 2^{\sqrt{2 \lg n}}$$

$$ \dots$$

Therefore:

$$\lg^2 n=o(2^{\sqrt{2 \lg n}}), \forall n \geq n_0= \dots$$

(Thinking)

 

[I like Serena]

That's what I got:

$$\lg (y^2)<\lg c+ \sqrt{2y} \Rightarrow \lg \left ( \frac{y^2}{c}\right )< \sqrt {2y }$$

How can I continue? (Thinking)

Simplify it a bit? (Wasntme)

Would it be generally true? (Wondering)

Since $\lg (\lg c)$ is well-defined, it must stand $\lg c>0 \Rightarrow \lg c> \lg 1 \Rightarrow c>1$

$$n> \lg (\lg c), n \geq n_0 \geq 1 \Rightarrow \lg (\lg c) \geq 1 \Rightarrow \lg (\lg c) \geq \lg 2 \Rightarrow \lg c \geq 2 \Rightarrow c \geq 4$$

Or have I done something wrong? (Thinking)

I think we can still allow $0< c < 4$, but we'll just have to pick $n_0=1$ in those cases. (Wasntme)

So, could I phrase like that?

We want to prove that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, so we want to prove that:
$$\forall c>0, \exists n_0 \geq 1 \text{ such that } \forall n \geq n_0: \\ \lg^2 n < c \cdot 2^{\sqrt{2 \lg n}}$$

$$ \dots$$

Therefore:

$$\lg^2 n=o(2^{\sqrt{2 \lg n}}), \forall n \geq n_0= \dots$$

(Thinking)

The word "therefore" is an implication in the wrong direction.
It would be correct if you say for instance "This is the case if", which is an implication in the proper direction.

Symbolically, you want to proof $P$.
To do so, you can use a proof like:
$$A \Rightarrow B \Rightarrow C \Rightarrow P$$

Or you can use a proof like:
$$P \Leftarrow C \Leftarrow B \Leftarrow A$$
which is unconventional, but still correct.

But a proof like $P \Rightarrow A \Rightarrow B \Rightarrow C$ is invalid to proof $P$. (Nerd)

 

[evinda]

Simplify it a bit? (Wasntme)

Would it be generally true? (Wondering)

How could I simplify it and check if it is generally true? (Sweating)

I think we can still allow $0< c < 4$, but we'll just have to pick $n_0=1$ in those cases. (Wasntme)

Why is $0< c < 4$ allowed? Also, why do we have to pick $n_0=1$ ? (Thinking)

The word "therefore" is an implication in the wrong direction.
It would be correct if you say for instance "This is the case if", which is an implication in the proper direction.

Symbolically, you want to proof $P$.
To do so, you can use a proof like:
$$A \Rightarrow B \Rightarrow C \Rightarrow P$$

Or you can use a proof like:
$$P \Leftarrow C \Leftarrow B \Leftarrow A$$
which is unconventional, but still correct.

But a proof like $P \Rightarrow A \Rightarrow B \Rightarrow C$ is invalid to proof $P$. (Nerd)

A ok... I understand... (Nod)

 

[I like Serena]

How could I simplify it and check if it is generally true? (Sweating)

$$\lg (y^2)<\lg c+ \sqrt{2y} \Rightarrow 2\lg(y) < \lg c + \sqrt 2 \cdot \sqrt y$$

Which one is bigger? $\lg(y)$ or $\sqrt y$? (Wondering)

Why is $0< c < 4$ allowed? Also, why do we have to pick $n_0=1$ ? (Thinking)

Your proof requires that $\forall c>0 \ \exists n_0 \ge 1$.
In words: for each $c>0$ it must be possible to find an $n_0 \ge 1$, such that...
That implies you have to be able to find an $n_0$ for $0< c < 4$ as well. (Worried)However, your formula for $n_0$ is undefined or negative in this range.
Luckily we can still pick $n_0=1$ in those cases. (Mmm)

 

[evinda]

$$\lg (y^2)<\lg c+ \sqrt{2y} \Rightarrow 2\lg(y) < \lg c + \sqrt 2 \cdot \sqrt y$$

Which one is bigger? $\lg(y)$ or $\sqrt y$? (Wondering)

$$\lim_{y \to +\infty} \frac{\lg y}{\sqrt{y}} \overset{\text{ DLH }}{=} \lim_{y \to +\infty} \frac{\frac{1}{y}}{\frac{1}{2 \sqrt{y}}}=\lim_{y \to +\infty} \frac{2 \sqrt{y}}{y}=\lim_{y \to +\infty} \frac{2}{\sqrt{y}}=0$$

So, $\sqrt{y}$ is bigger than $\lg y$ , or am I wrong? (Thinking)

Your proof requires that $\forall c>0 \ \exists n_0 \ge 1$.
In words: for each $c>0$ it must be possible to find an $n_0 \ge 1$, such that...
That implies you have to be able to find an $n_0$ for $0< c < 4$ as well. (Worried)However, your formula for $n_0$ is undefined or negative in this range.
Luckily we can still pick $n_0=1$ in those cases. (Mmm)

So, do we have to take cases, when we have $\lg c<2^n$, since the relation stands $\forall n \geq n_0$,if $\lg c<0$, and we just have to look for a $n_0$ for the case $\lg c>0$ ? (Thinking)

 

[I like Serena]

$$\lim_{y \to +\infty} \frac{\lg y}{\sqrt{y}} \overset{\text{ DLH }}{=} \lim_{y \to +\infty} \frac{\frac{1}{y}}{\frac{1}{2 \sqrt{y}}}=\lim_{y \to +\infty} \frac{2 \sqrt{y}}{y}=\lim_{y \to +\infty} \frac{2}{\sqrt{y}}=0$$

So, $\sqrt{y}$ is bigger than $\lg y$ , or am I wrong? (Thinking)

Yep.
$\sqrt{y}$ is asymptotically bigger than $\lg y$.
This means that for any $c$ there is some $y_0$, such that the inequality holds for any $y>y_0$.

What does that mean for $n_0$? (Thinking)

So, do we have to take cases, when we have $\lg c<2^n$, since the relation stands $\forall n \geq n_0$,if $\lg c<0$, and we just have to look for a $n_0$ for the case $\lg c>0$ ? (Thinking)

You've lost me.

We just want to prove that for any $c>0$ we can find an $n_0\ge 1$ such that the inequality holds.
We can pick:
$$n_0 =\begin{cases} \left\lfloor \lg(\lg c) \right\rfloor + 1 & \text{if }c \ge 4 \\
1 &\text{otherwise}\end{cases}$$
(Wasntme)

 

[evinda]

You're quite okay.

If we pick some $c>0$, we need to find an $n_0$ for which the equation holds.

So let's pick an $n_0$ such that $n_0 >\lg (\lg c)$.
Then the required equation follows. (Whew)

If $f(n)=\omega(g(n))$, according to the definition, it must be like that:

$\forall c>0, \exists n_0 \geq 0$, such that $\forall n \geq n_0$:

$$f(n)>cg(n) \geq 0$$

So, shouldn't that what we find stand also for $c \leq 1$ ? (Worried)

 

[I like Serena]

If $f(n)=\omega(g(n))$, according to the definition, it must be like that:

$\forall c>0, \exists n_0 \geq 0$, such that $\forall n \geq n_0$:

$$f(n)>cg(n) \geq 0$$

So, shouldn't that what we find stand also for $c \leq 1$ ? (Worried)

Yes.
In that case pick $n_0 = 1$. (Wink)

 

[evinda]

Yes.
In that case pick $n_0 = 1$. (Wink)

In this case, we will have: $\lg c< 2^n$ and we cannot take $\lg$, since $c<1$, right? (Thinking)

What else could we do? (Worried)

 

[I like Serena]

In this case, we will have: $\lg c< 2^n$ and we cannot take $\lg$, since $c<1$, right? (Thinking)

What else could we do? (Worried)

In this case, with $0<c\le 1$ and for instance $n=n_0=1$, we have:
$$2^{2^{n+1}}=2^{2^{1+1}}=16>c\cdot 2^{2^n} = c\cdot 2^{2^1} =4c$$

Why would you take the log? (Wondering)
It's not defined.

 

[evinda]

In this case, with $0<c\le 1$ and for instance $n=n_0=1$, we have:
$$2^{2^{n+1}}=2^{2^{1+1}}=16>c\cdot 2^{2^n} = c\cdot 2^{2^1} =4c$$

Why would you take the log? (Wondering)
It's not defined.

From which relation do we conclude that we take $n_0=1$, when $0<c\le 1$?

 

[I like Serena]

From which relation do we conclude that we take $n_0=1$, when $0<c\le 1$?

When $0<c\le 1$, we want an $n_0$ such that for each $n \ge n_0$, we have:
$$2^{2^{n+1}} > c\cdot 2^{2^n}$$
$$2^{2^{n}} > c$$
By substituting we can tell that this is the case if $n \ge 1$, so we can pick $n_0=1$. (Mmm)

In this case it does not help us to take the log twice, because it's not defined.
So we have to do this without that. (Shake)

 

[evinda]

When $0<c\le 1$, we want an $n_0$ such that for each $n \ge n_0$, we have:
$$2^{2^{n+1}} > c\cdot 2^{2^n}$$
$$2^{2^{n}} > c$$
By substituting we can tell that this is the case if $n \ge 1$, so we can pick $n_0=1$. (Mmm)

What do we substitute at the inequality? (Thinking)

 

[I like Serena]

What do we substitute at the inequality? (Thinking)

We substitute $n=1$ and conclude that the inequality holds for any $0<c\le 1$.
Furthermore, we observe that $2^{2^n}$ is a strictly increasing function, meaning that the inequality also holds for any greater $n$. (Wasntme)

 

[evinda]

We substitute $n=1$ and conclude that the inequality holds for any $0<c\le 1$.
Furthermore, we observe that $2^{2^n}$ is a strictly increasing function, meaning that the inequality also holds for any greater $n$. (Wasntme)

A ok... So isn't it possible that there is a smaller $n_0$, for which the inequality holds? (Thinking)

 

[I like Serena]

A ok... So isn't it possible that there is a smaller $n_0$, for which the inequality holds? (Thinking)

Maybe, but we don't have to find the smallest $n_0$.
We only need to show there is one. (Thinking)

 

[evinda]

Maybe, but we don't have to find the smallest $n_0$.
We only need to show there is one. (Thinking)

Oh, yes! Right! (Nod) But, then why do we have to distinguish cases for $c$? (Thinking)

 

[I like Serena]

Oh, yes! Right! (Nod) But, then why do we have to distinguish cases for $c$? (Thinking)

Because $n_0 = 1$ does not work for $c \ge 4$.
And the solution by taking the logarithm twice does not work for $0 < c \le 1$. (Wasntme)

 

[evinda]

Yep.
$\sqrt{y}$ is asymptotically bigger than $\lg y$.
This means that for any $c$ there is some $y_0$, such that the inequality holds for any $y>y_0$.

What does that mean for $n_0$? (Thinking)

So, we want to show that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, so, that $\forall c>0, \exists n_0$, such that $\forall n \geq n_0$: $\lg^2 n< c \cdot 2^{{\sqrt{2 \lg n}}} \Rightarrow \lg (\lg^2 n)< \lg c+ \sqrt{2 \lg n}$.

We set $y=\lg n$.

So, we have:

$\lg (y^2)< \lg c+ \sqrt{2y} \Rightarrow 2 \lg y< \lg c+ \sqrt{2} \sqrt{y}$

$$\lim_{y \to +\infty} \frac{\lg y}{\sqrt{y}}=0$$

That means, that $\forall \epsilon>0, \exists n_0 \geq 0$, such that $\forall n \geq n_0$:

$$\lg y< \epsilon \cdot \sqrt{y}$$

Right? (Thinking) But, how can we continue?

 

[evinda]

Because $n_0 = 1$ does not work for $c \ge 4$.
And the solution by taking the logarithm twice does not work for $0 < c \le 1$. (Wasntme)

If we use this definition of $f(n)=\omega(g(n))$:
$\forall c>0, \exists n_0 \geq 0$ such that $\forall n \geq n_0$:

$$f(n)>c \cdot g(n) \geq 0$$

can we pick this $n_0$?

$$n_0=\left\{\begin{matrix}
\lfloor \lg (\lg c)\rfloor+1, c>1 & \\
1, 0< c \leq 1 &
\end{matrix}\right.$$

(Thinking)

 

[I like Serena]

If we use this definition of $f(n)=\omega(g(n))$:
$\forall c>0, \exists n_0 \geq 0$ such that $\forall n \geq n_0$:

$$f(n)>c \cdot g(n) \geq 0$$

can we pick this $n_0$?

$$n_0=\left\{\begin{matrix}
\lfloor \lg (\lg c)\rfloor+1, c>1 & \\
1, 0< c \leq 1 &
\end{matrix}\right.$$

(Thinking)

Yes. (Nod)

 

[I like Serena]

So, we want to show that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, so, that $\forall c>0, \exists n_0$, such that $\forall n \geq n_0$: $\lg^2 n< c \cdot 2^{{\sqrt{2 \lg n}}} \Rightarrow \lg (\lg^2 n)< \lg c+ \sqrt{2 \lg n}$.

We set $y=\lg n$.

So, we have:

$\lg (y^2)< \lg c+ \sqrt{2y} \Rightarrow 2 \lg y< \lg c+ \sqrt{2} \sqrt{y}$

$$\lim_{y \to +\infty} \frac{\lg y}{\sqrt{y}}=0$$

That means, that $\forall \epsilon>0, \exists n_0 \geq 0$, such that $\forall n \geq n_0$:

$$\lg y< \epsilon \cdot \sqrt{y}$$

Right? (Thinking) But, how can we continue?

What is:
$$\lim_{y\to \infty}\frac{ 2 \lg y}{\lg c+ \sqrt{2} \sqrt{y}}$$
(Wondering)

 

[evinda]

What is:
$$\lim_{y\to \infty}\frac{ 2 \lg y}{\lg c+ \sqrt{2} \sqrt{y}}$$
(Wondering)

$$\lim_{y\to \infty}\frac{ 2 \lg y}{\lg c+ \sqrt{2} \sqrt{y}} \overset{\text{ DLH }}{=} \frac{\frac{2}{y}}{\frac{\sqrt{y}}{2 \sqrt{y}}}=2 \sqrt{2} \lim_{y \to +\infty} \frac{1}{ \sqrt{y}}=0$$

This means that $\forall \epsilon>0, \exists n_0$, such that $\forall n \geq n_0$:

$$\frac{ 2 \lg y }{ \lg c+ \sqrt{2} \sqrt{y} }< \epsilon \Rightarrow 2 \lg y <\epsilon( \lg c+ \sqrt{2} \sqrt{y}) $$

Do we have to set now again $y=\lg n$? (Thinking)

 

[I like Serena]

$$\lim_{y\to \infty}\frac{ 2 \lg y}{\lg c+ \sqrt{2} \sqrt{y}} \overset{\text{ DLH }}{=} \frac{\frac{2}{y}}{\frac{\sqrt{y}}{2 \sqrt{y}}}=2 \sqrt{2} \lim_{y \to +\infty} \frac{1}{ \sqrt{y}}=0$$

This means that $\forall \epsilon>0, \exists n_0$, such that $\forall n \geq n_0$:

$$\frac{ 2 \lg y }{ \lg c+ \sqrt{2} \sqrt{y} }< \epsilon \Rightarrow 2 \lg y < \lg c+ \sqrt{2} \sqrt{y} $$

Do we have to set now again $y=\lg n$? (Thinking)

That sounds like a good idea. (Nod)

 

[evinda]

That sounds like a good idea. (Nod)

$$2 \lg y< \epsilon( \lg c+ \sqrt{2} \sqrt{y}) \Rightarrow 2 \lg (\lg n)< \epsilon( \lg c+ \sqrt{2} \sqrt{\lg n}) \Rightarrow \lg (\lg^2 n)< \epsilon (\lg c+ \sqrt{2} \sqrt{\lg n})$$

Do we pick now $\epsilon=1$ ? (Thinking)

 

[I like Serena]

$$2 \lg y< \epsilon( \lg c+ \sqrt{2} \sqrt{y}) \Rightarrow 2 \lg (\lg n)< \epsilon( \lg c+ \sqrt{2} \sqrt{\lg n}) \Rightarrow \lg (\lg^2 n)< \epsilon (\lg c+ \sqrt{2} \sqrt{\lg n})$$

Do we pick now $\epsilon=1$ ? (Thinking)

Sounds good. (Sweating)

 

[evinda]

Sounds good. (Sweating)

Then , after picking $\epsilon=1$, have we shown that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$ ? (Thinking)

 

[I like Serena]

Then , after picking $\epsilon=1$, have we shown that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$ ? (Thinking)

Suppose you check the condition for this to be true.
Is it (always) satisfied with what you have? (Wondering)

 

[evinda]

Suppose you check the condition for this to be true.
Is it (always) satisfied with what you have? (Wondering)

We want to show that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, so, that:
$$\forall c>0, \exists n_0 \text{ such that } \forall n \geq n_0: \lg (\lg^2 n)< \lg c+ \sqrt{2} \sqrt{n}$$We have shown that $\exists n_0$ such that $\forall n \geq n_0$:

$$\lg (\lg^2 n)< \lg c+ \sqrt{2} \sqrt{ \lg n}$$

But, we haven't shown that the relation stands $ \forall c>0$, or am I wrong? (Thinking)

 

[I like Serena]

We want to show that $\lg^2 n=o(2^{\sqrt{2 \lg n}})$, so, that:
$$\forall c>0, \exists n_0 \text{ such that } \forall n \geq n_0: \lg (\lg^2 n)< \lg c+ \sqrt{2} \sqrt{n}$$We have shown that $\exists n_0$ such that $\forall n \geq n_0$:

$$\lg (\lg^2 n)< \lg c+ \sqrt{2} \sqrt{ \lg n}$$

But, we haven't shown that the relation stands $ \forall c>0$, or am I wrong? (Thinking)

You are wrong. (Shake)
For every $c>0$ the same reasoning stands. (Nod)