3
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ What do you think those commas mean? $\endgroup$
    – MJD
    Feb 13, 2013 at 14:21
  • $\begingroup$ Since it works for one case, it will work for any case up to k, if it works for k, it will work for k+1 (which is what needs to proved). Commas mean each 'case' is independent and the function is not a summation as would be implied by plus signs. $\endgroup$
    – AnchovyLegend
    Feb 13, 2013 at 14:23
  • 1
    $\begingroup$ Before you changed the plus signs to commas, you had a sensible but incorrect claim. Now your question doesn't even make sense, and your explanation above doesn't help. "It will work" is too vague for me to understand. If I were you I would stop worrying so much about the notation and focus on trying to make a simple and clearly-stated claim. $\endgroup$
    – MJD
    Feb 13, 2013 at 14:25
  • $\begingroup$ Thanks for the reply. I am trying to make a claim, this is the part I am having trouble with and I am trying to learn how to do correctly. Unfortunately, saying the question does not make sense and to make a 'simple and clearly stated claim', does not help me at all to better understand how I should write this proof :/ $\endgroup$
    – AnchovyLegend
    Feb 13, 2013 at 14:34
  • 2
    $\begingroup$ You have $S_{k+1}=\text{this},\text{that},\text{something else}$. This says that $S_{k+1}$ is equal to a whole bunch of things. That does not make sense. It might be equal to one of them, but it can't be equal to all of them, since they are all different. So it is not sensible to state that it is equal to all of them. You know this, and that's why you didn't explain it that way in your comment above; you waved your hands and said "it will work" which means nothing at all. $S_{k+1}$ can be computed from the values of $S_i$ for $i<k+1$. You should figure out how, and then say it. $\endgroup$
    – MJD
    Feb 13, 2013 at 14:37

2 Answers 2

Reset to default
7
$\begingroup$

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...

$\endgroup$
0
$\begingroup$

What you want to say is assume $S_k=2^k-1$. To solve the problem with $k+1$ disks, we must do the $k$ disk solution to move the top $k$ disks to one peg, then move disk $k+1$ to the other peg with one move, then do the $k$ disk solution to move the top $k$ disks on top of disk $k+1$. So $S_{k+1}=(2^k-1)+1+(2^k-1)=2^{k+1}-1$

$\endgroup$
1
  • 2
    $\begingroup$ Although this argument is correct, the question and the comments on it lead me to think the OP will need some additional explanation of why we must first move the top $k$ disks, etc., --- something along the lines of "Since all the disks must go to a different peg, we must eventually move the bottom disk. At that moment, none of the smaller disks can be on the peg from which we're moving the biggest disk, nor on the peg to which we're moving it (since we can't put it on top of a smaller disk). So what we did before that moment solved the $k$-disk problem...." $\endgroup$
    – Andreas Blass
    Feb 13, 2013 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.