## Prove by induction 3^n < (n+2)!

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

jacksmack
Posts: 83
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

### Prove by induction 3^n < (n+2)!

Hi,
I have the following exercise:

Prove by induction the truth of the following statement:
P(n) : 3n < (n+2)! (for all n in N)

The statement P(n) is true for n=0:
30 < (0+2)!
1 < 2

Assuming P(n) true for a particular value of n, from the truth of P(n) we will try to prove the truth of P(n+1).
Multiplying both members of P(n) by 3, we obtain:
3n · 3 < 3(n+2)!
3n+1 < 3(n+2)!
3n+1 < (n+3)(n+2)! < (n+3)!

we have written (n+3) in the place of 3. And also:
n+3 > 3, therefore the direction of the inequality remains the same.
And also, since n!=n(n-1)! we have (n+3)! = (n+3)(n+2)!

In conclusion:
3n+1 < [(n+1)+2]!

This last statement confirm that P(n) is valid also for n+1 and therefore, by the principle of mathematical induction, P(n) is valid for all n in N
END.

I have some doubts here, and I have some questions to ask:
n+3 > 3, therefore the direction of the inequality remains the same.

why is it valid that substitution?
If we are considering by inductive hypothesis that n≥0,
considering n+3 > 3, and since n≥0, let's take for example n=0: substituting we obtain 3>3 that it is false!! why? please, can you explain me betters this matter? Many thanks!
Last edited by jacksmack on Mon Aug 10, 2015 5:16 pm UTC, edited 1 time in total.

gmalivuk
GNU Terry Pratchett
Posts: 26836
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Prove by induction 3^n < (n+2)!

If a < b, then 3a < (n+3)b even for n=0.

In other words, it is not true that n+3 > 3 (when n≥0). It is only true that n+3 ≥ 3. But that's good enough because multiplying by the same thing on both sides also maintains inequalities.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

jacksmack
Posts: 83
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

### Re: Prove by induction 3^n < (n+2)!

thanks for the answer!

gmalivuk wrote:If a < b, then 3a < (n+3)b even for n=0.

ok, it's clear

gmalivuk wrote:In other words, it is not true that n+3 > 3 (when n≥0).

ok!

gmalivuk wrote:It is only true that n+3 ≥ 3. But that's good enough because multiplying by the same thing on both sides also maintains inequalities.

Sorry. Not clear! Forgive me! We are talking about n+3 > 3! How you obtain that greater and equal in n+3 ≥ 3 ?

PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

### Re: Prove by induction 3^n < (n+2)!

With n = 0 it's equal and with n>0 it's greater than 3. So it's >=.

jacksmack
Posts: 83
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

### Re: Prove by induction 3^n < (n+2)!

PeteP wrote:With n = 0 it's equal and with n>0 it's greater than 3. So it's >=.

Yes, obviously! But in the exercise I posted, there is n+3 > 3! Is a typo? I don't think so! Therefore, what are the elements that bring me to talk about n+3 ≥ 3? What is the reasoning that I have to do?

PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

### Re: Prove by induction 3^n < (n+2)!

There is no 3! anywhere in your first post?

jacksmack
Posts: 83
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

### Re: Prove by induction 3^n < (n+2)!

PeteP wrote:There is no 3! anywhere in your first post?

3n+1 < (n+3)(n+2)! < (n+3)!

we have written (n+3) in the place of 3. And also:
n+3 > 3, therefore the direction of the inequality remains the same.
And also, since n!=n(n-1)! we have (n+3)! = (n+3)(n+2)!

it's ok that it is not true that n+3 > 3 (when n≥0).
What I don't understand is: if we still considering, (and if it is right to consider), n≥0 (since n≥0 by inductive hyphotesis), n+3 > 3 (when n≥0) is false!
Since n+3 > 3 has been written in the exercise, what is the reasoning that bring to me to consider n+3 ≥ 3 (as gmalivuk said)? Is present a typo error in the my exercise? Or is there any particular reasoning behind that?
Last edited by jacksmack on Mon Aug 10, 2015 6:39 pm UTC, edited 1 time in total.

Dopefish
Posts: 855
Joined: Sun Sep 20, 2009 5:46 am UTC
Location: The Well of Wishes

### Re: Prove by induction 3^n < (n+2)!

