# Thread: Does this inductive proof make sense?

1. ## Does this inductive proof make sense?

I'm trying to prove by way of induction that:

$\displaystyle n! > 2^n$ $\displaystyle for$ $\displaystyle n \geq 4$

The base case is obviously true as $\displaystyle 24 > 16$
I then took the inductive step and came up with the following:

$\displaystyle (k + 1)! > 2^{k+1}$

$\displaystyle = (k + 1)*k! > 2*2^k$

I then figured that if $\displaystyle k! > 2^k$ (assumption), then if the amount that the LFH is being multiplied by each time is > the amount that the RHS is being multiplied by each time, then the LHS must always be > RHS and the statement is true.

So if:

$\displaystyle (k + 1) > 2$

then the original statement is true.

Since $\displaystyle n \geq 4$ then the LHS multiple is always > 4 which is > 2 (RHS multiple), therefore the LHS is always greater than the RHS and the statement is true.

Is this a valid proof? What are some other ways I could prove this?

Thanks.

2. ## Re: Does this inductive proof make sense?

Originally Posted by terrorsquid
Is this a valid proof?
Yes.

3. ## Re: Does this inductive proof make sense?

Originally Posted by alexmahone
Yes.
Is it an inductive proof because I took the inductive step? I thought that I had to show how to go to the next step in the chain from an arbitrary point to prove it via induction as opposed to just using general logic like I did above?

4. ## Re: Does this inductive proof make sense?

Without induction.

Lemma:

$\displaystyle \sum _{n=1}^{\infty}\frac{2^n}{n!}<\infty$

Proof:

We use, d'Alembert limit test.

$\displaystyle a_n=\frac{2^n}{n!}$

$\displaystyle \lim_{n\to\infty}\frac{a_{n+1}}{a_n}=\lim_{n \to \infty } \frac{\frac{2^{n+1}}{(n+1)!}}{\frac{2^n}{n!}}=\lim _{n\to\infty}\frac{2}{n+1}=0<1$

Hence, $\displaystyle \sum _{n=1}^{\infty}\frac{2^n}{n!}<\infty$.

From lemma 1:

$\displaystyle \lim_{n\to\infty}\frac{2^n}{n!}=0$

hence, by limit definition, there exist $\displaystyle n_0\in\mathbb{N}$, such that for all $\displaystyle n>n_0$

$\displaystyle \left|\frac{2^n}{n!}\right|<1$, $\displaystyle n_0=5$

5. ## Re: Does this inductive proof make sense?

You have the right idea, but should not have written at the start

(k+1)! > 2^(k+1)

That is what you want to PROVE, so don't state it first as if it's already been proven.

Rather, you could write it this way:

Suppose (as the inductive hypotheis) k! > 2^k.

And k+1 > 2.

So, by monotonicity, (k+1)! = (k+1)k! > 2(2^k) = 2^(k+1).

6. ## Re: Does this inductive proof make sense?

Originally Posted by MoeBlee
You have the right idea, but should not have written at the start

(k+1)! > 2^(k+1)

That is what you want to PROVE, so don't state it first as if it's already been proven.

Rather, you could write it this way:

Suppose (as the inductive hypotheis) k! > 2^k.

And k+1 > 2.

So, by monotonicity, (k+1)! = (k+1)k! > 2(2^k) = 2^(k+1).
Ok, thanks. That makes sense, I guess I was just trying to show my thought process of how I got to the proof by writing it out like that.

I have another example and I didn't quite understand the steps given in the notes so I tried to apply a similar method to the new statement; I was wondering if it was also valid and if I post the notes that maybe someone could understand these notes.

Show $\displaystyle 2^n \geq n^2 for$ $\displaystyle n \geq 4$

My proof:

Base case is true.

Induction step = assume $\displaystyle 2^n \geq n^2$ and test whether $\displaystyle 2^{n+1} \geq (n+1)^2$

Similar to my other proof, given my assumption, if the change in the LFH >= the change in the RHS then the statement must be true, i.e., if

$\displaystyle 2^n \geq 2n + 1$

then the statement is true. Since $\displaystyle n \geq 4$ the LHS >= 16 > 9 (RHS), the statement is true. Although I don't feel like I have PROVEN it for all changes in each side.

Notes I have on this:

$\displaystyle 2^{n+1} \geq 2*2^n \geq 2n^2 = n^2 + nn \geq n^2 +4n = n^2 + 2n + 2n \geq n^2 + 2n +1 = (n+1)^2$

Hence T(n) implies T(n+1)

I didn't understand the step to n^2 + 4n.

Sorry if I made some mistakes above, posting this in between classes - rushing.

Thanks.

7. ## Re: Does this inductive proof make sense?

Originally Posted by terrorsquid
I was just trying to show my thought process
When you want to mention various objectives in the proof, use a word like 'show'.

For example:

Show that if k>=4 then k! > k^2.
By induction on k:
Base case. 4! > 4^2.
Induction hypothesis: k! > k^2.
Show that (k+1)! > 2^(k+1).
etc...

So, always make clear to the reader whether a formula is something you WANT to show as opposed to something you HAVE shown. If you mention a formula without such qualification, the reader should be allowed to take it that the formula is something that has already been proven, either previously in the subject or in your own proof.

8. ## Re: Does this inductive proof make sense?

Without induction.

_______________________
The Leverage Season 5 DVD crew helps a veteran hockey player who thinks team management!