1
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.