Results 1 to 3 of 3

Math Help - Proof by induction

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    66

    Proof by induction

    A group of people stand in line to purchase movie tickets. The first person in line is a woman and the last person in line is a man. Use proof by induction to show that somewhere in the line a woman is directly in front of a man.
    This seems so obvious... but I'm not sure how to prove it using induction. Could someone give me a hint?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jan 2008
    Posts
    175
    well prove the base case first.
    If there are only 2 people in line then the first will be a woman, and the 2nd/last will be a man.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2009
    Posts
    66
    Thanks for your tip on how to start it. I've been working on it more, and this is what I have... would this be sufficient?

    Let N represent the number of people in the line.

    Basis step: Let N=2. If there are only two people in the line, then clearly a woman is directly in front of a man. Our base case is confirmed and we can continue.

    Induction hypothesis: Suppose that in a line of k people, a woman is directly in front of a man.

    Next, we need to show that in a line of k+1 people, a woman is directly in front of a man.

    Look at the second to last person. If the second to last person is a woman, then clearly a woman is directly in front of a man, and we're done. On the other hand, if the second to last person is a man, then remove the last person and we have the exact same line as k, and therefore a woman is still directly in front of a man. Therefore, the statement is true for k + 1 people.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction (n^4 - 4n^2)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 18th 2011, 10:01 PM
  2. Proof by induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 3rd 2010, 04:04 PM
  3. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: October 15th 2009, 12:11 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum