Let us formulate a conjecture and prove it by the principle of mathematical induction.
There are three poles vertically studded on a board.
The activity starts with discs of different sizes each smaller than the one on which it rests on one rod. We have to shift the entire stack of discs from one rod to another with the least number of moves adhering to the following rules.
- Only one disc may be moved at a time.
- Each move consists of taking the upper most disc from one of the stacks and placing it on the top of another stack.
- Larger disc cannot be placed on the top of a smaller disc.
Now conduct this activity using 1, 2, 3,........ discs. What do you observe? Is your result tallies with this.
Can you formulate a conjecture for the minimum number of moves it takes to shift n discs from one pole to another.
On generalising, you will observe that -
I) To prove:
P(n) = 2n – 1 is the minimum number of moves it requires to move n discs from one pole to the other.
Now, prove this conjecture using the principle of mathematical induction.
II) To prove:
P(k+1) = 2k+1 – 1 is the minimum number of moves to shift (k + 1) poles from one rod to the other.
