Answer:
Step-by-step explanation:
We will prove by mathematical induction that, for every natural n,
We will prove our base case (when n=1) to be true:
Base case:
As stated in the qustion,
Inductive hypothesis:
Given a natural n,
Now, we will assume the inductive hypothesis and then use this assumption, involving n, to prove the statement for n + 1.
Inductive step:
Let´s analyze the problem with n+1 stones. In order to move the n+1 stones from A to C we have to:
- Move the first n stones from A to C (
moves).
- Move the biggest stone from A to B (1 move).
- Move the first n stones from C to A (
- Move the biggest stone from B to C (1 move).
- Move the first n stones from A to C (
Then,
.
Therefore, using the inductive hypothesis,
With this we have proved our statement to be true for n+1.
In conlusion, for every natural n,