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

Printable View

October 4th 2012, 04:05 PM
RadMabbit

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!
October 4th 2012, 04:51 PM
Prove It

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

Well first off, you don't write $\displaystyle \begin{align*} ( k + 1) ^3 > 2(k + 1) + 1 \end{align*}$ , 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 $\displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}$ . Then

$\displaystyle \begin{align*} (k + 1)^3 &= k^3 + 3k^2 + 3k + 1 \\ &> 2k + 1 + 3k^2 + 3k + 1 \\ &= 2k + 2 + 3k^2 + 3k \\ &= 2(k + 1) + 3k( k + 1) \\ &> 2(k + 1) + 1 \textrm{ since } k > 1 \implies 3k(k + 1) > 1 \end{align*}$
October 4th 2012, 04:54 PM
RadMabbit

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

^
|
|

this guy....
October 4th 2012, 04:55 PM
Prove It

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

Quote:

Originally Posted by RadMabbit

^
|
|

this guy....

What value of n did you use in your base step?
October 4th 2012, 05:21 PM
RadMabbit

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

Quote:

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
October 4th 2012, 05:27 PM
Prove It

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

Quote:

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.
October 4th 2012, 05:30 PM
RadMabbit

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

just got a little confused... where did the k^3 go?
October 4th 2012, 05:33 PM
Prove It

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

Quote:

Originally Posted by RadMabbit

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

In the inductive step you assume $\displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}$ .
October 4th 2012, 05:37 PM
RadMabbit

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

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....
October 4th 2012, 05:48 PM
Prove It

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

Quote:

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 $\displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}$ then $\displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 + 3k^2 + 3k + 1 \end{align*}$ .
October 4th 2012, 05:57 PM
RadMabbit

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

Quote:

Originally Posted by Prove It

If $\displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}$ then $\displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 + 3k^2 + 3k + 1 \end{align*}$ .

Shouldnt it just be

$\displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 \end{align*}$ .

Im confused about where you got all the other stuff, as I already incorporiated the k+1 into the 2n+1 at the start.
October 4th 2012, 06:10 PM
Prove It

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

Quote:

Originally Posted by RadMabbit

Shouldnt it just be

$\displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 \end{align*}$ .

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

$\displaystyle \begin{align*} k^3 &> 2k + 1 \\ k^3 + 3k^2 &> 2k + 1 + 3k^2 \\ k^3 + 3k^2 + 3k &> 2k + 1 + 3k^2 + 3k \\ k^3 + 3k^2 + 3k + 1 &> 2k + 1 + 3k^2 + 3k + 1 \end{align*}$

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.
October 4th 2012, 08:22 PM
Deveno

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

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.