Démontrons par récurrence...

[baldebaran]

Bonjour à tous,
Je suis en 2ème année d'informatique, et j'ai un petit souci en mathématiques.
Je cherche à démontrer (dans le cadre d'un exercice sur les arbres équilibrés AVL) cette formule de récurence :
pour tout h>=0 ,

avec la formule et nb(0)=1, et nb(1)=1

J'en arrive à essayer de démontrer que pour tout h>=1.
Mais à partir de là, je bloque et même j'arrive à quelquechose de faux. :mur:
Quelqu'un peut-il m'aider ?
Merci d'avance.

P.S. : j'ai essayé le latex pour mettre mes formules proprement, mais avec les doubles exposants, ça foirait et c'était presque illisible. Si quelqu'un m'explique, je suis ok pour corriger ça

EDIT: j'ai un peu compris le LATEX, donc j'ai un peu corrigé mes formules, pour que ça soit plus clair.

[baldebaran]

Je vois qu'un collègue à moi a posté également un message.
http://www.maths-forum.com/showthread.php?t=53069
Cependant, mon message étant plus clair, je le laisse quand même.
Une réponse pour deux devrait suffir.
Merci d'avance.

[tize]

Bonjour,
pour mettre les choses au clair :
vous voulez montrer que ou ?

[baldebaran]

La première, chef !
Mais comment tu fais pour que ça soit lisible, toi ?

[tize]

ok, je vais voir...pour les formules, c'est du latex, fais une recherche du mot LATEX sur le forum tu trouveras des instructions...

[fatal_error]

Bonjour,


On veut :

[tize]

Je ne comprends pas la première inégalité...

[baldebaran]

Moi j'ai compris ! Merci beaucoup, c'était pas si sorcier mais fallait y penser
Pour la première inégalité, on a :


avec 2nb(h).nb(h-1)>0

[tize]

bah je voudrais bien si 2nb(h).nb(h-1)<0 mais pas avec 2nb(h).nb(h-1)>0...

[baldebaran]

oulalala :cry:
On voit que ça fait longtemps que je ne fais plus de maths :--:
Tu as raison, en effet.
Bon bah du coup, retour à la case départ :hum:

[fatal_error]

Oulaoula oui! :briques:

[tize]

Voici ce que je vous propose :
donc :
car il est facile de montrer que l'un des termes entre parenthèses :

[alben]

Bonjour,
C'est un peu fastidieux mais ça marche.
En faisant à l'envers :
on veut montrer
équivaut à
équivaut à
équivaut à
équivaut à
et finalement vraie pour n>0
Il suffit de reprendre tout ça en commençant par la fin

edit grillé...

[baldebaran]

Là, ça me semble tout à fait juste, mais je vérifierai ça plus dans le détail cet après-midi.
En tout cas, merci d'y avoir accordé un peu de votre temps. :++: