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

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

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

Postby jacksmack » Mon Aug 10, 2015 4:53 pm UTC

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.

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

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

Postby gmalivuk » Mon Aug 10, 2015 5:16 pm UTC

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)

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

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

Postby jacksmack » Mon Aug 10, 2015 5:29 pm UTC

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 ?

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

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

Postby PeteP » Mon Aug 10, 2015 5:46 pm UTC

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

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

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

Postby jacksmack » Mon Aug 10, 2015 5:55 pm UTC

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?

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

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

Postby PeteP » Mon Aug 10, 2015 6:06 pm UTC

There is no 3! anywhere in your first post?

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

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

Postby jacksmack » Mon Aug 10, 2015 6:28 pm UTC

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.

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

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

Postby Dopefish » Mon Aug 10, 2015 6:39 pm UTC

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).

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

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

Postby jacksmack » Mon Aug 10, 2015 7:06 pm UTC

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)! ?

User avatar
Sizik
Posts: 1156
Joined: Wed Aug 27, 2008 3:48 am UTC

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

Postby Sizik » Mon Aug 10, 2015 7:39 pm UTC

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)!
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)!

Postby skullturf » Tue Aug 11, 2015 2:45 pm UTC

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.

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

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

Postby Cleverbeans » Wed Aug 12, 2015 3:51 am UTC

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)!

Postby theBuddha7 » Wed Aug 19, 2015 4:34 pm UTC

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 15 guests