Como se obtém recursivamente a sequência de movimentos da Torre de Hanói para n discos?

S_n = S_{n-1} X S_{n-1}, onde X é o disco de maior tamanho, e o comprimento é \(2^n-1\).

Explicação:
Usa-se a recorrência, primeiro executa-se a sequência para os n-1 discos menores, depois move-se o maior disco, por fim repete-se a mesma sequência dos n-1 discos.

Exemplo:
Sea rótulos L, M, N, O, P para discos do menor ao maior.
• S1 = L
• S2 = S1 M S1 = LML
• S3 = S2 N S2 = LMLNLML
• S4 = S3 O S3 = LMLNLML O LMLNLML
• S5 = S4 P S4, e o número de movimentos é \(2^5-1=31\).