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 )
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!
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)?
I agree with the reply above:Originally Posted by rushtonBut 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".We are using 3n particularly because we know that we have to make in the right hand side of the inequality.
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.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.
You probably mean .Originally Posted by Sudharaka
I would write, Since and, as we have shown, , we have . (The fact that does not imply that .)Originally Posted by Sudharaka