Results 1 to 11 of 11

Math Help - Proove: the sum of two even numbers is even

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    90

    Proove: the sum of two even numbers is even

    E:= \{m: 2m, m \in \mathbb{N}\}

    U:= \{n: 2n+1, n \in \mathbb{N}\}

    Proof by contradiction:
    assume E_1+E_2=U

     \Rightarrow 2m_1+2m_2=2n+1

     \Rightarrow 2m_1+2m_2-1=2n

     \Rightarrow \nexists m \in \mathbb{N}: 2\mid(2m_1+2m_2-1)

    This contradicts the assumption, therefore E_1 + E_2 = E_3
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,306
    Thanks
    1282
    Isn't 2m+ 2n= 2(m+n) simpler?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello bmp05
    Quote Originally Posted by bmp05 View Post
    E:= \{m: 2m, m \in \mathbb{N}\}

    U:= \{n: 2n+1, n \in \mathbb{N}\}

    Proof by contradiction:
    assume E_1+E_2=U

     \Rightarrow 2m_1+2m_2=2n+1

     \Rightarrow 2m_1+2m_2-1=2n

     \Rightarrow \nexists m \in \mathbb{N}: 2\mid(2m_1+2m_2-1)

    This contradicts the assumption, therefore E_1 + E_2 = E_3
    Are you required to prove this by contradiction? The direct proof is very straightforward. We define an even number in the obvious way: n is even \iff \exists \,m \in \mathbb{N}, n = 2m.

    Then n_1 is even and n_2 is even \Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n_1 = 2m_1) \wedge (n_2 = 2m_2)

    \Rightarrow n_1 + n_2 = 2m_1 + 2m_2 = 2(m_1+m_2)

    \Rightarrow n_1 + n_2 is even


    If you're going to use a 'contradiction' method, I think you have to be a little more careful with your use of notation. The definition of your sets should be

    E = \{m:m=2n, n \in \mathbb{N}\}

    U = \{m:m=2n+1, n \in \mathbb{N}\}

    Then your hypothesis would be:

    Assume \exists\,m_1, m_2 \in E, m_1 + m_2 =m_3, m_3\in U

    Then \exists\, n_1, n_2,n_3\in \mathbb{N},m_1=2n_1, m_2 = 2n_2, m_3 = 2n_3+1

    \Rightarrow 2n_1+2n_2 = 2n_3+1

    \Rightarrow 2(n_1+n_2 -n_3)=1

    \Rightarrow 2 |1. Contradiction.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2009
    Posts
    90
    Thanks grandad! I was trying to follow your last example as well, btw. I read that you should be careful to not neglect the direct proof, because it is easier if possible, but then I have hardly ever seen it used.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2009
    Posts
    90
    And now to prove uneven.even = even

    n is even \iff \exists \,m \in \mathbb{N}, n = 2m.
    i is uneven \iff \exists \,m \in \mathbb{N}, i = 2m+1.

    Then n is even and i is uneven \Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n = 2m_1) \wedge (i = 2m_2+1)

    \Rightarrow n.i = 2m_1 . (2m_2+1) = 2m_1.2m_2+2m_1 = 2.m_1(m_2+1)

    \Rightarrow n.i is even

    Is this a trivial case, because you prove that 2 \mid P(n) but P(n) is 2m.n using the definition of an even number? (But that's the same for adding two even numbers as well...)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello bmp05
    Quote Originally Posted by bmp05 View Post
    And now to prove uneven.even = even

    n is even \iff \exists \,m \in \mathbb{N}, n = 2m.
    i is uneven \iff \exists \,m \in \mathbb{N}, i = 2m+1.

    Then n is even and i is uneven \Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n = 2m_1) \wedge (i = 2m_2+1)

    \Rightarrow n.i = 2m_1 . (2m_2+1) = 2m_1.2m_2+2m_1 = \color{red}2.m_1(m_2+1)

    \Rightarrow n.i is even

    Is this a trivial case, because you prove that 2 \mid P(n) but P(n) is 2m.n using the definition of an even number? (But that's the same for adding two even numbers as well...)
    Well done. You've got this pretty well complete, except for the bit I've marked in red, where you've just gone back to the original expression.

    I agree, it does look more or less trivial, but what you should have said is

    \Rightarrow n.i = 2m_1 . (2m_2+1) = 2 \color{red}\times (2m_1m_2+m_1)

    which is now in the format 2 \color{red}\times p\color{black}, p\in \mathbb{N}

    So that you can now say:

    \Rightarrow n.i is even

    using the \color{red}\Leftarrow part of the definition that n is even \color{red}\iff\color{black} \exists \,m \in \mathbb{N}, n = 2m

    Do you understand this subtle, but important, point?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2009
    Posts
    90
    Yes- thanks again, I realised that I needed to show something analogue to the definition of the even number, but I can see that it is much clearer to substitute of the natural numbers (m_1.m_2+m_1) as opposed to m_1(m_2+1). But the most important thing missing from the proof is this substitution of an equivalent natural number p.
    This reminds me of another probelm that I'm having proving the distributive laws in set theory- it is somehow simple, but hard to express in the right way!

    Proove \forall k \in \mathbb{Z}: 3 \mid k \Leftrightarrow 3 \mid k^2

     \equiv (3 \mid k \Rightarrow 3 \mid k^2) \wedge (3 \mid k^2 \Rightarrow 3 \mid k)

    Part1:  3 \mid k \Rightarrow 3 \mid k^2

    3 \mid k \Leftrightarrow k = 3.l,     k,l \in \mathbb{Z}

    \Rightarrow k^2 = (3.l)^2 = 3.(3.l^2)

    \exists p \in \mathbb{Z}: p = (3.l^2)

    \Rightarrow 3.(3.l^2) = 3.p

    \Rightarrow 3 \mid k \Rightarrow 3 \mid k^2

    Part2:  3 \mid k^2 \Rightarrow 3 \mid k

    3 \mid k^2 \Leftrightarrow k^2=3.l, k,l \in \mathbb{Z}

    3 \mid k \Leftrightarrow k = 3.m,     k,m \in \mathbb{Z}

    \exists m \in \mathbb{Z} : m=l

    \Rightarrow 3.l \Rightarrow 3.m

     3 \mid k^2 \Rightarrow 3 \mid k

    It follows that, (3 \mid k \Rightarrow 3 \mid k^2) \wedge (3 \mid k^2 \Rightarrow 3 \mid k)

    \forall k \in \mathbb{Z}: 3 \mid k \Leftrightarrow 3 \mid k^2

    Unfortunately, it's not very clear to read.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello bmp05
    Part1:  3 \mid k \Rightarrow 3 \mid k^2

    3 \mid k \Leftrightarrow k = 3.l,     k,l \in \mathbb{Z}

    \Rightarrow k^2 = (3.l)^2 = 3.(3.l^2)

    \exists p \in \mathbb{Z}: p = (3.l^2)

    \Rightarrow 3.(3.l^2) = 3.p

    \Rightarrow 3 \mid k \Rightarrow 3 \mid k^2
    Part 1 of your proof is fine.
    Part2:  3 \mid k^2 \Rightarrow 3 \mid k

    3 \mid k^2 \Leftrightarrow k^2=3.l, k,l \in \mathbb{Z}

    3 \mid k \Leftrightarrow k = 3.m,     k,m \in \mathbb{Z}

    \exists m \in \mathbb{Z} : m=l

    \Rightarrow 3.l \Rightarrow 3.m

     3 \mid k^2 \Rightarrow 3 \mid k
    This is not so good. One way to check to see if it makes sense is this: p|k^2 \Rightarrow p|k only works if p is a prime number, or a product of single powers of prime numbers. (For instance, 3|36 \Rightarrow 3|6 is OK, but 4|36 \Rightarrow 4|6 isn't.) But you haven't used the fact anywhere in your proof that 3 is a prime.

    You need to use the Fundamental Theorem of Arithmetic and say that if
    k=\prod p_i^{r_i}, where the p_i are primes, then k^2=\prod p_i^{r_i}\times\prod p_i^{r_i}=\prod p_i^{2r_i}. So 3|k^2 \Rightarrow 3 = p_i, for some i, and therefore 3 | k.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Mar 2009
    Posts
    90
    Hello Grandad,
    I'm not sure about the Fundamental Theorem of Arithmetic, I had a look at the wikipedia page and it looks interesting, but the course is moving very quickly, unfortunately and although I can't write very good proofs yet, we have already moved onto fields (help!)- anyway, I thought of a good idea for this problem, but I'm not sure how to proove it.
    The idea is that  \forall k \in \mathbb{Z},~k = 3m,~3m+1,~3m+2, ~m \in \mathbb{Z}
    This would mean that I can jump straight into the  3 | k^2 \Rightarrow 3 | k proof, because k^2 can only ever equal one of the 3 possibilities above. But the proof becomes something like:

     \forall k \in \mathbb{Z},~(k=3m)~\vee~(k=3m+1)~\vee~(k=3m+2), so I would like to say something like:

    Proof by contraditiction, suppose  k = 3m+1~~or~~k = 3m+2

     \Rightarrow k^2~= (3m+1)^2~~or~~(3m+2)^2

     \Rightarrow k^2~=(9m^2 + 6m + 1)~~or~~(9m^2 + 12m + 4)

     \Rightarrow 3 \mid (9m^2 + 6m + 1)~~or~~3 \mid (9m^2 + 12m + 4)

    [Errr... well, I- this seems to be true, but I don't know how to...?]

     \Rightarrow (9m^2 + 6m + 1) = 3 . n,~~\exists~n \in \mathbb{Z}

     \Rightarrow 3m^2 + 2m + \frac{1}{3} = n

    [... do the same for the other or]

    This is a contradiction, therefore  3 \mid k^2 \Leftrightarrow 3 \mid k

    Well, this is a terrible proof, but on the good side, if done correctly this would actually be an "if and only if" proof! (?)
    Last edited by Plato; March 31st 2009 at 12:37 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello bmp05

    Well done. I think this is pretty well OK. I should just change the last part a bit (the part where you weren't so sure) so that instead of:
    Quote Originally Posted by bmp05 View Post
    \Rightarrow (9m^2 + 6m + 1) = 3 . n,~~\exists~n \in \mathbb{Z}

     \Rightarrow 3m^2 + 2m + \frac{1}{3} = n

    This is a contradiction, therefore  3 \mid k^2 \Leftrightarrow 3 \mid k
    I think I'd factorise the right-hand sides, and say:

     3 \mid (9m^2 + 6m + 1)~~or~~3 \mid (9m^2 + 12m + 4)

    \Rightarrow 3 \mid 3(3m^2 + 2m) + 1~~or~~3\mid 3(3m^2 + 4m + 1) + 1

    Contradiction, since 3(3m^2 + 2m) + 1 and  3(3m^2 + 4m + 1) + 1 both leave remainder 1 when divided by 3.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Mathematics, or how to complicate simple things
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proove that...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 20th 2011, 11:15 PM
  2. Proove an isomorphism
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 19th 2010, 02:32 AM
  3. How can I proove this?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 22nd 2010, 05:36 AM
  4. How do I proove this
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: June 8th 2010, 05:47 PM
  5. Proove
    Posted in the Calculus Forum
    Replies: 5
    Last Post: May 7th 2009, 10:59 PM

Search Tags


/mathhelpforum @mathhelpforum