Results 1 to 5 of 5

Math Help - Rule Induction Question

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    95

    Rule Induction Question

    Here is the problem I'm trying to solve:

    The set S is defined to be the least subset of Natural Numbers such that:

    1. 1∈S
    2. if n∈S then 3n∈S
    3. if n∈S and n>2 then (n-2)∈S

    I must firstly show that S={m∈ℕ| ∃r,s ∈ ℕ0. m=3^r - 2s} and secondly show that this is the set of all odd numbers. By rule induction, I know I can show that the property m=3^r - 2s holds for all members of S but this does not prove the above definition for S since S might only contain a subset of m=3^r - 2s for integers r and s. Could someone please explain this? I hope I've made the problem clear.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    Indication:

    When you have to prove a set equality (A=B), you prove that A\subset B and B\subset A.

    S=\left \{ m \in \mathbb{N} |\exists r, s\in \mathbb{N}^{*}, m=3^{r}-2s \right \}
    First show that every m=3^{r}-2s is in S. (Hint - 3 \in S) Then show that every element from S can be written as [tex]3^{r}-2s, r, s \in \mathbb{N}^{*}.
    Last edited by veileen; April 15th 2011 at 03:19 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Each inductive definition of some set A has two sides. One shows how to approximate A from below, i.e., how to construct subsets of A by building more and more elements of A. Elements of A are built using the rules given in the inductive definition. The other side shows how to bound A from above, i.e., how to prove that A is a subset of other sets that satisfy the same building rules. This is done using induction, which says that A is the least set that satisfy these building rules.

    Let T = {m ∈ ℕ | ∃r,s ∈ ℕ0. m=3^r - 2s}. You've shown that S ⊆ T using structural induction (rule induction). Conversely, you can show T ⊆ S by showing how each element of T can be constructed using the building rules of S. Let m = 3^r - 2s ∈ T for some r, s. It is easy to see how m can be constructed using rules 13.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2008
    Posts
    95
    Thanks, I've manged to prove the first part now. What about showing that S is the set of odd numbers? Don't I need to show that every number of the form 2^k + 1 can be written in the form 2^m -3m? I'm not sure how to do this.

    Quote Originally Posted by emakarov View Post
    Each inductive definition of some set A has two sides. One shows how to approximate A from below, i.e., how to construct subsets of A by building more and more elements of A. Elements of A are built using the rules given in the inductive definition. The other side shows how to bound A from above, i.e., how to prove that A is a subset of other sets that satisfy the same building rules. This is done using induction, which says that A is the least set that satisfy these building rules.

    Let T = {m ∈ ℕ | ∃r,s ∈ ℕ0. m=3^r - 2s}. You've shown that S ⊆ T using structural induction (rule induction). Conversely, you can show T ⊆ S by showing how each element of T can be constructed using the building rules of S. Let m = 3^r - 2s ∈ T for some r, s. It is easy to see how m can be constructed using rules 13.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    You can prove by induction on n that there exist r, s such that 2n + 1 = 3^r - 2s. For the step, consider two cases: when s from the induction hypothesis equals 0 and when it is > 0. The second case is trivial.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] quick question on product rule and equality rule for logs
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: October 19th 2011, 08:29 PM
  2. Replies: 19
    Last Post: October 19th 2009, 06:10 PM
  3. Replies: 5
    Last Post: October 19th 2009, 02:04 PM
  4. Replies: 1
    Last Post: October 13th 2007, 02:19 AM
  5. Replies: 5
    Last Post: October 11th 2007, 06:22 AM

Search Tags


/mathhelpforum @mathhelpforum