Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Did someone tell you to use induction? –  Stefan Smith Aug 30 '13 at 23:18

7 Answers 7

up vote 4 down vote accepted

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.

share|improve this answer
    
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$$

share|improve this answer
    
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$

share|improve this answer

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.

share|improve this answer
1  
What is the derivative of a function $f : \mathbb{N} \to \mathbb{Z}$? –  Michael Albanese Aug 30 '13 at 13:44
1  
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
2  
@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

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

share|improve this answer

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

share|improve this answer

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.