Conjecture et récurrence

Bonjour, voila j'ai un problème à une question de mon DM. j'espére que vous pourrez m'aider.
Alors l'exercice c'est:

Jeu des tours de Hanoï

On considère trois lignes verticales A, B et C. Le jeu consiste à amener sur le tige C les disques empilés sur la tige A. pour cela, on utilise la tige B comme intermédiaire en respectant les règles suivantes:
-On ne déplace qu’un disque à la fois
-Tout disque doit être au-dessus d’un disque de diamètre supérieur

Soit d(n) le nombre minimal de déplacements, n désignant le nombre de disques.
Le suite d(n))est définie par d1=1 et d(n+1)=2d(n)+1

Il faut calculer d(2), d(3), d(4) et d(5)
J’ai trouvé:
d(2)=3, d(3)=7, d(4)=15, d(5)=31
Donc jusque la ça va.
Après, la question suivante c’est:
Conjecturer une expression de d(n) en fonction de n.
J’ai trouvé d(n)=2^(n) -1
Mais je ne sais pas comment y arriver (mais il me manque le raisonnement)
Donc j'aimerai donc savoir comment procéder pour arrivé a ce résultat.
Merci d'avance

salut

tu peux essayer de faire ça par récurrence

c'est fondé (premiers rangs)
suppose que d(n)=2^(n) - 1 (HR)

et montre que c'est vrai aussi au rang suivant.

alors tu pars de d(n+1) = 2d(n)+1 et tu remplaces par l'expression donnée par (HR).

ça doit se faire facilement.

@+

Merci.
Justement la suite à "Conjecturer une expression de d(n) en fonction de n."
c'est la démontrer par récurrence.
mais comment on trouve d(n)=2^(n)-1? comment on suppose que c'est ça?
car j'ai fait pour la deuxième partie de la question: d(n+1)=2d(n)+1=2(2^(n)-1)+1=2^(n+1)-1

mais comment on trouve d(n)=2^(n)-1?
Merci

la démarche est là :
Zauctore-autocitation

c'est fondé (premiers rangs)
suppose que d(n)=2^(n) - 1 (HR)
et montre que c'est vrai aussi au rang suivant.

alors tu pars de d(n+1) = 2d(n)+1 et tu remplaces d(n) par l'expression donnée par (HR).

ça doit se faire facilement.

la relation sera la même que d(n)=2^(n)-1, sauf que ce sera au rang suivant (pour n+1, quoi).

essaie !

@+

je trouve pas XD
c'est pas grave, j'pense que ce que j'ai déjà fait doit répondre à la question.
Merci pour votre aide.

re.

je te montre alors

on sait que la relation est vraie pour n=1,ou 2...

maintenant je fais l'hypothèse que cette relation est vraie au rang n, c'est-à-dire que d(n) = 2^n - 1.

maintenant je m'intéresse à d(n+1).

je sais que d(n+1) = 2d(n) +1, je peux donc remplacer

d(n+1) = 2(2^n - 1) + 1 = ... = 2^(n+1) - 1

c'est bien la relation attendue (la même au rang n+1 qu'au rang n) : par récurrence, la propriété est démontrée.

ok ?

oui pour ça c'est bon, j'ai compris, et je l'avais réussi mais c'est le "maintenant je fais l'hypothèse que cette relation est vraie au rang n, c'est-à-dire que d(n) = 2^(n) - 1.'
comment on trouve cette hypothèse?
c'est ça que je n'ai pas compris

non, on ne la trouve pas, sauf par essais, erreurs et conjecture (comme tu as fait avant).

pour prouver que pour tout entier n on a d(n) = 2^(n) - 1

il faut montrer en fait que si elle est vraie au rang n (HR), alors la propriété est encore vraie au rand n+1

c'est ce qu'on appelle l'hérédité de la propriété. il faut donc supposer que pour un certain n elle est vraie, c'est ce que j'ai fait, et qu'alors automatiquement elle se transmet au rang n+1

enfin, puisqu'elle est vraie au rang 1, alors elle sera automatiquement vraie au rang 2, puis au rang 3 puis au 4 rang, puis 5 puis etc. jusqu'à n'importe quel entier n.

c'est le principe du raisonnement par récurrence.

je te suggère de lire attentivement le paragraphe Récurrence simple sur les entiers de l'article wikipedia.

ok
c'est bon j'ai compris
merci pour votre aides
et bonne aprés midi

t'es une rapide, toi.
bonne après midi et bon weekend aussi !
@+

Salut Zauctore,

La compréhension de la méthode de démo par réc n'est pas tjrs facile à saisir. Pourquoi on fait une initialisation puis une hérédité et enfin conclure.

Je me souviens que tu avais, qqpart ici, fait le parallèle avec les dominos : On fait tomber le premier qui fait tomber le second etc...). J'ai trouvé l'idée excellente. Elle devrait être utilisée par les profs pour aider à piger le raisonnement.

Désolé du hors sujet.

ce n'est pas du tout hors sujet babgeo. merci de me rappeler ce que j'ai oublié de préciser dans mes posts précédents ! ça complète très utilement ce que j'ai raconté jusque là en restant un peu trop formel finalement.

c'est vrai que le principe d'une preuve par récurrence, bien qu'il soit fort simple en définitive (avec le recul d'une année par exemple), est vraiment difficile à saisir pour les débutants de TS.

merci de ne pas hésiter à poster tes commentaires lorsque tu les juges pertinents !

@+

Ce n'est pas que j'suis une rapide, c'est que j'avais déjà fait l'exo mais que je ne comprenais pas comment on trouvé d(n)=2^(n) -1
et si je devais le mettre directe comme ça et après faire la récurrence ou expliquer avec un raisonnement avant. enfin merci pour votre aides.