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 $\displaystyle \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 \displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}$. Then
$\displaystyle \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*}$
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 $\displaystyle \displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}$.
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 $\displaystyle \displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}$ then $\displaystyle \displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 + 3k^2 + 3k + 1 \end{align*}$.
Re: Proof By Induction, n^3>2n+1
Quote:
Originally Posted by
Prove It If $\displaystyle \displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}$ then $\displaystyle \displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 + 3k^2 + 3k + 1 \end{align*}$.
Shouldnt it just be
$\displaystyle \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.
Re: Proof By Induction, n^3>2n+1
Quote:
Originally Posted by
RadMabbit Shouldnt it just be
$\displaystyle \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 \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.
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.