2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Hint: Reduce to the case that $n$ is positive (easy enough) and then apply induction. $\endgroup$ Commented May 25, 2016 at 7:04
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Galc127
    Commented May 25, 2016 at 7:07

4 Answers 4

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .