- #1

- 39

- 0

**Towers of hanoi induction-- slight bit i don't understand**

## 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) = 2

^{n+1}- 1

By the Induction Hypothesis, f(n) = 2

^{n-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(2

^{n-1}) + 1

f(n+1) = 2(2

^{n}- 2) + 1

f(n+1) = 2

^{n+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 :(