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