Prove $n^2 > (n+1)$ for all integers $n \geq 2$
Olivia Zamora 
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.
Thanks for the advice
$\endgroup$ 27 Answers
$\begingroup$Do you really need induction?
$$0 < (n-1)^2 = n^2 - 2n + 1 \implies n^2 > 2n - 1 = n + (n-1) \ge n + 1$$
$\endgroup$ 1 $\begingroup$$n \ge 2$. Then
$n^2\ge 2n$. Then
$n^2 \ge 2n \ge n+2 >n+ 1$
$\endgroup$ $\begingroup$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.
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ 4 $\begingroup$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?
$\endgroup$ $\begingroup$Your second thought is right.
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$.
$\endgroup$ $\begingroup$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$.
$\endgroup$
