- #1
pyrosilver
- 39
- 0
Towers of hanoi induction-- slight bit i don't understand
I am trying to prove towers of hanoi. Now I am on the induction part and there is a part I don't get. I have the whole thing, but i don't understand a couple lines.
WTS: f(n+1) = 2n+1 - 1
By the Induction Hypothesis, f(n) = 2n-1.
Earlier, we showed f(n) = f(n-1) + 1 + f(n-1).
By the recursive definition,
f(n+1) = f(n) + 1 + f(n).
f(n+1) = 2f(n) + 1
f(n+1) = 2(2n-1) + 1
f(n+1) = 2(2n - 2) + 1
f(n+1) = 2n+1 - 1.
QED.
Ok I get the first line...get the second line...I get that you substitute f(n) in the third line... but I have no idea what the fourth and fifth lines are about! Please help me? I need to understand this by tomorrow :(
Homework Statement
I am trying to prove towers of hanoi. Now I am on the induction part and there is a part I don't get. I have the whole thing, but i don't understand a couple lines.
Homework Equations
The Attempt at a Solution
WTS: f(n+1) = 2n+1 - 1
By the Induction Hypothesis, f(n) = 2n-1.
Earlier, we showed f(n) = f(n-1) + 1 + f(n-1).
By the recursive definition,
f(n+1) = f(n) + 1 + f(n).
f(n+1) = 2f(n) + 1
f(n+1) = 2(2n-1) + 1
f(n+1) = 2(2n - 2) + 1
f(n+1) = 2n+1 - 1.
QED.
Ok I get the first line...get the second line...I get that you substitute f(n) in the third line... but I have no idea what the fourth and fifth lines are about! Please help me? I need to understand this by tomorrow :(