Proof Watch

Chittesh14
Badges: 19
Rep:
?
#1
Report Thread starter 7 months ago
#1
There is a natural number n such that 2n = 2n.

Now, this is an existential statement and one in which it talks about 'a value of n' existing for which the predicate P(n) holds.
If I want to prove it true, I only need to find one value of n to show this e.g. n = 1 where 2n = 2^1 = 2 and 2n = 2(1) = 2.
In this case, I have proven the statement true.

But, if I want to prove the existential statement wrong, it becomes a proof of an universal statement.
i.e. There are no natural numbers such that 2n = 2n, or For all natural numbers n, 2n ≠ 2n.

Let's say the statement was false, of course it is not, but if it was, how would I prove it?

Would I split the natural numbers into two categories which would be the universe of natural numbers i.e. odd and even natural numbers and prove it separately for them showing it's proved false for all natural numbers?

E.g. test with an even natural number e.g. n = 2k.
So, 22k and 2(2k) and show they're not equal to each other? Something along those lines and the same thing for odd natural numbers?

Thank you
Last edited by Chittesh14; 7 months ago
0
reply
Gregorius
Badges: 14
Rep:
?
#2
Report 7 months ago
#2
(Original post by Chittesh14)
But, if I want to prove the existential statement wrong, it becomes a proof of an universal statement. i.e. There are no natural numbers such that 2n = 2n, or For all natural numbers n, 2n ≠ 2n.

Let's say the statement was false, of course it is not, but if it was, how would I prove it? Thank you
Plot graphs of y = 2n and y = 2^n on the same plot, and then start thinking!
1
reply
ftfy
Badges: 13
Rep:
?
#3
Report 7 months ago
#3
Analyse the roots of f(x) = x^n-nx.
Last edited by ftfy; 7 months ago
0
reply
artful_lounger
Badges: 20
Rep:
?
#4
Report 7 months ago
#4
(Original post by Gregorius)
Plot graphs of y = 2n and y = 2^n on the same plot, and then start thinking!
(Original post by ftfy)
f(x) = x^n-nx has no rational roots.
The question is restricted to the natural numbers :s

(Original post by Chittesh14)
~
I'm not really sure exactly what you're trying to ask honestly...you can't prove a false statement. If you mean in general where you have some statement you want to prove "universally" then you would use proof by induction.

For this particular question, then you would be trying to prove there exist no natural numbers such that 2n=2n (n being a natural number). You would start setting up your inductive argument taking n=1, which would immediately prove there does exist a natural number that satisfies the relation and then you would stop there because you've proved your statement false (n=2 is also a possible solution, incidentally). There's no point in continuing to try and prove something you've proved false. You only need one counterexample to nullify the statement.

I'm not really sure what splitting the natural numbers into odds and evens would achieve here; there are both odd and even cases (1 and 2) which satisfy the relation, so you can't even partially "prove" that using that route. On a different proof, you could do that and it might allow you to prove by induction some more limited form of a statement (i.e. that it's true/false for only odd or even numbers) or prove by contradiction somehow using the properties of even/odd numbers...?
Last edited by artful_lounger; 7 months ago
0
reply
ftfy
Badges: 13
Rep:
?
#5
Report 7 months ago
#5
(Original post by artful_lounger)
The question is restricted to the natural numbers :s
Huh?
0
reply
Gregorius
Badges: 14
Rep:
?
#6
Report 7 months ago
#6
(Original post by artful_lounger)
The question is restricted to the natural numbers :s
The last time I looked, the natural numbers embed as a subset of the real numbers; therefore if the statement is true for the reals, then it is true for the naturals. This is a very standard proof technique.

You might also notice that, although the OP's original stament isn't true, following the suggested techniques will help arrive at conditions whereby it is true!
1
reply
artful_lounger
Badges: 20
Rep:
?
#7
Report 7 months ago
#7
(Original post by Gregorius)
The last time I looked, the natural numbers embed as a subset of the real numbers; therefore if the statement is true for the reals, then it is true for the naturals. This is a very standard proof technique.

You might also notice that, although the OP's original stament isn't true, following the suggested techniques will help arrive at conditions whereby it is true!
I'm not really sure I understand what you're getting at; but perhaps I haven't quite grasped what the OP was trying to ask. My attempt to follow through what I think what you're saying under the spoiler(?)

edit: I'm not actually convinced I've shown anything actually...

double edit: it turns out the formatting does work, it just doesn't show in the preview. I'll now just tidy that up...

Spoiler:
Show








If we're trying to show where 2n=/=2n rather than just in general whether the original statement is true, then aside from the case where n=0 which is pretty simple to show directly, then presumably you would just look at where 2<n and try to prove inductively that 2n=2n for all natural (or real...) n (or rather, that it doesn't).

