Using induction to prove that $n^2 > n + 1$ for $n\geq2$

Question

Use mathematical induction to prove that $n^2 > n + 1$ for all $n\geq2.$

I have proved that it is true for the initial case $n=2$ as $4>3$, and have assumed the statement to be true for $k^2 > k + 1$ where $k\geq 2$.

So I need to prove that $(k + 1)^2 >(k + 1) + 1$.

My thought process for this was first to expand $(k + 1)^2$, which equals $k^2 + 2k + 1.$ Therefore we have $k^2 + 2k + 1 > (k + 1) + 1.$

I noticed that there is a $k^2$ term and a $k+1$ term and we established from the initial equation that $k^2 > k + 1$. This left me with $2k + 1 > 1$, which we know is true as $k\geq 2$.

Is this an appropriate method of proving this statement to be true, or is it not advisable to split the inequality into multiple terms?

Answer 1

It looks nicer if you from one side of the expression derives the other: \begin{equation}(k+1)^2 = k^2+2k+1 \stackrel{\text{IH}}{>} k+1 + 2k +1 = k+2 + 2k > k+2 \end{equation}

But yes, your method is fine.

Answer 2

There really is only one minor issue with your proof:

[...] and have assumed the statement to be true for $k^2>k+1$ where $k\geq 2$.

Ah, but isn't that what you are actually trying to prove? That is, it appears that you are actually assuming what you are trying to prove. A simple fix will do though: "Fix some $k\geq 2$, and assume that $k^2>k+1$ is true. ..."

Is this an appropriate method of proving this statement to be true?

Not exactly. It seems like using induction here is a bit of overkill because you can easily prove the inequality by noting that $k^2>k+1\Longleftrightarrow k^2-k-1>0\Longleftrightarrow k(k-1)-1>0$, and this is clearly true when $k\geq 2$; to prove it is true, you could use some very basic calculus, but I think most people would look at $k(k-1)-1>0$ and would not worry about drawing up a proof that this is true for when $k\geq 2$ because it's clear the "$k(k-1)$ term" grows for larger $k$ and so on. In fact, you actually utilize this kind of reasoning when you go from $k^2+2k+1>(k+1)+1$ [the implicit reasoning is that $k^2+2k+1>(k+1)+1\Longleftrightarrow k^2+k>0$, and this is obviously true when $k\geq 2$, but someone may be a little annoying and require a proof though that would clearly be highly unreasonable]

Thus, I would not use induction here unless I were required to, which it sounds like you may have been. You may benefit from reading this post about how to write a clear induction proof. Just to show you how that might look in your case here, I have provided a more or less polished proof below. Hope it helps.

---

For $n\geq 2$, let $S(n)$ denote the statement $$ S(n) : n^2 > n+1. $$ Base case ($n=2$): $S(2)$ says that $2^2=4>3=2+1$, and this is true.

Inductive step $S(k)\to S(k+1)$: Fix some $k\geq 2$, and assume that $$ S(k) : \color{green}{k^2 > k+1} $$ holds. To be shown is that $$ S(k+1) : \color{blue}{(k+1)^2 > (k+1)+1} $$ follows. Beginning with the left-hand side of $S(k+1)$, \begin{align} \color{blue}{(k+1)^2} &= \color{green}{k^2}+2k+1\tag{expand}\\[0.5em] &> \color{green}{(k+1)}+2k+1\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &= 3k+1+1\tag{simplify}\\[0.5em] &> \color{blue}{(k+1)+1},\tag{$3k>k$ since $k\geq 2$} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

By mathematical induction, the statement $S(n)$ is true for all $n\geq 2$. $\blacksquare$

Answer 3

Without explicitly using induction, you can write this one-line proof: $$ n^2-n=n(n-1) \ge 2 \cdot 1 > 1 $$

Induction is implicit in $a \ge a', b \ge b' \implies ab \ge a'b'$.