Missatge: Si volem moure n peces a una posició, el que podem fer és moure recursivament n-1 peces a l'altra posició lliure, després more la de baix on toca, i després tornar a moure recursivament les n-1 peces a on toca. Per tant la recurrència és a_n = 2*a_{n-1} + 1, i deixo la resolució de la fórmula exacta com a exercici :P

Resposta: Amb una mica d'esforç és fàcil de desenvolupar la sèrie: (en blanc)  a_n = 2 a_{n-1} + 1 = 2^{n-1} + … + 2 = 2^n - 1