Results 1 to 2 of 2

Math Help - Need help with proofs by induction

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    United States
    Posts
    1

    Question Need help with proofs by induction

    I am really stuck with a few problems and would really appreciate any assistance possible. The problems I am having trouble with are:

    1. Prove: For every integer n greater than or equal to 1, 1 + (1/2) + (1/4) + ... + (1/(2^(n-1))) = (2^(n) - 1) / (2^(n-1))

    2. Prove: For every integer n greater than or equal to 5, 2^n > 2n +1

    3. Prove: For every integer n greater than or equal to 0, 5^n - 3^n is an even integer

    4. Prove: For every line of people with a woman at the front and a man at the rear, there is always an instance in which a woman immediately precedes a man.

    Again, any help that anyone could provide on how to answer these problems would be incredibly helpful.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697

    Re: Need help with proofs by induction

    let's look at number 4:

    suppose we have a line of just two people: a woman at the front, and a man at the rear. then the woman immediately precedes the man (there's no one else in the line!).

    now, suppose that we know that if the theorem was true for a line of n people, it was ALSO true for a line of n+1 people.

    then true for a line of 2 people, would imply true for a line of 3 people, and true for a line of 3 people would imply true for a line of 4 people, and true for a line of 4 people....can you see where this is going?

    so, let's assume this is true for a line of n people (with a woman in the front, and a man in the back). the only n we're sure this is true for at the moment is n = 2, but it might be true for some other n.

    now suppose we have a line of n+1 people with a woman in the front, and a man in the back. so our line might look like:

    W......MM (the last two people are men)
    W......WM (the next to last person is a woman, and the last person is a man).

    in the first case, then the first n people form a line with a woman in front, and a man in the back, and we are assuming that for this n (whatever it may be) we have some woman immediately in front of a man. well she's STILL immediately in front of that man if we just add one more man to the line.

    in the second case, the next-to-last person in the line is a woman immediately in front of a man, so in this case we have a woman in front, a man in back, and some woman in front of a man.

    so in ALL cases, whenever we have a line of n people with a woman in front and a man in back with a woman immediately in front of a man, a line of n+1 people with a woman in front and a man in back ALSO has some woman immediately in front of a man.

    that is: the theorem true for n implies it is also true for n+1.

    but we know it is true for n = 2, and thus true for n = 3, and then true for n = 4, and then true for n = 5...in short: true for any positive integer greater than or equal to 2.

    let's look at how we go from n= 2 to n = 3 in greater detail:

    here are the possible lines of length 2 that start with W and end with M:

    WM

    now, let's look at the possible lines of length 3 that start with W and end with M:

    WMM <---already covered in the n = 2 case
    WWM <--not covered by the n = 2 case, but true because it ends in WM

    now let's look at lines of length 4:

    WWMM <---covered in the case n = 3
    WMMM <---covered in the case n = 3
    WMWM <---not covered in the case n = 3, but ends in WM
    WWWM <---not covered in the case n = 3, but ends in WM

    rather than do an "infinite number" of proofs where we reduce the n+1 case to ether:

    1) ends in WM
    2) ends in MM (so that the n case applies)

    we do "all of these proofs at once" (which is a LOT more efficient).

    ***********

    let's look at how we can adapt this method to prove #2.

    first we need to establish that 25 > 2(5) + 1. since 32 > 11, this is indeed true.

    now suppose that 2n > 2n + 1, for some (unspecified) n ≥ 5.

    note that 2n+1 = 2(2n) > 2(2n + 1) (by our assumption, above, that 2n > 2n + 1)

    and 2(2n + 1) = 4n + 2. is this greater than 2(n+1) + 1 = 2n + 3?

    well, n ≥ 5, so 2n ≥ 10 > 1.

    hence 4n = 2n + 2n > 2n + 1, so 4n + 2 > 2n + 1 + 2 = 2n + 3.

    thus 2n+1 > 2(2n + 1) > 2n + 3 = 2(n+1) + 1.

    that is, if 2n > 2n + 1, then 2n+1 > 2(n+1) + 1, as well.

    so true for n = 5, implies true for n = 6, implies true for n = 7, implies true for n = 8,......and so on: so true for ANY n ≥ 5.

    (i don't know why you're being asked to prove this for n ≥ 5, it's clearly true for n ≥ 3).

    **********

    the idea is: to use the assumption of truth for n, to derive the (conditional) truth for n+1. if we can also find "a starting place" (some minimal n for which we know its true), then "the domino effect" takes place:

    the proof for our "starting n" then proves true for n+1, and then n+1 proves the truth for n+2, and then n+2 proves the truth for n+3, and so on, for...well, forever.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction Proofs
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 6th 2012, 04:03 PM
  2. Induction proofs
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 08:32 PM
  3. proofs by induction
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 28th 2009, 05:29 AM
  4. Induction Proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 5th 2009, 07:11 AM
  5. proofs by induction
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 25th 2007, 04:14 AM

Search Tags


/mathhelpforum @mathhelpforum