# Disprove this number that exists in the integers.

$\exists n\in \mathbb{Z}, n^{2}<n$

I've started to prove the contradiction is true:

$\forall n\in \mathbb{Z}, n^{2}\geq n$

But not sure how to do this, unless I need to show what (n)(n) = (m), m is always greater than or equal to n? Not sure how I would write this in proof terms.

• Hint: Reduce to the case that $n$ is positive (easy enough) and then apply induction. May 25, 2016 at 7:04
• You can easily show that $n^2<n \iff n^2-n<0 \iff n(n-1)<0 \iff 0<n<1$, thus $\forall n\in \mathbb{Z}:\ n^2\ge n$. May 25, 2016 at 7:07

By induction, symmetrically:

• $0^2\ge 0$ is the base case,

• $n\ge0\land n^2\ge n\implies (n+1)^2=n^2+2n+1\ge n+2n+1\ge n+1$,

• $n\le0\land n^2\ge n\implies (n-1)^2=n^2-2n+1\ge n-2n+1\ge n-1$.

You have a statement saying something is true for all $n\in \mathbb Z$, so you know

• how you have to start: by saying "let $n\in\mathbb Z$ be some integer".
• how you have to end: by saying "therefore, $n^2\geq n$".

Now, you need a path from your start to your finish. I suggest you start by splitting the cases, since you know that either $n\leq 0$ or $n>0$. If you can prove:

1. If $n\leq 0$, then $n^2 \geq n$
2. If $n>0$, then $n^2\geq n$,

you are done. The first one is almost trivial to prove, and the second one is not much harder, since, if $n>0$, then $n^2 = n\cdot n = n + (n-1)\cdot n$.

It is obvious that the relationship does not hold for non-positive numbers. Regarding positive numbers:

For n=1 $1^{2}=1$

Induction assumption The relationship does not hold for $n\in\mathbb{Z}$, that is: $n\leq n^{2}$.

Proof

$$(n+1)^{2}\geq n^{2}+1^{2} \geq n+1^{2}$$

$$=n+1$$

The first inequality is the triangle inequality, the second one stems from our assumption.

Q.e.d.

• @5xum I meant that the statement regarding the existence of such a number is wrong.
– rsm
May 25, 2016 at 7:21

$n^2 < n$ iff $n^2 - n < 0$ iff $n(n-1) < 0$ iff one of $n$ or $n-1$ is positive and the other is negative. If $n$ is a large positive number, then both $n$ and $n-1$ are positive. If $n$ is a negative integer, then both factors are negative. If $n=1$ or $n=0$, then one of the factors is 0, so again we can't have one factor positive and the other negative.

• "large" is a vague term...
– 5xum
May 25, 2016 at 7:20
• I expected the poster to work out that detail. It would be $n \ge 2$ for that case. May 25, 2016 at 7:22