2
$\begingroup$

I am having some serious trouble figuring out this induction problem. I've tried following other problems and can not seem to get the end result or understand it sufficiently.

My attempt:

Theorem: For all integers $n≥2, n^3 > 2n + 1$

Proof: We will prove this by induction. Let $P(n)$ be the statement: $n^3 > 2n + 1$. We will show $P(2)$ is true. When we let $n = 2, 2^3 = 8$ and $2(2) + 1 = 5$, so we know $P(2)$ to be true for $n^3 > 2n + 1$.

Induction Step: Suppose $P(k)$ is true for some integer $k≥2$, then $k^3>2(k)+1$. We wish to show that $P(k+1)$ is true, that is $(k+1)^3>2(k+1)+1$. We then factor it out to be $k^3 + 3k^2 + 3k + 1 > 2k + 3$. I am stuck from here. Any help would be great, thank you.

$\endgroup$
  • $\begingroup$ $k^{3}+3k^{2}+3k+1>k^{3}+3k+1>(2k+1)+3k+1>2k+1+1+1=2k+3$ $\endgroup$ – Shoutre May 10 '16 at 22:38
  • $\begingroup$ Welcome to MSE. You will definitely want to bookmark this link for future use on typesetting math. It will make your question(s) easier to read and more likely to receive help. $\endgroup$ – Daniel W. Farlow May 10 '16 at 22:39
1
$\begingroup$

Here is the main part of the inductive step: \begin{align} (k+1)^3 &= k^3+3k^2+3k+1\tag{expand}\\[1em] &> (2k+1)+3k^2+3k+1\tag{by inductive hypothesis}\\[1em] &> 2k+2+1\tag{since $k\geq2$}\\[1em] &= 2(k+1)+1\tag{rearrange} \end{align}

$\endgroup$
  • $\begingroup$ Could you explain how you determined (2k+1)+3k^2+3k+1 > 2k + 2 + 1. I see you said since k ≥ 2, but I don't quite understand how that gives you 2k+2+1 $\endgroup$ – CaSrBa May 10 '16 at 23:52
  • $\begingroup$ To see that $(2k+1)+3k^2+3k+1>2k+2+1$, simply note the following: $2k+1>2k; 3k^2>2; 3k>1; 1>0$. $\endgroup$ – Daniel W. Farlow May 11 '16 at 0:28
1
$\begingroup$

Here is a conceptual way of viewing the proof that makes it obvious, and works very generally. First construct the obvious inductive proof of the following Lemma

$\rm\:f(n) > 0\:$ for $\rm\:n\ge 2\ $ if $\rm\ f(2)> 0\:$ and $\rm\,f\,$ is increasing, i.e. $\rm\: f(n\!+\!1) \ge f(n)\:$ for $\rm\:n\ge2.\:$

So to show $\rm\:f(n) = n^3\!-2n-1> 0\:$ it suffices to show $\rm\: f(n\!+\!1)-f(n) = 3n^2\!+3n-1 \ge 0\:$ for $\rm\:n\ge 2,\:$ and $\,\rm f(2)>0,\,$ which is easy.

For many more examples see my posts on telescopy.

$\endgroup$
0
$\begingroup$

To prove the inductive step, expand so that we have $$k^3 + 3k^2 + 3k + 1 > 2k + 3$$

By hypothesis, $k^3 > 2k+1$. It thus suffices to show $3k^2 + 3k + 1 > 2$, or, equivalently, $3(k + \frac{1}{2})^2 - \frac{7}{4} > 0$ which holds for $k\geq2$

$\endgroup$
  • $\begingroup$ I want to make sure I understand this. So 3k2+3k+1>2, so is it solved by saying 3k2+3k-1>0. $\endgroup$ – CaSrBa May 10 '16 at 22:52
  • $\begingroup$ @xXNathan360Xx Well, they're equivalent statements. Adding or subtracting numbers from an inequality doesn't change anything. $\endgroup$ – MathematicsStudent1122 May 10 '16 at 22:53
  • $\begingroup$ So would I end this proof by saying: Since we know 3k^2+3k+1 > 2, we know that the original statement is true as well? $\endgroup$ – CaSrBa May 10 '16 at 22:56
  • $\begingroup$ @xXNathan360Xx Basically. You're using the fact that $a>b, c>d \Longrightarrow a+c>b+d$. $\endgroup$ – MathematicsStudent1122 May 10 '16 at 23:07
  • $\begingroup$ So I can say: k^3+3k^2+3k+1>2k+3 since k^3 > 2k+3 and we know 3k^2+3k+1>2, due to a > b and c > d thus a + c > b + d. $\endgroup$ – CaSrBa May 10 '16 at 23:20
0
$\begingroup$

You don't have to do it by induction. You can also look at $n^3-2n-1$.

$n^3-2n-1=n^3-n-n-1=n(n-1)(n+1)-(n+1)=(n+1)(n^2-n-1)=(n+1)(n^2-2n+1+n-2)=(n+1)(n-1)^2+(n+1)(n-2)>0$

We know from the condition $n\ge2$ that $n+1$ has to be positive, $(n-1)^2$ is always positive and so is $n-2$. So it's clear why the whole term has to be positive for $n\ge2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.