Suites : tour de hanoi version 2

Encore moi,

Cette version de la tour de hanoi est posée en exercice dans le livre concrete mathematics de Donald E. Knuth . Le sujet est en anglais.

"Find the shortest sequence of moves that transfers a tower of n disks
from the left peg A to the right peg B, if direct moves between A and B
are disallowed. (Each move must be to or from the middle peg. As usual,
a larger disk must never appear above a smaller one.)"

Le transfer direct du piquet A à B est interdit. Il faut un transfer à un piquet intermédiaire. Trouver le nombre de mouvement le plus court, pour un transfer de n disques.

Après réflexion avec deux disques, je pense qu'il faut $M_n$ = $6_{n-1}$ + 2 mouvements.
Le grand disque bouge deux fois. Et ceux du dessus, 2 fois (un aller), 2 fois (un retour) et enfin 2 fois (un autre aller). Après généralisation à n-1 ca fait donc $M_n$ = $6_{n-1}$ + 2 avec n > 0, $M_0$ = 0. Il ne me restait qu'à résoudre l'équation.

Mais j'ai faussé.

Voilà ce qu'ils trouvent et je ne comprend pas.

If Xn is the number of moves, we have $X_0$ = 0 and $X_n$ = $X_{n-1}$ + 1 +
$X_{n-1}$ + 1 + $X_{n-1}$ when n > 0. It follows (for example by adding 1 to both
sides) that $X_n$ = $3^n$ - 1. (After $\frac{1}{2}X_n$ moves, it turns out that the entire tower
will be on the middle peg, halfway home!)

Merci de votre aide.