0

From the book "Concrete mathematics", I tried to solve the following warmup exercise:

Find the shortest sequence of moves that transfers a tower of n disks from the left peg A to the right peg B, if direct moves between A and B are disallowed. (Each move must be to or from the middle peg. As usual, a larger disk must never appear above a smaller one.)

By resolving this manually I came up with the following table:

n f (n)
0 0
1 2
2 8
3 26
4 80

And I came with this formula:

f(0) = 0

f(1) = 2

f(n) = 4f(n-1)-3f(n-2) for n >=2

Now, my problem comes when I try to perform the "Math Induction", according to the steps:

Stage 1 : Write down what the proposition asserts for the case n = k. This is what you are going to assume. It is often called the inductive hypothesis.

Stage 2 Write down what the proposition asserts for the case n = k +1. This is what you have to prove. Keep this clearly in mind as you go.

Stage 3 Prove the statement in Stage 2, using the assumption in Stage 1.

I do not have any idea of how to do this, I tried replacing n for n+1 but that does not provide any hint.

My only experience with Math Induction was the "Josephus problem" on the same book.

Note: I am not 100% sure my hypotesis is 100% correct; I found on the internet a different answer, but that's what math induction is for, right? So, I'd like to perform it on my formula, even if that proves am wrong.

Eduardo
  • 127

1 Answers1

1

To be able to use induction, you need to already know what the explicit function will be and you want to prove that that is the function that describes the problem using your recurrence relation. Induction doesn't help you finding the function.

Also I'm not quite sure if your recurrence relation is correct. I get $$f(n) = 2+3f(n-1)$$ since you move the first $n-1$ disks to the right peg, then place the last disk on the middle peg, then move the $n-1$ disks from the right peg to the left peg, then move the biggest disk from the middle peg to the right peg and than move the $n-1$ pegs to the right peg (onto the biggest disk).

You get the following values: $$\begin{align*}f(0) &= 0\\f(1)=3f(0)+2&=2\\f(2)=3f(1)+2&=2\cdot3+2\\f(3)=3f(2)+2&=2\cdot3^2+2\cdot3+2\\f(4)=3f(3)+2&=2\cdot3^3+2\cdot3^2+2\cdot3+2\end{align*}$$ So we suspect $f(n)=2\cdot(3^n+3^{n-1}+\dots+3+1) = 2\cdot\frac{3^{n+1}-1}{2} =3^{n+1}-1$. And now you can use induction to prove that that is indeed the function that describes the problem.

Edit: Your recurrence relation is correct, it's just harder to find the function $3^{n+1}-1$. You can use your relation as well to prove that $f(n) = 3^{n+1}-1$.

Vincent Batens
  • 1,762
  • This function fits the values you found. Your recurrence relation might be correct as well but it's more complicated than mine and probably a bit harder to solve. – Vincent Batens Jul 12 '23 at 19:50
  • This is the book answer, I prefer to reason and solve it by myself.

    What I want is to perform Math Induction on my own recurrence/hypothesis, even if this proves my answer is incorrect, that is the purpose of these warmup exercises.

     – Eduardo Jul 14 '23 at 15:37
  • You will need a hypothesis for an explicit function to use induction. Everything will be the same except it would be a bit harder to find that explicit function. – Vincent Batens Jul 16 '23 at 15:17
  • What are you talking about? My hypothesis is described in the question. (f(n) = 4f(n-1)-3f(n-2) for n >=2) – Eduardo Jul 17 '23 at 16:08
  • No that is your recursion, you normally have a reasoning why that recursion fits the problem. What you need is a hypothesis for the explicit formula. You will get that by plugging values in and calculating a bit, just like I did in my answer. Than you proof that the hypothesis for the explicit formula is true using your recursion. You can't apply induction with only a recursion. – Vincent Batens Jul 23 '23 at 17:35
  • If you look at my answer, you can see that I used the recursion to proof that the explicit formula, that I "guessed", is the correct formula. – Vincent Batens Jul 23 '23 at 17:36
  • 1
    I think I see what your problem here is. If you want to use induction, you need to be sure of your recursion. You cannot use your induction to prove your recursion. If you want to prove your recursion, you will have to do it another way and I don't see a way to prove that except for first proving the explicit formula and plugging that in. If I understand correctly, you guessed the recursion based on the values you plugged in. Like you can see in my answer, I also didn't proof the recursion using induction, I used a different reasoning for that. – Vincent Batens Jul 23 '23 at 17:50