Proof by induction that $n^2 \ge n$ for all $n \in \mathbb{Z}$

Prove that the inequality $n^2\geq n$ holds for every integer.

With induction, I believe we would start with the base case, that is $n=0$

$n=0$

$0^2 \geq 0$, which is true.

Then would I start with $n=1$?

$n=1$

$1^2 \geq 1$, which is also true.

Then prove for all $n$.

Then prove for all $n+1$

How would I go about proving for $n$ and $n+1$?

• Do you really need induction? How about this: $n \ge n, n \ge 1 \implies n\cdot n \ge n \cdot 1$ ? – lhf Jun 7 '16 at 12:53

4 Answers

As in the other solution, we consider only positive integers, as it is clear that $n^2 \ge -n$.

Our base case is $n = 1$: evidently, $1 \ge 1$, so this is true.

Now, our inductive step: we assume it is true for $n$ and try to prove it true for $n+1$. This means that we know that $n^2 \ge n$ and are trying to show that $(n+1)^2 \ge n+1$. Note that this is equivalent to showing $n^2 + 2n + 1 \ge n+1 \Rightarrow 2n \ge 0$, since we know $n^2 \ge n$. Now, it is evident that this is true for positive integers $n$, so we are done.

We could also just consider the following for positive integers $n$: $$n^2 \ge n \Rightarrow n^2 - n \ge 0 \Rightarrow n(n-1) \ge 0$$ Noting that $n$ and $n-1$, if not $0$, are either both negative or positive, this expression is evidently true.

Consider the strictly positive integers only, as $n^2\geq-n$ is clearly true.

$n=1$ gives $1\geq1$ so that's the base case sorted. Now the inductive step: Assume that $n^2\geq n$. Now we look at $(n+1)^2=n^2+2n+1$. To complete the proof, you need to use the inductive hypothesis to show this is going to be $\geq n+1$.

To prove $$(n+1)^2 = n^2+2n+1 \geq n+1$$ $$n^2+n \geq 0$$

we know $$n^2 -n \geq 0 => n(n-1) \geq 0$$ => Either $n \leq 0$ or $n \geq 1$

if $$n \geq 1 => n^2 + n \geq 0$$ if $$n \leq 0 => n^2 + n \geq 0$$

Thus for any integer n, $n^2\geq n$

The only region it does not work are for $-1 < n < 1 \lnot (0)$ the region which is not an integer anyway.

Hence Proved

Your base case is fine. After this first step, there's the so called inductive step: by assuming that $n^2\geq n$ we have to show that $(n+1)^2\geq n+1$. Assume $n^2\geq n$ is true. Notice that $$n^2\geq n\implies n^2+1\geq n+1\implies (n+1)^2-2n\geq n+1$$ But this means that $$(n+1)^2\geq (n+1)^2-2n \geq n+1$$ Hence $(n+1)^2 \geq n+1$ as we wanted and the proof by induction is complete.