Help with a proof

Printable View

February 20th 2011, 12:06 AM
rushton

Help with a proof

Ok I've just started a university maths course and the first thing we are learning is proofs. (I hope this is the right sub-forum (Bigsmile))
I get the concept and all but I am reading a book on the subject anyway and it has a proof early on that I don't quite get the reasoning of.
Its to prove 2^n > n^2 for n>or=5.

I get that we have to prove that 2^(n+1) > (n+1)^2

So we multiply 2^n > n^2 X2
2X 2^n = 2^(n+1) > 2X n^2 = 2n^2 = n^2 + n^2 = n^2 +nn

Now this is the part that I don't quite understand. It has;

Since n> or =5, we have n> or =3 (Why 3? In using 3 there is an inequality in the wrong direction?) so

nn> or = 3n = 2n+n > or = 2n+1 (I don't see how you can just assume that the n can turn into a 1 either)

I see that this gets the answer to the needed 2^(n+1) > n^2 + 2n + 1 = (n+1)^2
but can't justify why you can just use the things pointed out above to get the reasoning.

Personally I would have argued (this is by no means a correct statement so if I'm gravely wrong please say) That n^2 + n^2 is always going to be greater than n^2 + 2n + 1 for n> or =5 as n^2 is always going to be larger then 2n + 1 for numbers that high. I know thats not quite induction but to me it makes more sense the swapping out n for convenient numbers.

Thanks for the help!(Rock)
February 20th 2011, 12:30 AM
Sudharaka

Quote:

Originally Posted by rushton

Ok I've just started a university maths course and the first thing we are learning is proofs. (I hope this is the right sub-forum (Bigsmile))
I get the concept and all but I am reading a book on the subject anyway and it has a proof early on that I don't quite get the reasoning of.
Its to prove 2^n > n^2 for n>or=5.

I get that we have to prove that 2^(n+1) > (n+1)^2

So we multiply 2^n > n^2 X2
2X 2^n = 2^(n+1) > 2X n^2 = 2n^2 = n^2 + n^2 = n^2 +nn

Now this is the part that I don't quite understand. It has;

Since n> or =5, we have n> or =3 (Why 3? In using 3 there is an inequality in the wrong direction?) so

nn> or = 3n = 2n+n > or = 2n+1 (I don't see how you can just assume that the n can turn into a 1 either)

I see that this gets the answer to the needed 2^(n+1) > n^2 + 2n + 1 = (n+1)^2
but can't justify why you can just use the things pointed out above to get the reasoning.

Personally I would have argued (this is by no means a correct statement so if I'm gravely wrong please say) That n^2 + n^2 is always going to be greater than n^2 + 2n + 1 for n> or =5 as n^2 is always going to be larger then 2n + 1 for numbers that high. I know thats not quite induction but to me it makes more sense the swapping out n for convenient numbers.

Thanks for the help!(Rock)

Hi rushton,

Since it is given that, $n>5\Rightarrow{n>3}$

Since n is a positive integer, we can multiply both sides of the inequality by n,

$n^2>3n\Rightarrow{n^2>2n+n}$

$n>1\Rightarrow{n^2>2n+n>2n+1}$

We are using 3n particularly because we know that we have to make $(n+1)^2$ in the right hand side of the inequality.
February 20th 2011, 12:49 AM
rushton

So just because we know n> or =5 we can use n>3 and n>1 as n is larger then 1,2,3 or 4. Which, I'm assuming, this means in proofs we can change variables around to get answers we need as long as the change fits into the given criteria. (For an example if we had a proof xn>yn to do where n>3 we could not change an n in the right hand side to a 4 but we could change it to a 1,2 or a 3)?
February 20th 2011, 01:09 AM
Sudharaka

Quote:

Originally Posted by rushton

So just because we know n> or =5 we can use n>3 and n>1 as n is larger then 1,2,3 or 4.

Yes because, we know that, $n>5~and~5>4$ . Therefore, $n>4$ Hope you understood.
February 20th 2011, 01:14 AM
emakarov

Quote:

Originally Posted by rushton

Since n> or =5, we have n> or =3 (Why 3? In using 3 there is an inequality in the wrong direction?)

I agree with the reply above:

Quote:

We are using 3n particularly because we know that we have to make $(n+1)^2$ in the right hand side of the inequality.

But the short answer to "Why 3?" questions is, because it is true (namely, if n >= 5, then n >= 3). It is one thing to find that some step in a proof is incorrect and another to not understand the author's intention behind a step. The former obviously invalidates the whole proof; the latter happens all the time and is normal. Hopefully, when you reach the end of the proof, you will understand why 3 and not 2 or 4 is chosen. In fact, you write that you see "that this gets the answer to the needed 2^(n+1) > n^2 + 2n + 1 = (n+1)^2".

Similarly, if n >= 5, then n > 1, so 2n + n > 2n + 1. To be extremely formal, you start with a true inequality n > 1 (which follows from n >= 5) and add 2n to both sides.

Quote:

Personally I would have argued (this is by no means a correct statement so if I'm gravely wrong please say) That n^2 + n^2 is always going to be greater than n^2 + 2n + 1 for n> or =5 as n^2 is always going to be larger then 2n + 1 for numbers that high.

This is precisely how the proof proceeds, it just justifies n^2 > 2n + 1 in more detail.

Quote:

Originally Posted by Sudharaka

Since n is a positive integer, we can multiply both sides of the inequality by n,

$n^2>3nn^2>2n+n$

You probably mean $n^2>3n=2n+n$ .

Quote:

Originally Posted by Sudharaka

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

I would write, Since $n > 1$ and, as we have shown, $n^2>2n+n$ , we have $n^2 > 2n + 1$ . (The fact that $n>1$ does not imply that $n^2>2n+n$ .)
February 20th 2011, 01:19 AM
rushton

Thank you very much both of you!
I totally understand how it is done now and understand proofs and induction more in turn.
I'm doing this degree externally so I can see that this forum is going to a lot of help.
February 20th 2011, 03:04 AM
Sudharaka

Quote:

Originally Posted by emakarov

I agree with the reply above:But the short answer to "Why 3?" questions is, because it is true (namely, if n >= 5, then n >= 3). It is one thing to find that some step in a proof is incorrect and another to not understand the author's intention behind a step. The former obviously invalidates the whole proof; the latter happens all the time and is normal. Hopefully, when you reach the end of the proof, you will understand why 3 and not 2 or 4 is chosen. In fact, you write that you see "that this gets the answer to the needed 2^(n+1) > n^2 + 2n + 1 = (n+1)^2".

Similarly, if n >= 5, then n > 1, so 2n + n > 2n + 1. To be extremely formal, you start with a true inequality n > 1 (which follows from n >= 5) and add 2n to both sides.

This is precisely how the proof proceeds, it just justifies n^2 > 2n + 1 in more detail.

You probably mean $n^2>3n=2n+n$ .
I would write, Since $n > 1$ and, as we have shown, $n^2>2n+n$ , we have $n^2 > 2n + 1$ . (The fact that $n>1$ does not imply that $n^2>2n+n$ .)

Dear emakarov,

Thanks for pointing out those mistakes.(Hi) I think I need to improve my way of expressing ideas. Most of the time I myself is not satisfied when I read a reply I had already posted.