This may or may not be relevant to the case at hand (I just woke up and skimmed it), but some people consider N (the natural numbers) to be positive integers (1, 2, 3, ...) while others consider N to be the non-negative integers (0, 1, 2, ...). If things work as the book implies in the former case, but not quite in the latter (due to it technically being >= rather than >), then the book might be using the former definition (in which case you'd need to use 1 as your base case rather than 0, but that part is easy).

jacksmack
Posts: 83
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

### Re: Prove by induction 3^n < (n+2)!

Dopefish wrote:This may or may not be relevant to the case at hand (I just woke up and skimmed it), but some people consider N (the natural numbers) to be positive integers (1, 2, 3, ...) while others consider N to be the non-negative integers (0, 1, 2, ...). If things work as the book implies in the former case, but not quite in the latter (due to it technically being >= rather than >), then the book might be using the former definition (in which case you'd need to use 1 as your base case rather than 0, but that part is easy).

I understand, and it's no good! I have lost some time on it!

Let's try another method:
Considering P(n) we go to multiply both members by (n+3):
3n(n+3) < (n+3)(n+2)!
But from this, how can I obtain P(n+1) : 3n+1 < (n+3)! ?

Sizik
Posts: 1261
Joined: Wed Aug 27, 2008 3:48 am UTC

### Re: Prove by induction 3^n < (n+2)!

jacksmack wrote:
Dopefish wrote:This may or may not be relevant to the case at hand (I just woke up and skimmed it), but some people consider N (the natural numbers) to be positive integers (1, 2, 3, ...) while others consider N to be the non-negative integers (0, 1, 2, ...). If things work as the book implies in the former case, but not quite in the latter (due to it technically being >= rather than >), then the book might be using the former definition (in which case you'd need to use 1 as your base case rather than 0, but that part is easy).

I understand, and it's no good! I have lost some time on it!

Let's try another method:
Considering P(n) we go to multiply both members by (n+3):
3n(n+3) < (n+3)(n+2)!
But from this, how can I obtain P(n+1) : 3n+1 < (n+3)! ?

We know that 3 <= (n+3) for n >= 0. Multiply both sides by 3n, and we get:
3n+1 <= 3n(n+3)
So, with respect to our original inequality:
3n+1 <= 3n(n+3) < (n+3)(n+2)! = (n+3)!
Cutting out the middle term leaves us with
3n+1 < (n+3)!
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

### Re: Prove by induction 3^n < (n+2)!

The key is that from a <= b and b < c, we can conclude a < c. We only need *one* of the inequalities to be strict.

Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

### Re: Prove by induction 3^n < (n+2)!

Instead of just doing n=0, do n=1 explicitly and we see that 3 < 6. This means in addition to the inductive hypothesis we can can assume that n > 1 which implies n+2 > 3, which mean 3^(n+1) = 3 * 3^n < 3*(n+1)! < (n+2)(n+1)! = (n+2)! which was to be shown.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

theBuddha7
Posts: 1
Joined: Wed Aug 19, 2015 3:13 pm UTC

### Re: Prove by induction 3^n < (n+2)!

Prove: 3n < (n+2)! for n ⊂ ℕ.

Base Case: n = 0
30 = 1 < 2 = (0+2)!
∴ 3n < (n+2)! for n = 0

Case: n+1
3(n+1) = 3*3n
We know 3n < (n+2)!
∴ 3*{3n} < 3*{(n+2)!}
If 3*(n+2)! ≤ (n+3)! then we're done as 3*3n < 3*(n+2)! ≤ (n+3)!
3*(n+2)! ¿? (n+3)!
RHS: (n+3)! = (n+3)*(n+2)!
so 3*(n+2)! ¿? (n+3)*(n+2)!
divide by (n+2) on both sides, noting n ⊂ ℕ ∴ (n+2)! ≥ 1 ≠ 0
3 ¿? (n+3)
3 ≤ (n+3)
∴ 3*(n+2)! ≤ (n+3)!
∴ 3*3n < 3*(n+2)! ≤ (n+3)!
∴ 3*3n < (n+3)!
or 3(n+1) < [(n+1)+2]!∎

It's been 7 years since I've written a proof, so apologies if the structure isn't quite right, but I do believe the original post contains a typo and that it should be 3 ≤ (n + 3), with a less than or equal to sign, not a strictly less than sign. Then skullturf's point of a ≤ b and b < c ∴ a ≤ c can be applied as 3*3n < 3*(n+2)! ≤ (n+3)!
Edit: formatting of superscript tags.

Return to “Mathematics”

### Who is online

Users browsing this forum: No registered users and 5 guests