/sci/ - Science & Math

I'm new.

Tower of hanoi, blah blah prove that it takes 2^n - 1 moves.
I understand all the steps of this proof, but its not quite evident to me why...

1. assuming the solution for n discs takes 2^n - 1 moves, and then
2. showing that the solution for n+1 discs takes 2^(n+1) - 1 moves

...along with the base case n=1, sufficiently proves this. I mean I kind of see it but how do we know we couldn't have assumed some other expression other than 2^n - 1 and then found a similar result for that?

Thank you