taking n=k for all 2<n => 2<k
=> 2k=2k
=> 2k-1=k (1) (factoring out 2 from both sides)

and then taking n=k+1
=> 2k+1=2(k+1)
=>2k=k+1 (multiplying out the brackets, then factoring 2 from both sides)
=>2k=2k-1+1 from (1)
=>2k-2k-1=1 (subtracting 2k-1 from both sides)
=>2k-1(2-1)=1 (I'm a little dubious about this step, factoring out the 2k-1; this is more due to my questionable basic algebra understanding than anything, but as it's the crux of this "proof" if it's false then I have no idea lol)
=>2k-1=1 (simplifying and multiplying out the brackets)
=>k-1=0 (as we require some 2m=1 => m=0, where m is some real valued expression)
=>k=1

but as we had 2<n => 2<k this is a contradiction and hence there are no values of n for which 2n=2n where 2<n

While this shows then the range of values for which it doesn't hold, that doesn't really...do much since the question was where it is valid, which can be shown pretty easily, and this is just a long winded way to prove something that seems a bit besides the point. I don't know, maybe this is what the OP was trying to get at originally?

I'm also a little dubious whether all that algebra holds in the natural numbers, although I guess since the outcome was in terms of natural numbers in a hand-wavy way it doesn't matter (although that has been sort of assumed along the way, and I can't think how I can frame that more rigorously). Also the algebra is probably wrong anyway :x







Last edited by artful_lounger; 7 months ago
0
reply
ftfy
Badges: 13
Rep:
?
#8
Report 7 months ago
#8
(Original post by artful_lounger)
I'm not really sure I understand what you're getting at; but perhaps I haven't quite grasped what the OP was trying to ask. My attempt to follow through what I think what you're saying under the spoiler(?)
Your objection did not make any sense whatsoever because you said the statement is restricted to natural numbers. Why do you think this would be a problem? Aren't natural numbers rational as well as real?
0
reply
Chittesh14
Badges: 19
Rep:
?
#9
Report Thread starter 6 months ago
#9
Sorry for the late reply everyone, TSR been weird recently didn't send me any notifications until today and I haven't checked if anyone has replied to my thread . Sorry everyone, thanks for the help.

(Original post by artful_lounger)
The question is restricted to the natural numbers :s

I'm not really sure exactly what you're trying to ask honestly...you can't prove a false statement. If you mean in general where you have some statement you want to prove "universally" then you would use proof by induction.

For this particular question, then you would be trying to prove there exist no natural numbers such that 2n=2n (n being a natural number). You would start setting up your inductive argument taking n=1, which would immediately prove there does exist a natural number that satisfies the relation and then you would stop there because you've proved your statement false (n=2 is also a possible solution, incidentally). There's no point in continuing to try and prove something you've proved false. You only need one counterexample to nullify the statement.

I'm not really sure what splitting the natural numbers into odds and evens would achieve here; there are both odd and even cases (1 and 2) which satisfy the relation, so you can't even partially "prove" that using that route. On a different proof, you could do that and it might allow you to prove by induction some more limited form of a statement (i.e. that it's true/false for only odd or even numbers) or prove by contradiction somehow using the properties of even/odd numbers...?
Sorry, I meant show that the statement is false. What I meant is that, if the equation was such that a natural number didn't exist, then would I show it by proof by induction? Like in this case, it is true - there exists a natural number n. For example, if the question was: Determine whether the statement 'there is a natural number n such that 3n = 2n.' is true or false. How would I do it? Would I draw the two graphs and show that the two graphs do not intersect. Or would I rearrange it to show, 3n - 2n = 0, and that it is not equal to 0 for every n \geq 0.

For the next part, I meant, let's say the question was: for all integers n, 2n is a even number’. Then I would consider separately the cases of even and odd numbers, which covers the full set of integers. So, I would say if the integer n was even i.e. n = 2k, where k is an integer. Then, 2n = 4k = 2(2k) which is an even number. Similarly, if the integer n was odd i.e. n = 2k + 1, where k is an integer. Then, 2n = 2(2k+1), which is an even number. So, it proves that for all integers n, 2n is an even number.

(Original post by ftfy)
Analyse the roots of f(x) = x^n-nx.
Let's say I wanted to prove it wrong, i.e. there doesn't exist a natural number such that 2n = 2n.
Do I show that no roots exist, because if no roots exist - then there doesn't exist a natural number 'n' that satisfies 2n = 2n. Of course, a root exists - but if it didn't, then I can use that right?

(Original post by Gregorius)
Plot graphs of y = 2n and y = 2^n on the same plot, and then start thinking!
Thank you, same question as above. ^ If they didn't intersect, how do I show no roots exist without sketching the graphs?
0
reply
Chittesh14
Badges: 19
Rep:
?
#10
Report Thread starter 6 months ago
#10
(Original post by artful_lounger)
I'm not really sure I understand what you're getting at; but perhaps I haven't quite grasped what the OP was trying to ask. My attempt to follow through what I think what you're saying under the spoiler(?)

edit: I'm not actually convinced I've shown anything actually...

double edit: it turns out the formatting does work, it just doesn't show in the preview. I'll now just tidy that up...

Spoiler:
Show









If we're trying to show where 2n=/=2n rather than just in general whether the original statement is true, then aside from the case where n=0 which is pretty simple to show directly, then presumably you would just look at where 2<n and try to prove inductively that 2n=2n for all natural (or real...) n (or rather, that it doesn't).

taking n=k for all 2<n => 2<k
=> 2k=2k
=> 2k-1=k (1) (factoring out 2 from both sides)

and then taking n=k+1
=> 2k+1=2(k+1)
=>2k=k+1 (multiplying out the brackets, then factoring 2 from both sides)
=>2k=2k-1+1 from (1)
=>2k-2k-1=1 (subtracting 2k-1 from both sides)
=>2k-1(2-1)=1 (I'm a little dubious about this step, factoring out the 2k-1; this is more due to my questionable basic algebra understanding than anything, but as it's the crux of this "proof" if it's false then I have no idea lol)
=>2k-1=1 (simplifying and multiplying out the brackets)
=>k-1=0 (as we require some 2m=1 => m=0, where m is some real valued expression)
=>k=1

but as we had 2<n => 2<k this is a contradiction and hence there are no values of n for which 2n=2n where 2<n

While this shows then the range of values for which it doesn't hold, that doesn't really...do much since the question was where it is valid, which can be shown pretty easily, and this is just a long winded way to prove something that seems a bit besides the point. I don't know, maybe this is what the OP was trying to get at originally?

I'm also a little dubious whether all that algebra holds in the natural numbers, although I guess since the outcome was in terms of natural numbers in a hand-wavy way it doesn't matter (although that has been sort of assumed along the way, and I can't think how I can frame that more rigorously). Also the algebra is probably wrong anyway :x








Yeah, this is exactly it lol. Thank you so much, sorry I chose a new statement: Show that the statement is false: There exists a natural number n, such that, 3n = 2n. I'm going to try proving it false by induction tomorrow, can you please then help me on that? Thank you
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • Imperial College London
    Undergraduate Open Day Undergraduate
    Tue, 25 Jun '19
  • University of Brighton
    Photography MA open afternoon Postgraduate
    Wed, 26 Jun '19
  • University of Plymouth
    General Open Day Undergraduate
    Wed, 26 Jun '19

Who do you think will be the next PM?

Boris Johnson (158)
74.53%
Jeremy Hunt (54)
25.47%

Watched Threads

View All