Thread: Proof By Induction, n^3>2n+1

Hey all

Having an issue with a proof by induction. Here is the question:
n³>2n+1

I got through the basis step, induction hypothesis step, but really struggled with understanding how to prove it. Have looked around at similar answers, but I believe I am just missing the key part of knowing what to do.

(k+1)³>2(k+1)+1 - this is as far as I got.

Any help would be greatly appreciated!

Well first off, you don't write , you write down ONE side of this and go through a series of steps to arrive at the other side.

What you need to do is make the assumption that P(k) is true, i.e. that . Then

^
|
|

this guy....

Originally Posted by RadMabbit

^
|
|

this guy....

What value of n did you use in your base step?

Originally Posted by Prove It

What value of n did you use in your base step?

Ah sorry, forgot to write it was for all integers n>=2, so I used 2.

2³>2*3+1

Originally Posted by RadMabbit

Ah sorry, forgot to write it was for all integers n>=2, so I used 2.

2³>2*3+1

Yes, that's fine. I realised at the last minute that it didn't hold for n = 1, so I thought I'd better ask.

just got a little confused... where did the k^3 go?

Originally Posted by RadMabbit

just got a little confused... where did the k^3 go?

In the inductive step you assume .

ok, you kinda lost me with your process. I feel like you just moved everything from one side to the other for no real reason....

Originally Posted by RadMabbit

ok, you kinda lost me with your process. I feel like you just moved everything from one side to the other for no real reason....

If then .

Originally Posted by Prove It

If then .

Shouldnt it just be

.

Im confused about where you got all the other stuff, as I already incorporiated the k+1 into the 2n+1 at the start.

Originally Posted by RadMabbit

Shouldnt it just be

.

Im confused about where you got all the other stuff, as I already incorporiated the k+1 into the 2n+1 at the start.

Even though that is a correct inequality, it won't help you out in this case. The reason why mine is correct is...



This is the whole principle of mathematical induction. You make an assumption, then SUBSTITUTE THAT ASSUMPTION and do some algebraic manipulation to get what you need.

just so it's 100% clear.

the "general shape" of an induction proof is:

P(n₀) is true. (here, n₀ represents the "base case").

if P(k) is true, then P(k+1) is true (no matter "what" natural number k is).

therefore, P(n) is true for all natural numbers n ≥ n₀.

********

here, P(n) means: n³ > 2n+1

since P(1) translates to: 1 > 3 (which is false), we cannot use n₀ = 1.

P(2) translates to: 8 > 5, which IS true, so perhaps n₀ = 2 is a reasonable place to start.

now for the "P(k) implies P(k+1)" step.

if P(k) was true (that is: assume for the time being that it is), then:

k³ > 2k+1.

therefore:

(k+1)³ = k³ + 3k² + 3k + 1 > (2k+1) + 3k² + 3k + 1.

what we WANT to show is:

(k+1)³ > 2(k+1) + 1 = 2k + 3.

if we knew that 3k² + 3k - 1 > 0, then we would have:

(k+1)³ > (2k+1) + 3k² + 3k + 1 = 2k + 3 + 3k² + 3k - 1 > 2k + 3 + 0 = 2k + 3, by transitivity of ">".

now 3k² + 3k - 1 > 0 is the same as:

3k² + 3k > 1, or:

(3k)(k+1) > 1. now, we know that we are only considering k > 1, so (3k)(k+1) > (3k)(2) > (3)(2) = 6 > 1.

so since for any k > 1, (3k)(k+1) > 1, 3k² + 3k - 1 > 0.

(if we really wanted to punish ourselves, we could prove THIS by induction as well. we'd probably have to use more letters to avoid confusion).

so IF k³ > 2k + 1, THEN it follows that (k+1)³ = 2k + 3 + (3k² + 3k - 1) > 2k + 3 = 2(k+1) + 1.

thus we can now apply to principle of induction to conclude that for ALL n ≥ 2:

n³ > 2n + 1.

*************

as one might guess, one really doesn't "need" induction to prove this:

suppose n ≥ 2.

then n³ = n(n²) ≥ 2(n²) = 2(n)(n) = n² + n² > n² + n

(since n ≥ 2, so n > 1, so n² = (n)(n) > (n)(1) = n),

≥ n² + 2 > n² + 1 = (n)(n) + 1 ≥ 2n + 1.