I am new to proofs and I am trying to learn mathematical induction. I started working out a sample problem, but I am not sure if I am on the right track. I was wondering if someone would be kind enough to comment on my work so far, and give me some hints as to how I should proceed.Many thanks in advance!
$S_n$ is the minimum number of moves it takes to solve towers of Hanoi where $n$ is a positive integer.
$$S_n = 2^n-1$$
Base Case:
$$\begin{align*}S_1 &= 2^1-1 \\&= 1 \end{align*}$$
Assume true for $k$:
$$S_k = 2^k-1$$
Hence,
$$\begin{align*}S_{k+1} &= (2^1-1) , (2^2-1) , (2^3-1) , \ldots , (2^k-1) , (2^{k+1}-1) \\&= (2^k-1) + 2^{k+1}-1\end{align*}$$ This is where I am stuck.
Best Answer
Let it be true for $k$
With a tower of $k+1$ disks, we first have to move the tower of $k$ disks from off the top of the $(k+1)^{\text{th}}$ disk onto another of the pegs. Then move the $(k+1)^{\text{th}}$ disk to the destination peg. And finally move the tower of $k$ disks from where it was put temporarily onto the top of the $(k+1)^{\text{th}}$ disk.
It is clear steps 1 and 3 above, each take $S_k$ moves, while step 2 takes one move.
We have
$$S_{k+1} = 2S_k+1 = 2(2^k-1) + 1 = 2^{k+1}-1$$
I don't see how to make it in another way...