From Puzzles to Programming

Inferring the general from the knowledge of the particular.

Example: The sum of odd n numbers up to 2n-1 is equal n².

1 = 1

1+3 = 4

1+3+5 = 9

1+3+5+7= 4² = 16

Is this true for all n > 0?

The proof:

Let S1, S2, S3,…Sn be the sequence of statements.

Hypothesis of math induction:

1-    S1 = true

2-    For all k>0, if S_k is true it implies S_k+1 is true.

Going to the above example,

By hypothesis 1, S1 1=1 is true. By hypothesis 2, if S_k is true it implies S_k+1 is true. Now, S_k+1 = 1+3+5+…(2k-1)+(2(k+1)-1)

= 1+3+5+….(2k-1)+(2k+1) = k² + (2k + 1)

= k² + 2k + 1 = (k+1)².

Thus, S_k+1 is true.

In the game of tower of Hanoi, name the pegs A, B, C. Prove that the number of steps to move n discs from peg A to peg B is 2ⁿ – 1.

Answer

Using method of induction, let Sn = statement that n discs can be transferred in 2ⁿ – 1 steps.

S₁ = true. Move 1 disc from A to B. It takes 1 move = 2¹ – 1 = 1.

Assume S_k  is true and let A be original peg and B be new peg where k discs to be stacked.

If now k+1 discs are on A, transfer top k discs to B. This will take 2^k – 1 steps since S_k is true. Now, transfer the remaining disc k+1 or a_k+1 to peg C. Relabel the pegs now as follows: A becomes C, B becomes A, and C becomes B. Transfer k discs on new A to new B in 2^k – 1 steps. Therefore, total number of steps to transfer k+1 discs is 2^k – 1 + 1 + 2^k – 1 = 2^k+1 – 1 steps. Thus, S_k implies S_k+1. By method of induction, S_n is true for all n.