Answer to Question #264580 in Discrete Mathematics for Abhijeet Kaur

Question

Rahul left his cycle in a parking lot that is filled with bikes and cycles, parked neatly

in several rows. When he returns, he notices someone push all the vehicles on the

left end of each row, causing them to fall. Rahul knows that if a bike falls, then the

vehicle to its immediate right will also fall, but if a cycle falls, then the next vehicle

will fall only if that is also a cycle. Rahul hasn’t spotted his cycle yet, but he deduces

by mathematical induction that it will fall.

“Let P(n) statement: ‘In every row, every cycle in nth position will fall.’ I

know that P(1) is true - all cycles in the first position were pushed. For the inductive

step, consider any row with a cycle in the nth position. By the inductive assumption,

this cycle will fall. Now consider the next vehicle, which is in the (n + 1) th position.

If it is a bike, I don’t have to prove anything; if it is a cycle, it will fall because it was

pushed by the cycle on its left. ” What is the

flaw in his argument?

Answer 1

Mathematical induction is for every natural number, without breaks.

In the given proof Rahul does not consider bike in (n+1)th position.

But if cycles in (n)th position is falling and there is a bike in (n+1)th position, then this bike is not falling. So, cycles after this bike are not falling also.