Simple Proof by Induction: Question About Formulation of the Inductive Step.

Question

Prove $n^2 > n+1, n\geq2$:

Basis: n = 2

$n^2 > n+1$

$2^2 > 2+1$

$4>3$

Inductive Hypothesis: Assume P(k) is true, i.e.,

$k^2 > k+1$

Inductive Step: Show P(k+1) is true, i.e.,

$(k+1)^2 > (k+1) + 1$

$k^2 + 2k + 1 > (k+1) + 1$

$k^2 + 2k + 1 > k + 2$

$k^2 + 2k > k+1$

$k(k+2) > k + 1$

I know that I need to try and get the expression to read $k^2 > k+1$. The steps above are the closest I could get. Can some explain if my format for inductive proofs is correct and point me in the right direction to completing the proof?

Answer 1

Format-wise, I think what you're doing is perfectly fine. I think some more wording would be appropriate though: for instance, the way you have your inductive step written, it almost seems like you're assuming the inequality holds at every step along the way. Usually, I would start at the left-hand side and do manipulations to verify the right-hand side does hold (or the reverse). Still, don't be afraid to use words: being able to explain what you're doing and why is very important in proof-writing!

---

So, on the premise $k^2 > k+1$, you wish you show $(k+1)^2 > k+2$. We see that

$$(k+1)^2 = k^2 + 2k + 1$$

Invoking the induction hypothesis ($k^2 > k+1$), we see that

$$k^2 + 2k + 1 > k+1 + 2k + 1 = 3k + 2 > k+2$$

(for which the inequality holds since $k$ is assumed positive). Thus, $(k+1)^2 > k+2$ as desired.

Answer 2

$$(k+1)^2=k^2+2k+1>k+1+2k+1>(k+1)+1.$$

Answer 3

In an induction step you will have $k^2 > k+1$ and you will need to use is

So We want to show $(k+1)^2 > k+2$ or $k^2 + 2k + 1 > k+1$.

How can we use $k^2 + 1 > k+1$ to do that.

Well $k^2 + 2k + 1 = (k^2)+2k+1 > (k+1)+3k + 1 = 4k+2$.

So if we can somehow prove that $4k + 2 > (k+1) + 1$ we will be done.

......

Alternatively

$k^2 > k+1$ so

$k^2 + 1 > k + 2$

$k^2 + 2k + 1 > k^2 +1 > k+2$

$(k+1)^2 = k^2 + 2k+ 1 > k^2 + 1 > k+2$.

========

But to complete YOUR proof they way YOU are doing it.

First we can't start with assuming what we want to prove UNLESS every step is invertable. We can't say CONCLUSION implies PREMISE. But we can do CONCLUSION is implied by PREMISE or, if it is true, CONCLUSION if and only if PREMISE.

So what you say is:

$(k+1)^2>(k+1)+1\iff$

$k^2+2k+1>(k+1)+1\iff$

$k^2+2k+1>k+2\iff$

$k^2+2k>k+1\iff $

$k(k+2)>k+1$.

Now as $k > 1$ and $k+2 > 0$ then

$k(k+2)>k+1 \Leftarrow$ (is implied by; this is not an if and only if)

$k(k+2) > 1*(k+2) > k+1 \Leftarrow$

$k+2 > k+1 \iff$

$2>1$.

.....

If you want to look like a rock star write that backwards.

$2 > 1 \implies$

$k+2 > k+1$ and as $k > 1;k+2>0\implies$

$k(k+2) > 1*(k+2) = k+2>k+1\implies

$k^2 + 2k > k+1\implies$

$k^2 + 2k + 1> k+2\implies$

$(k+1)^2 > (k+1)+1$.

.....

and actually if you did that you notice you didn't even use induction.

---

So a non-inductive proof could be:

$1> 0\implies$

$k+1> k\implies$

$k+k > k+1\implies$

$2k > k+1\implies$

$k*k \ge 2k > k+1\implies$

$k^2 > k+1$

Or to pare it down to a single line:

$k\ge 2>1$ so

$k^2 \ge 2*k = k+k > k+1$.

QED