Proof By Induction, n^3>2n+1
Hey all
Having an issue with a proof by induction. Here is the question:
n^{3}>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!
Re: Proof By Induction, n^3>2n+1
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
Re: Proof By Induction, n^3>2n+1
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?
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^{3}>2*3+1
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^{3}>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.
Re: Proof By Induction, n^3>2n+1
just got a little confused... where did the k^3 go?
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 .
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....
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 then .
Re: Proof By Induction, n^3>2n+1
Quote:
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.
Re: Proof By Induction, n^3>2n+1
Quote:
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.
Re: Proof By Induction, n^3>2n+1
just so it's 100% clear.
the "general shape" of an induction proof is:
P(n_{0}) is true. (here, n_{0} 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_{0}.
********
here, P(n) means: n^{3} > 2n+1
since P(1) translates to: 1 > 3 (which is false), we cannot use n_{0} = 1.
P(2) translates to: 8 > 5, which IS true, so perhaps n_{0} = 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^{3} > 2k+1.
therefore:
(k+1)^{3} = k^{3} + 3k^{2} + 3k + 1 > (2k+1) + 3k^{2} + 3k + 1.
what we WANT to show is:
(k+1)^{3} > 2(k+1) + 1 = 2k + 3.
if we knew that 3k^{2} + 3k  1 > 0, then we would have:
(k+1)^{3} > (2k+1) + 3k^{2} + 3k + 1 = 2k + 3 + 3k^{2} + 3k  1 > 2k + 3 + 0 = 2k + 3, by transitivity of ">".
now 3k^{2} + 3k  1 > 0 is the same as:
3k^{2} + 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^{2} + 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^{3} > 2k + 1, THEN it follows that (k+1)^{3} = 2k + 3 + (3k^{2} + 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^{3} > 2n + 1.
*************
as one might guess, one really doesn't "need" induction to prove this:
suppose n ≥ 2.
then n^{3} = n(n^{2}) ≥ 2(n^{2}) = 2(n)(n) = n^{2} + n^{2} > n^{2} + n
(since n ≥ 2, so n > 1, so n^{2} = (n)(n) > (n)(1) = n),
≥ n^{2} + 2 > n^{2} + 1 = (n)(n) + 1 ≥ 2n + 1.