4
$\begingroup$

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$
1
  • $\begingroup$ Did someone tell you to use induction? $\endgroup$ – Stefan Smith Aug 30 '13 at 23:18
4
$\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$ This is exactly what I was looking for. Thank you! $\endgroup$ – Neurax Aug 31 '13 at 23:01
  • $\begingroup$ You are welcome! $\endgroup$ – user87543 Sep 1 '13 at 9:22
14
$\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$ Question prompted for a proof using mathematical induction. $\endgroup$ – Neurax Sep 3 '13 at 19:14
5
$\begingroup$

$n \ge 2$. Then

$n^2\ge 2n$. Then

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

$\endgroup$
4
$\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
  • 1
    $\begingroup$ What is the derivative of a function $f : \mathbb{N} \to \mathbb{Z}$? $\endgroup$ – Michael Albanese Aug 30 '13 at 13:44
  • 1
    $\begingroup$ you prove the claim for all real values. In particular, this holds for integers. $\endgroup$ – Igor Shinkar Aug 30 '13 at 13:47
  • $\begingroup$ @MichaelAlbanese : Nice Question ;) IgorShinkar : Great answer :) $\endgroup$ – user87543 Aug 30 '13 at 13:49
  • 2
    $\begingroup$ @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. $\endgroup$ – Git Gud Aug 30 '13 at 13:55
2
$\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$
1
$\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$
1
$\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$

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.