# Math Help - Proof By Induction, n^3>2n+1

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

Hey all

Having an issue with a proof by induction. Here is the question:
n3>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)3>2(k+1)+1 - this is as far as I got.

Any help would be greatly appreciated!

2. ## 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*}

^
|
|

this guy....

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

^
|
|

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

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

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.

23>2*3+1

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

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

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

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

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

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

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

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

10. ## 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....
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*}.

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

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.

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

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.

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

just so it's 100% clear.

the "general shape" of an induction proof is:

P(n0) is true. (here, n0 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 ≥ n0.

********

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

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

P(2) translates to: 8 > 5, which IS true, so perhaps n0 = 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:

k3 > 2k+1.

therefore:

(k+1)3 = k3 + 3k2 + 3k + 1 > (2k+1) + 3k2 + 3k + 1.

what we WANT to show is:

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

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

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

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

3k2 + 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, 3k2 + 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 k3 > 2k + 1, THEN it follows that (k+1)3 = 2k + 3 + (3k2 + 3k - 1) > 2k + 3 = 2(k+1) + 1.

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

n3 > 2n + 1.

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

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

suppose n ≥ 2.

then n3 = n(n2) ≥ 2(n2) = 2(n)(n) = n2 + n2 > n2 + n

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

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