Torres de Hanói: O número mínimo de movimentações é $2^n$-1

Continuando a série de posts sobre torres de Hanói e indução, vamos provar que o número mínimo de movimentações necessárias para resolver o problema é $2^n - 1$.

A prova é por indução em n:

• Caso Base: Para n = 0, temos $2^0-1 = 0$.
• Hipótese de Indução: Vamos supor que para mover n-1 discos entre quaisquer 2 pinos sejam necessárias $2^{n-1}-1$ movimentações.
• Caso Geral: Para compor o caso geral teremos que considerar o custo para mover n-1 discos para um pino auxiliar ($2^{n-1}-1$ movimentações), o custo para mover 1 disco para o pino final (1 movimentação) e o custo para mover os n-1 discos do pino auxiliar para o pino final ($2^{n-1}-1$ movimentações), ou seja

                                                      Nº de movimentações =  $\underbrace{(2^{n-1}-1) + (2^{n-1}-1)}_\text{Hipótese de Indução} + 1$
                                                                                                     
                                                                                    = $2(2^{n-1}-1) + 1$

                                                                                    = $(2^n -2) + 1$

                                                                                    = $2^n -1$     C.Q.D.