Results 1 to 5 of 5

Math Help - Proofs and Mathematical Induction

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    13

    Proofs and Mathematical Induction

    I 've got these 3 problems.
    Any help would be appreciated!
    Thanks!
    Attached Thumbnails Attached Thumbnails Proofs and Mathematical Induction-proofmath.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by BACONATOR View Post
    I 've got these 3 problems.
    Any help would be appreciated!
    Thanks!
    for problem (1)

    we need to go both ways. that is, show that A \subseteq B \implies A \cap \bar B = \emptyset and A \cap \bar B = \emptyset \implies A \subseteq B

    for the first, let x \in A. show that this means A \cap \bar B = \emptyset

    for the second, use the contrapositive. that is, show that A \not \subseteq B \implies A \cap \bar B \ne \emptyset

    can you continue?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by BACONATOR View Post
    I 've got these 3 problems.
    Any help would be appreciated!
    Thanks!
    for problem (3)

    Let x be a positive, odd integer. then x = 2n - 1 for some integer n \ge 1

    now, x^2 - 1 = (x + 1)(x - 1) = (2n - 1 + 1)(2n - 1- 1) = 2n(2n - 2) = 4n(n - 1). thus, you need to prove the following by induction on n.


    Let P(n): " 4n(n - 1) is divisible by 8" for all n \in \mathbb{N}, n \ge 1

    can you continue?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    for (1): note that x \in A \cap \bar B means x \in A and x \in \bar B. clearly we cannot have x \in \bar B if x \in B. so all you have to do, is show that if x \in A (as i suggested you start with) then x \in B... oh, just let me do it.

    for the first implication, assume A \subseteq B. Then x \in A \implies x \in B. Clearly if x \in B, then x \not \in \bar B. thus, we have that x \in A and x \not \in \bar B. It means therefore, that x is not in their intersection. so, A \cap \bar B = \emptyset.

    for the second implication, you need to show that A \not \subseteq B \implies A \cap \bar B \ne \emptyset.

    now, if A \not \subseteq B, then there exists an x \in A such that x \not \in B.

    then what?




    for problem (3):

    Let P(n) be defined as i said.

    by induction, we need to prove P(1) is true, then show that if P(n) is true, then P(n + 1) will be true.

    Clearly P(1) is true. since when n = 1, 4n(n - 1) = 0. and, of course, 0 is divisible by 8.

    Assume P(n) is true for some n. we show P(n + 1) is true.

    Since P(n) is true, we can write 4n(n - 1) = 8k for some integer k.

    so, we need to show we can write P(n + 1) in this fashion.

    for P(n + 1), we have:

    4n(n + 1)

    now show that we can write this as 8m for some integer m, given that 4n(n - 1) = 8k
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    on second thought, i don't like my proof for the first implication in problem (1). there seems to be a problem with it.

    instead, do it by the contrapositive. assume A \cap \bar B \ne \emptyset and show that implies A \not \subseteq B.


    in other words, i want you to prove the equivalent statement that:

    A \not \subseteq B \Longleftrightarrow A \cap \bar B \ne \emptyset.

    you need to be clear on what it means for A \not \subseteq B and A \cap \bar B \ne \emptyset
    Last edited by Jhevon; March 18th 2008 at 11:24 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 7th 2010, 06:12 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Mathematical Induction Proofs
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: April 6th 2008, 06:27 AM
  4. Mathematical proofs
    Posted in the Discrete Math Forum
    Replies: 27
    Last Post: April 8th 2007, 11:36 AM
  5. Proofs by Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: March 3rd 2007, 11:29 PM

Search Tags


/mathhelpforum @mathhelpforum