Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - help showing simple induction

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    help showing simple induction

    For each natural number n>0, we define the set B_n to be {2^i:i in and 0<=i<n}

    My inductive definition for B_n is
    n∈ℕ+B_n={2^0,2^1,2^2,…,2^(n-1)}={B_(n-1)}{2^(n-1)}


    My proof that for any natural number n>0 if t∈ℕ and 0<=t<2^n , then there is a subset A of B_n such that ∑[xA]x=t.







    [Base Case]:
    Prove P(1)
    Let n=1
    Then t∈ℕ s.t 0≤t<2^1
    So t{0,1}
    B_1 ∑[x]x = 0
    {2^0}B_1 ∑[x{2^0}]x = 1
    t∈ℕ s.t 0≤t<2^1 AB s.t ∑[xA]x = t

    [I.S]:
    Let n≥2
    Suppose P(n) [I.H]
    W.T.P P(n+1) i.e. t∈ℕ s.t 0≤t<2^(n+1) → subset A s.t AB_(n+1) ˄ ∑[xA]x = t

    t∈ℕ s.t 0≤t≤2^(n)-1 → subset A s.t AB_n ˄ ∑[xA]x = t [re-arranging inequality]
    For n
    C1:
    0≤t≤2^(n-1)-1 [since t∈ℕ, n≥2] (*) [re-arranging inequality]

    C2:
    2^(n-1)-1<t≤2^(n)-1 [since t∈ℕ, n≥2] (**) [re-arranging inequality]
    For n+1
    C1:
    0≤t≤2^(n-1+1)-1 [since t∈ℕ, n≥2] (***) [by I.H, since ***=*+**]

    C2:
    2^(n-1+1)-1<t≤2^(n+1)-1 [since t∈ℕ, n≥2] [by I.H]
    0≤t<2n+1 as wanted.






    Is this right and formal?
    Last edited by Sneaky; May 20th 2011 at 12:37 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Quote Originally Posted by Sneaky View Post
    My inductive definition for B_n is
    n∈ℕ+B_n={2^0,2^1,2^2,,2^(n-1)}={B_(n-1)}{2^(n-1)}
    An inductive definition needs a base case (B_1).

    For the proof, it's good to say that induction is on n (not on t).

    [Base Case]:
    Prove P(1)
    P was not defined above.
    Let n=1
    Fix (consider) t∈ℕ s.t 0≤t<2^1
    {2^0}B_1 ∑[x∈{2^0}]x = 1
    [I.S]:
    Let n≥2
    Suppose P(n) [I.H]
    W.T.P P(n+1) i.e. t∈ℕ s.t 0≤t<2^(n+1) → ∃ subset A s.t A⊆B_(n+1) ˄ ∑[x∈A]x = t
    What is W.T.P.: Want To Prove? Also, write "Case 1" instead of "C1."

    t∈ℕ s.t 0≤t≤2^(n)-1 → ∃ subset A s.t A⊆B_n ˄ ∑[x∈A]x = t
    This is the induction hypothesis.

    After that, it became too hard to understand. Are you claiming these facts or are you going to prove them? What does "for n" mean? Rearranging which inequality? A formal proof does not have to be difficult to read.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    My inductive definition for B_n is now:






    n∈ℕ^+ B_n={2^0,2^1,2^2,…,2^(n-1)}={B_(n-1)}{2^(n-1)}
    B_1={2^0}
    t∈ℕ s.t 0t2^(n)-1 subset A s.t AB_n ˄ [xA]x = t
    -------------------------------------------------------------



    Let P(n) be the predicate that n∈ℕ+, t∈ℕ s.t 0≤t<2^n → subset A s.t AB_n ˄ ∑[xA]x = t.


    This is P(n)

    btw when it says A of B_n, does that mean subset or proper subset?
    -------------------------------------------------------------



    w.t.p is Want.To.Prove
    --------------------------------------------------------------


    after this i am explaining this:


    Suppose P(n) for all n >= 2, then

    0≤t<2^n
    can become
    0≤t2^(n) - 1


    then


    there exists at least 1 t s.t 0t2^(n-1)-1 (*)

    there exists at least 1 t s.t 2^(n-1)-1t2^(n)-1 (**)



    since


    0 2^(n-1)-1 < 2^(n)-1
    since t∈ℕ and n>=2
    One of my problems here is that i can't prove (**)




    i think the key to this proof is to split the cases into 2.
    the * case for n+1 is basically the union of the * and ** for n (i don't know if you understand what i wrote)

    if n=1, t is 0 and 1, which i proved in the base case
    if n=2, by * there is at least 1 t in {0,1}, this is true since i proved it in base case
    by ** there is at least 1 t in {2,3}, (this is the part i can't prove)

    if i prove **, then it can be easier to show that for the other n's, * is proved by the (n-1)'s * and ** being proved.
    This is what i want to get at to solve this. Like before i dont know how to write this as well (assuming ** gets proved).




    And what do you mean by fix(consider) ?
    Last edited by Sneaky; May 20th 2011 at 04:31 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    I'll mark with red what needs to be removed.

    Let P(n) be the predicate that ∀n∈ℕ+, t∈ℕ s.t 0≤t<2^n → ∃ subset A s.t A⊂B_n ˄ ∑[x∈A]x = t.
    btw when it says A of B_n, does that mean subset or proper subset?
    I am not sure where it says "A of B_n." I believe it should be improper subset everywhere.

    Suppose P(n) for all n >= 2, then

    0≤t<2^n
    can become is equivalent to
    0≤t≤2^(n) - 1
    there exists at least 1 t s.t 0≤t≤2^(n-1)-1 (*)
    Of course: take t = 0.

    there exists at least 1 t s.t 2^(n-1)-1≤t≤2^(n)-1 (**)
    Take t = 2^(n-1)-1.

    What you probably want to say is that if 0 <= t < 2^n, then either 0 <= t < 2^(n-1), or 2^(n-1) <= t < 2^n.

    since


    0 ≤ 2^(n-1)-1 < 2^(n)-1
    since t∈ℕ and n>=2
    I am lost with two words "since" in a row. I don't understand where one sentence ends and another begins.

    Suppose P(n) is true and let 0 <= t < 2^(n+1). Then either 0 <= t < 2^n or 2^n <= t < 2^(n+1). In the first case, the induction hypothesis states that t is represented as a sum of some of 2^0, ..., 2^(n-1) (the last element of B_(n+1), i.e., 2^n, is not used). In the second case, 0 <= t - 2^n < 2^n, so t - 2^n is represented as a sum of 2^0, ..., 2^(n-1) by IH; then we add 2^n to that sum to get t.

    And what do you mean by fix(consider) ?
    A proof of a statement "For all x..." typically starts with "Fix (or consider) an arbitrary x..."

    In the future, please make an extra effort to write clearly: capitalize the first word in each sentence, use periods to terminate sentences, avoid unnecessary abbreviations, etc.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    Can you please explain in more detail about your two cases. I don't understand what you mean.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Do you understand that 0 <= t < 2^(n+1) implies 0 <= t < 2^n or 2^n <= t < 2^(n+1)? If yes, then which specific part you don't understand?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    OK I think I understand now, is this right and formal?

    modified:


    But one thing I am not sure about is, that you started proving P(n) but started with P(n+1), aren't we supposed to start from P(n) and get to P(n+1) ?
    Last edited by Sneaky; May 21st 2011 at 03:14 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Yes, I think this is correct. I only have some stylistic remarks.

    Every time you state P(n) (in the problem statement, in the definition of P(n) and after "W.T.P"), it starts with "t ∊ ℕ s.t ..." (by the way, if you have a period after s in "s.t", then you should also have one t, and similarly for W.T.P, which is not a universally accepted abbreviation). When a new variable (t in this case) is introduced, it should be bound by a universal or existential quantifier. In this case, I would say, "For all t ∊ℕ, if 0 <= t < 2^n, then ..." or "For all t ∊ℕ s.t. 0 <= t < 2^n, it is the case that ..." In fact, the claim to prove should start with "for all n > 0"; so far you only have it in the definition of B_n. It is not necessary to write "subset A" since you immediately write A ⊆ B_n.

    Remove the sentence "If 0 <= t < 2^(n+1), then..." from the second line of the proof. First, n-1 should be replaced with n in the conclusion and, second, its place is later, in the induction step.

    It's good that you use explicit universal quantifier with t at the end of the base case.

    Remove "since t ∊ℕ, n >= 2" from the induction step. It is enough to write n >= 2 once at the beginning if the induction step.

    In Case 2, t - 2^n is represented as a sum of numbers from B_n by the IH, and is it t, not t - 2^n, that equals 2^n plus that sum.

    I would remove the last line: it is not clear what "t is existent" means, and you were proving P(n+1), not P(n).

    Quote Originally Posted by Sneaky View Post
    But one thing I am not sure about is, that you started proving P(n) but started with P(n+1), aren't we supposed to start from P(n) and get to P(n+1) ?
    I am not exactly sure what you mean by "started proving P(n)." By "started with P(n+1)," do you mean that I started proving the induction step by considering an arbitrary t such that 0 <= t < 2^(n+1), which is the premise of P(n+1)? If P(n) were an equation, then yes, formally one should start with that equation and gradually rewrite it to get P(n+1). In this case, P(n+1) has the form of an implication, so we start proving it like any other implication, by assuming the premise. We are free to invoke P(n) at any point during the proof.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    I edited my work in my previous post, can you quickly look it over and see if anything is still wrong?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    The proof is OK, but you deleted the problem statement, i.e., the claim you are proving. In fact, I don't understand why you need an inductive definition of B_n. An inductive (or recursive) definition is usually needed when one does structural induction on that definition. You are doing induction on n, not on the definition of B_n. In any case, for n > 0 you either say

    B_n = {2^0, ..., 2^(n-1)}

    (no need to set apart B_1), or, if you want to avoid informal ...,

    B_1 = {1}, B_n = B_n ∪ {2^(n-1)}.

    Then you need to write the claim you are proving.

    When you define P(n), you don't need ∀n. What you are proving is ∀n P(n), so P(n) is ∀t, 0 <= t < 2^n -> ...
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    so i should change my inductive definition to
    ∀n∈ℕ+ Bn={2^0}, if n=1; {2^0,2^1,…,2^(n-1)}, if n>1

    (fragment of it) Proof:

    Let P(n) be the predicate that ∀t∈ℕ, 0≤t<2^n → ∃ subset A s.t. A⊆B_n ˄ ∑[x∈A]x = t.

    Claim: ∀n>0 P(n) holds.
    (should I put a claim statement? If so can I write it like this, since P(n) is defined?)
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Quote Originally Posted by Sneaky View Post
    so i should change my inductive definition to
    ∀n∈ℕ+ Bn={2^0}, if n=1; {2^0,2^1,,2^(n-1)}, if n>1
    No,
    Quote Originally Posted by emakarov
    you either say

    B_n = {2^0, ..., 2^(n-1)}

    (no need to set apart B_1), or, if you want to avoid informal ...,

    B_1 = {1}, B_n = B_n ∪ {2^(n-1)}.
    (fragment of it) Proof:

    Let P(n) be the predicate that ∀t∈ℕ, 0≤t<2^n → ∃ subset A s.t. A⊆B_n ˄ ∑[x∈A]x = t.

    Claim: ∀n>0 P(n) holds.
    (should I put a claim statement? If so can I write it like this, since P(n) is defined?)
    Usually they start by writing the original statement to prove ("For every n > 0 and 0 <= t < 2^n, ...") and define the induction statement P only inside the proof.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    If I write the claim, then wouldn't defining P(n) after seem redundant? Can't I formally say the claim in the beginning and define P(n) after without writing the whole claim again for P(n)? Is there a way to combine both?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    If I write the claim, then wouldn't defining P(n) after seem redundant?
    Yes. The way I look at it, the question is given to you from a textbook, or by your boss, etc.; it's outside of your control. What you control is located after the word "Proof": there you define concepts that you need. That said, this is a question of style, not mathematics.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    Can I write it like this:

    Claim: ∀n∈ℕ>0, ∀t∈ℕ, 0≤t<2^n → ∃ subset A s.t. A⊆B_n ˄ ∑[x∈A]x = t.

    Let P(n) be the predicate that ∀t, 0≤t<2^n → ∃ subset A s.t. A⊆B_n ˄ ∑[x∈A]x = t.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Showing equality via a simple calculation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 2nd 2011, 01:33 AM
  2. Help with simple induction
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 7th 2011, 03:53 PM
  3. Simple Question about showing convex:
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 7th 2009, 11:41 AM
  4. Complete/Simple Induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 25th 2009, 11:57 PM
  5. Simple induction help
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: September 29th 2008, 06:29 AM

Search Tags


/mathhelpforum @mathhelpforum