Can someone check my induction proof of $n^2 > 2n + 1$ for all $ n \geq 3$.

Question

I have been studying proof by induction and I came across this proof: Prove that for all integers $n ≥ 3$, $$n^2 > 2n + 1.$$

Proof: It’s obvious that the above statement holds for $n = 3$. Thus, we can assume that it holds for $n = k$ and prove that it holds for $n = k+1$, which means $(k + 1)^2 > 2(k + 1) + 1$, which is the same expression as $k^2 + 2k + 1 > 2k + 3$. Simplifying the expression leaves us with $k^2 > 2$. But since $n = k$ must be $≥ 3$, $k^2 > 2$, thus completing the proof. □

I checked the answer to the proof and it was different from mine. But I still fail to see what's wrong with my proof. Could someone please point it out for me?

Thanks in advance.

Answer 1

There is nothing seriously wrong with your proof, in your inductive step however you end up just proving the statement directly, but there is nothing wrong with this as it does still prove the implication

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

Which is technically what is required for a proof by induction, or at least for you to apply the statement of mathematical induction, but there are some things you might want to improve on in the proof of the inductive step:

Usually, "expression" is used to refer to some combination of symbols and operations and relations between them. Two expressions are the same when they are...the same... so the expression

$$ x+1 $$

Is not the same as

$$ x+1+0$$

But in some contexts, these expressions are associated with the same object. What you were comparing are what is usually referred to as statements, and we don't talk about statements being the same, but rather about statements being equivalent to another, or some statement implying another. This is an important distinction because if one were to interpret your proof entirely formally you would probably venture that what you meant is this:

\begin{align} &(k+1)^2 > 2(k+1) +1 \\\\ \implies & k^2 +2k + 1 > 2k + 3 \\\\ \implies & k^2 > 2 \\\\ \impliedby & k>3 \\ \end{align}

And since we know $k>3$, we can conclude

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

And this proof is definitely not correct, since

$\alpha \implies \beta$

and

$\gamma \implies \beta $

does not mean that

$\gamma \implies \alpha $

If $\implies $ is still an unfamiliar concept for you, you can imagine thinking of statements as being on different "heights", if $\alpha \implies \beta$ then $\alpha$ is higher than $\beta$, and now it's clear why this doesn't make any sense. If I am higher than Bob, and you are higher than Bob, we can't conclude anything about the relative height between you and me. this can be fixed if at every step you replace $\implies$ with $\iff$, since

\begin{align} &(k+1)^2 > 2(k+1) + 1 \\\\ \iff & k^2 + 2k +1 > 2k + 3 \\\\ \end{align}

For example, and indeed this may have been what you meant when you said the expressions are the same, but for the sake of clarity it is probably better to start with a statement that you know, and end with the statement that you want to conclude through a chain of implications, so a rewritten version of your proof could be:

Since $k>3$ we know that $k^2>2$, and so we can conclude that

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

And so adding $1$ on both sides,

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

But this implies that

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

And so the implication

$$ k> 3 \land k^2 > 2k+1 \\ \implies (k+1)^2 > 2(k+1) + 1 $$

Is true, which allows you to conclude using the principle of mathematical induction that

$$ n^2 > 2n+1 $$

For any $n>3$.

Here it is entirely clear that I proved the implication, and there is no room for incorrect interpretation, however, it is entirely unnecessary to use induction here, but induction was technically used. You'll have to ask your course convenor if they would accept such a proof, some might appreciate you noticing that it is still technically inductive, and others might be confused by what you're even asking, in which case it is better to follow the type of approach given in one of the other ansers

Answer 2

According to induction hypothesis the statement is true for $n=k$ i.e., $k^2 > 2k+1$. Now we have to show it is true for $n=k+1$ i.e., $(k + 1)^2 > 2(k + 1) + 1$. \begin{align*} (k + 1)^2 &= k^2+2k+1\\ &> (2k+1)+2k+1 ~ ~ ~ ~ ~ [\text{From induction hypothesis } k^2 > 2k+1]\\ &= 2k + 2k + 2\\ &= 2(k + 1) + 2k\\ &>2(k + 1) + 1 ~ ~ ~ ~ ~ [\text{Since } 2k > 1, ~\forall k\geq 3] \end{align*} Therefore, we get $(k + 1)^2 > 2(k + 1) + 1$ for all $k \geq 3$.

Answer 3

Your proof is not a proof by induction !

In order to do a proof by induction you should be proving that

For $n = 3$ $$ n^2 > 2 n + 1$$ and for all $k \geq 3 :$ $$ k^2 >2k + 1 \implies (k+1)^2 > 2(k+1) +1$$

You can check out A Sahoo's answer to see such a proof.

Instead of this you have proven

For $n = 3$ $$ n^2 > 2 n + 1$$ and $$ k \geq 3 \implies (k+1)^2 > 2(k+1) +1.$$

by using the fact that

$k \geq 3 \implies k^2 > 2 $ and $ k^2 \geq 2 \iff (k+1)^2 > 2(k+1) +1.$

In particular you proof does have as a consequence that for all $n \geq 3$ we have $$ n^2 > 2n + 1$$ but it is not a proof by induction.

Answer 4

You are assuming the consequent: If your induction assumption is: $k^2>2k+1$

You can not start from: $(k+1)^2>2(k+1)+1$

Since this is what you have to prove. Start from your assumption: $k^2>2k+1$

Now adding the same number to both sides does not change the inequality:

$k^2+2k+1>2k+1+2k+1=2(2k+1)$ Now:

$4k+2-(2(k+1)+1)=2k-1>0$

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