Suites numériques 1ère générale

Sujet du devoir

Bonjour, j'ai besoin de votre aide en maths svp. Je vous remercie par avance :) 

Le problème des Tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français Edouard Lucas en 1892, et considéré à déplacer des disques de diamètres différents d'une tour de "départ" (A) à une tour d' "arrivée" (C) en passant par une tour "intermédiaire" (B) et ce en un minimum de coups, tout en respectant les règles suivantes :


- on ne peut déplacer plus d'un disque à la fois ;
- on ne peut placer un disque que sur un autre disque de diamètre plus grand ou sur un emplacement vide ;
- un disque ne peut être placé que sur une des trois tours.

Soit n un nombre entier naturel non nul. Au départ, les n disques sont placés sur la tour A. On note (un), le nombre minimal de déplacements nécessaires pour que les n disques soient placés sur la tour C.


1°) Déterminer u1, u2 puis u3, et vérifier que u4 = 15.

2°) En remarquant que pour pouvoir déplacer le plus grand disque de A vers C, il est nécessaire d'avoir au préalable empilé les n-1 premiers disques en B, expliquer pourquoi la suite (un) vérifie :

{ u1 = 1
{ ∀n ≥ 2, un = 2un-1 + 1


3°) On note vn = un + 1.

a- Calculer les premiers termes de la suite (vn) puis conjecturer sa nature.
b- Démontrer la conjecture précédente.
c- En déduire l'expression de un en fonction de n.

4°) On dispose de 64 disques et on suppose que chaque déplacement de disque demande 1 seconde.
Combien de temps au minimum demande le déplacement complet de la tour ?