Proving Asymptotic Bound: n*4^n=O(n!)

[evinda]

Hi! (Wave)

$$\text{ I want to prove that } n \cdot 4^n=O(n!), \text{ so that } \exists c>0, n_0 \geq 0, \text{ such that } \forall n \geq n_0: n \cdot 4^n \leq c \cdot n!$$

That's what I have tried:

$$n \cdot 4^n=n \cdot \underbrace{4 \cdot 4 \cdots 4}_n=4 \cdot 4 \cdot 4 \cdot4 \cdot \underbrace{4 \cdot 4 \cdots 4}_{n-4} \cdot n \leq 4^4 \cdot 1 \cdot 2 \cdot 3 \cdot \underbrace{4 \cdot 4 \cdots 4}_{n-4} \cdot n \leq 4^4 \cdot 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdots (n-1) \cdot n=4^4 \cdot n!, \forall n \geq 0$$

We pick $n_0=0$ and $c=4^4$ and we have that: $4^n=O(n!)$.

Can we say it like that or do we have to prove that it stands also with an other way, for example by induction? (Thinking)

 

[Evgeny.Makarov]

Your proof works for $n\ge 4$, but I am not sure about $n<4$ since you use the notation $\underbrace{4 \cdot 4 \cdots 4}_{n-4}$, which does not make sense for $n<4$. The constants $n_0=0$ and $c=4^4$ are correct, though.

 

[evinda]

Your proof works for $n\ge 4$, but I am not sure about $n<4$ since you use the notation $\underbrace{4 \cdot 4 \cdots 4}_{n-4}$, which does not make sense for $n<4$. The constants $n_0=0$ and $c=4^4$ are correct, though.

I undertstand! (Nod) So, does this proof suffice or do I have to prove it also by indunction or with an other way? (Thinking)

 

[Evgeny.Makarov]

So, does this proof suffice

Hmm. Let me say it again.

I am not sure about $n<4$ since you use the notation $\underbrace{4 \cdot 4 \cdots 4}_{n-4}$, which does not make sense for $n<4$.

do I have to prove it also by indunction

Technically, every proof that involves ellipses ($\cdots$) uses induction. However, it is often abbreviated by using dots or by saying things like "and so on". Usually this is perfectly fine. I don't think rewriting your proof to use explicit induction would make it clearer, so if your course does not require induction, I would leave it as is after correcting the $n<4$ case. For example, $(1\cdot2\cdot\ldots\cdot(n-1))\cdot n\ne n!$ when $n=0$.

 

[evinda]

Hmm. Let me say it again.

Technically, every proof that involves ellipses ($\cdots$) uses induction. However, it is often abbreviated by using dots or by saying things like "and so on". Usually this is perfectly fine. I don't think rewriting your proof to use explicit induction would make it clearer, so if your course does not require induction, I would leave it as is after correcting the $n<4$ case. For example, $(1\cdot2\cdot\ldots\cdot(n-1))\cdot n\ne n!$ when $n=0$.

For $n=1: 4 \leq c \cdot 1$, for $c=4 \checkmark$

For $n=2: 2 \cdot 16 \leq c \cdot 2$, for $c=16 \checkmark$

For $n=3: 3 \cdot 4^3 \leq c 6$, for $c=4^3 \checkmark$

For $n=4: 4^5 \leq c \cdot 4 \cdot 3 \cdot 2$, for $c=4^4 \checkmark$

Is it right? (Thinking)

 

[Evgeny.Makarov]

What you wrote is correct, but a proof of big-O must use a single $c$. This is expressed in the fact that in the definition of big-O $\exists c$ comes before $\forall n\ge n_0$. This means that a single $c$ must work for all $n$. This is crucial because if $c$ can change with $n$, then I can say that $n^2=O(n)$ because for $c=n$ we have $n^2\le cn$. Of course, in your proof you can simply take $c=4^4$ in all cases.

Also, you checked some values of $n$ starting from $n=1$, but in your initial proof $n_0=0$ and $n\ge n_0$, i.e., $n$ can equal 0.

I would not go through this hassle and simply declare $n_0=4$, so that the general case of your proof works.

 

[evinda]

What you wrote is correct, but a proof of big-O must use a single $c$. This is expressed in the fact that in the definition of big-O $\exists c$ comes before $\forall n\ge n_0$. This means that a single $c$ must work for all $n$. This is crucial because if $c$ can change with $n$, then I can say that $n^2=O(n)$ because for $c=n$ we have $n^2\le cn$. Of course, in your proof you can simply take $c=4^4$ in all cases.

Also, you checked some values of $n$ starting from $n=1$, but in your initial proof $n_0=0$ and $n\ge n_0$, i.e., $n$ can equal 0.

I would not go through this hassle and simply declare $n_0=4$, so that the general case of your proof works.

I understand! (Smile)

How could we prove it by induction for $n \geq 4$?

For $n=4: 4 \cdot 4^4 \leq 4^4 \cdot 4! \checkmark$

We suppose that $n \cdot 4^n \leq 4^4 \cdot n!$

$(n+1) \cdot 4^{n+1}=n \cdot 4^{n+1}+4^{n+1}=n \cdot 4^n \cdot 4+4^n \cdot 4$

How could we continue? (Thinking)

 

[Evgeny.Makarov]

You could prove that $4\frac{n+1}{n}\le n+1$ for $n\ge 4$ and multiply $4^nn$ by $4\frac{n+1}{n}$ and $n!$ by $n+1$.

I believe that your original proof (which, unlike the idea above, does not use fractions) can be written more carefully and explicitly in inductive form, but I don't have time at the moment to write it out. I'll think about it later.

 

[Evgeny.Makarov]

Your original idea can be rendered using induction as follows.

Lemma. If $n\ge 4$, then
\[
4^n<4^4(n-1)!\enspace.\qquad(*)
\]
Proof by induction on $n$. If $n=4$, then $4^4<4^4\cdot1\cdot2\cdot 3$. Suppose that $4^k<4^4(k-1)!$ and $k\ge 4$. Then multiplying the left-hand side by $4$ and the right-hand side by $k\ge 4$ the inequality becomes $4^{k+1}<4^4k!$, as required.

Theorem. If $n\ge 4$, then $4^nn<4^4n!$.
Proof. Just multiply both sides of (*) by $n$.