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