# Prove $n^2 > (n+1)$ for all integers $n \geq 2$

I understand that I need to use induction for this, that's not a problem. I get stuck after I try to invoke the inductive hypothesis.

$P_n: n^2 > n+1$... and we want to prove $P_{n+1}: (n+1)^2 > (n+1)+1$ holds.

Base: $P_2: 4 > 3$

Suppose $P_n$ holds, such that $n^2 > n+1$.

Now, in most of the induction proofs I've done have some manipulation of the original formula to get the new step into form. I don't necessarily see where to go with this.

My original thought was, if $P_{n+1}$ is different from $P_n$ by one unit, then I'd add a unit to the other side of the formula, and get it into form. This turns out to be difficult.

Second thought was to start by looking at $(n+1)^2 = n^2+2n+1$ and since there's an $n^2$ term, I could use the "inductive hypothesis", where I isolate the squared term, and check to see if the RHS of the inequality is less than the RHS in the inductive step.......... This doesn't seem right either.

-
Did someone tell you to use induction? – Stefan Smith Aug 30 '13 at 23:18

I guess $$n^2>n+1\Rightarrow n^2+2n>n+1\Rightarrow n^2+2n+1>(n+1)+1\Rightarrow (n+1)^2>(n+1)+1$$ This is what you are looking for.

-
This is exactly what I was looking for. Thank you! – Neurax Aug 31 '13 at 23:01
You are welcome! – Praphulla Koushik Sep 1 '13 at 9:22

Do you really need induction?

$$0 < (n-1)^2 = n^2 - 2n + 1 \implies n^2 > 2n - 1 = n + (n-1) > n + 1$$

-
Question prompted for a proof using mathematical induction. – Neurax Sep 3 '13 at 19:14

$n \ge 2$. Then

$n^2\ge 2n$. Then

$n^2 \ge 2n \ge n+2 >n+ 1$

-

You can prove it for all real values $n \geq 2$. You need to prove that $f(n) = n^2-n-1>0$ for all $n \geq 2$. For $n=2$ this is clearly true. the derivative of $f$ is $f'(n) = 2n-1 > 0$, and thus $f$ is a monotone increasing function, and so is positive for all $n\geq 2$.

Here is also a proof by induction.

Base case $n=2$: Clear.

Suppose the claim is true for $n$. That is $n^2 \geq n-1$. Let's prove it for $n+1$. We have $(n+1)^2 = n^2 + 2n + 1 \geq (n-1) + 2n + 1 = 3n > n+1$, where the inequality is by induction hypothesis.

-
What is the derivative of a function $f : \mathbb{N} \to \mathbb{Z}$? – Michael Albanese Aug 30 '13 at 13:44
you prove the claim for all real values. In particular, this holds for integers. – Igor Shinkar Aug 30 '13 at 13:47
@MichaelAlbanese : Nice Question ;) IgorShinkar : Great answer :) – Praphulla Koushik Aug 30 '13 at 13:49
@IgorShinkar Obviously Michael knew what you meant. He's implying that you should make clear what is going on as it might not be so obvious to the OP. The OP might even accept the concept of derivative in $\Bbb N$ without thinking about it. – Git Gud Aug 30 '13 at 13:55

I think youre overthinking it. Firstly, the base case is obvious as 4>3.

Next, assume that $k^2 \ge k+1$ for some k>2. Then, we simply have, $(k+1)^2= k^2+ 2k +1 > k^2 +1 \ge (k+1)+1$.

Therefore the inducyion hypothesis is proved. And we are done. Do you see it?

-

Assume $n^2 > n + 1$. As $(n + 1)^2 = n^2 + 2n + 1$, apply the inductive hypothesis to show $(n + 1)^2$ is greater than something which is indeed greater than $(n + 1) + 1$.
You can do better than that. $$n^2 > n + 1\\ ⇔ n^2 - n - 1 > 0\\ ⇔ (n-½)^2 - \tfrac54 > 0\\ ⇔ |n-½| > ½\sqrt{5}$$
So the inequality holds for all $$n < ½ - ½\sqrt{5} \text{ and } n > ½ + ½\sqrt{5}$$ If your interested in integer numbers, you easily see that $$2 < \sqrt{5} < 2.5\\-1 < -\tfrac34 < \tfrac12 - \tfrac12\sqrt{5} < -\tfrac12 < 0\\1 < \tfrac32 < \tfrac12+\tfrac12\sqrt{5}<\tfrac74<2$$ So it holds for all integers except $0$ and $1$.