Mathematical Induction — 3 Fun Examples
Proof by induction is central to discrete mathematics and computer science. See if you can apply it to these nice problems…
If you need a refresher on mathematical induction, check out this article by Sundip Tailor. Otherwise, enjoy the fun problems below!
Problem 1 — A “Round Table” Job Interview
The final round of a job interview takes place around a round table, where n supporters and n opponents are seated in a random order.
Given the locations of all supporters and opponents, you may choose any starting position to complete one lap of the table. When passing a supporter you receive an upvote, but when passing an opponent you receive a downvote.
You succeed in the interview if you can complete the lap without having a negative vote tally at any stage. Prove that it is always possible for you to succeed.
Problem 2 — The Tower of Hanoi
Initially, n disks of different sizes are placed on the first of three pegs. The disks are arranged in size order, with larger disks below smaller disks.
Your challenge is to move the n disks one at a time from the first peg to the third peg, without ever…
