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