Results 1 to 5 of 5

Thread: 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
    5
    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 $\displaystyle A \subseteq B \implies A \cap \bar B = \emptyset$ and $\displaystyle A \cap \bar B = \emptyset \implies A \subseteq B$

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

    for the second, use the contrapositive. that is, show that $\displaystyle 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
    5
    Quote Originally Posted by BACONATOR View Post
    I 've got these 3 problems.
    Any help would be appreciated!
    Thanks!
    for problem (3)

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

    now, $\displaystyle 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 $\displaystyle n$.


    Let $\displaystyle P(n)$: "$\displaystyle 4n(n - 1)$ is divisible by $\displaystyle 8$" for all $\displaystyle 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
    5
    for (1): note that $\displaystyle x \in A \cap \bar B$ means $\displaystyle x \in A$ and $\displaystyle x \in \bar B$. clearly we cannot have $\displaystyle x \in \bar B$ if $\displaystyle x \in B$. so all you have to do, is show that if $\displaystyle x \in A$ (as i suggested you start with) then $\displaystyle x \in B$... oh, just let me do it.

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

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

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

    then what?




    for problem (3):

    Let $\displaystyle P(n)$ be defined as i said.

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

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

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

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

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

    for $\displaystyle P(n + 1)$, we have:

    $\displaystyle 4n(n + 1)$

    now show that we can write this as $\displaystyle 8m$ for some integer $\displaystyle m$, given that $\displaystyle 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
    5
    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 $\displaystyle A \cap \bar B \ne \emptyset$ and show that implies $\displaystyle A \not \subseteq B$.


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

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

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

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum