Strong induction problem solution to $n! > 2^n,$ is it correct?

Question

We are given: $$n! > 2^n$$ $$\forall n \geq 4 \space\space (n\in N) $$ Base case: $$4! > 2^4$$ $$24>16$$ Assumption: $$i! > 2^i$$ Inductive step: $$(i+1)!>2^{i+1}$$ $$i!(i+1)>2(2^i)$$ Now we want to know whether $(i+1)(2^i)$ is bigger than $2(2^i)$ $$(i+1)2^i > 2(2^i)$$ $$i2^i+2^i > 2(2^i)$$ $$(i-2)2^i+2^i>0$$ $$(i-2)2^i>-2^i$$ $$(i-2) > -1$$ $$(i > 1)$$ So now we know that $(i+1)2^i$ is bigger than $2(2^i)$ for i>1. Our assumption tells us that $(i)! > (2^i)$ is true for all $i \geq 4$.

My book gave a different answer but I think my way is also true.

Answer 1

You proof is valid.

But a few points.

i) First of all I hate stating what is to be proven first and working backwards.

We need to prove $(i+1)! > 2^{i+1}$. We can not assume it.

So working backwards:

$(i+1)! > 2^{i+1}$

$i(i+1)! > 2*2^{i}$.

etc. is not legitimate and when I see a student do it I am nearly always convinced they don't know what they are doing.

Especially if they end their proof with something like "... and $1 = 1$ which is true." That is utterly wrong and proves absolutely nothing (except "If the theorem is true than $1 = 1$" which is inane, banal, and pointless.)

You did not do that though. You said "Now we want to know whether" which implied you knew that we do not actually know this stuff yet and it is precisely that we need to know to reach our result.

But I'd prefer it if you had started from what we do know (that $i! > 2^i$) and work toward what we want to prove (that $(i+1)! > 2^{i+1}$) rather than the other way around.

In fact... I don't like you conclusion.

$i > 1$....

well, so what? That doesn't prove anything. We already knew $i > 1$. Just because you came to something true at the end means that what you started with was in the beginning was true.

The one thing you forget to say, that is absolutely essential is that each step can only be true if the next one is.

We aren't saying "If $(i+1)! > 2^{i+1}$ then $i!(i+1) > 2^i*2$". We are actually say the exact opposite. We are saying "We will know $(i+1)! > 2^{i+1}$ is true if we can know that $i!(i+1) > 2^i*2$".

And we continue "and we will know that is true if we know.... ". That way when we end with "and we will know that is true if we know $i > 1$" that is legitimate.

But it WONT work if we say "If $(i+1)! > 2^{i+1}$ then $i!(i+1) > 2^i*2$ and if that ..... then $x> 1$". "Ifs" only work in one direction and that is the wrong direction. We need "If $x > 1$ then .... then $i!(i+1) > 2^i*2$ and therefore $(i+1)! > 2^{i+1}$".

ii) This is picky of me but:

You say "Now we want to know whether $(i+1)(2^i)$ is bigger than $2(2^i)$".

Yes, if we can find that then we will be good. But if we can't find that, that doesn't mean we are stuck. It is sufficient that if $(i+1)2^i > 2*2^i$ we can get $i!(i+1) > (i+1)2^i > 2*2^i$ but it is not necessarily true. It could turn out (it doesn't but we don't know that yet) it could turn out that $i!(i+1) > 2*2^i > (i+1)2^i$ and we'd never be able to show $(i+1)2^i > 2*2^i$ because it wasn't true.

The thing is we need to prove $i!(i+1) > 2*2^i$ and if we can prove a stronger statement $i!(i+1) > (i+1)2^i > 2*2^i$ that will get us there. But because it is a stronger statement, it might not actually be true.

So I'd prefer acknowledgement like "it will be sufficient to show" or words to that affect.

iii)

You say "Now we want to know whether $(i+1)(2^i)$ is bigger than $2(2^i)$".

It'd be nice if you told us why.

I think it is good practice to get used to reducing statements to the former expression and putting them in directly.

We are given that $i! > 2^i$

And so we want to show $(i+1)! > 2^{i+1}$

So we know $(i+1)! = i!(i+1)$. At this point we know ONE thing about $i!$. We know $i! > 2^i$ so we should put that in right now.

$(i+1)! = i!(i+1) < 2^i(i+1)$.

iv) "Now we want to know whether $(i+1)(2^i)$ is bigger than $2(2^i)$"

But you do this in the most complicated and convoluted manner!

Since $i + 1 > 2$ and $2^i > 0$ then $(i+1)2^i > 2*2^i$

That's all.

===

So putting this together. I think the induction step would be clear and stronger if it were something like this:

We assume

$i! > 2^i$ therefore

$(i+1)! = i!(i+1)$

$> 2^i(i + 1); i > 1$

$> 2^i*2$

$= 2^{i+1}$.

So $i! > 2^i \implies (i+1)! > 2^{i+1}$ so the induction step is done.

....

But that's not to say your proof was wrong. It was fully correct. But it could be better.

Answer 2

You should actually use the hypothesis to reach the inductive step, the ideia it:

Since it's the hypothesis, you can claim: $$ i!>2^i $$

But given that, you still need to prove that $(i+1)!>2^{i+1}$. The way to do so is using the hypothesis:

Starting with: $$ i!>2^i $$

And since $(i+1)>2$: $$ (i+1)!>2^i (i+1)>2^i (1+1)>2^i (2)>2^{i+1} $$

Answer 3

It seems correct indeed from here

$$(i+1)!>2^{i+1}$$

you have used the inductive hypotesis to get

$$(i+1)!=(i+1)i!\stackrel{Ind. Hyp.}>(1+i)2^i\stackrel{?}>2\cdot2^i$$

which is true when $i+1>2\implies i>1$.

Note that it is not a strong induction but a "simple" induction.

Answer 4

You are done at this stage $$(i+1)2^i > 2(2^i)$$ because $$i+1 >2$$

There is no need for further analysis.

Answer 5

You can also write $\quad n!=\underbrace{1\times 2\times 3\times 4}_{>2^4}\times \underbrace{5}_{>2}\times \underbrace{6}_{>2}\cdots\times \underbrace{n}_{>2}>2^n\quad\forall n\ge 4$

This is the same induction proof, but more visual. You do not really need to write much more.

Remark that would you like to go on for $n! > 3^n$, this would be exactly the same.

$\quad n!=\underbrace{1\times 2\times 3\times 4\times 5\times 6\times 7}_{>3^7}\times \underbrace{8}_{>3}\times \underbrace{9}_{>3}\cdots\times \underbrace{n}_{>3}>3^n\quad\forall n\ge 7$