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$?
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.
