Fonction de IN dans IN

[lémathdabor]

Bonsoir tous le monde ;

j'ai du mal avec l'exercice suivant :

Si f :

Vérifie f(n+1) > f(f(n))

alors n , f(n)= n

Merci
Cdt
-----

[Thorin]

Salut,

tu peux déjà commencer par montrer que . Après, essaie de voir pourquoi .

[lémathdabor]

L'ennui c'est que je ne vois pas comment montrer que :

f(1) > f(f(0)) .....

[Thorin]

Je n'ai pas été très explicite dans mon premier message pour la simple raison que moi même je n'étais pas beaucoup plus loin que ce que je proposais
Il me semble finalement avoir réussi à trouver une solution, que je vous soumets :


Montrons que 0 a un antécédent par f.
soit
soit la suite définie par et . est défini tant que est non nul.
Supposons (par l'absurde) que 0 n'admette pas d'antécédent par f. Ainsi, est toujours défini.
on a alors .
Puis, comme est non nul, on peut écrire : d'où .
En poursuivant de la même manière, par itération, on arrivera finalement à écrire f(u_k)<a-(k-2), avec k-2>a, ce qui est contradictoire, puisque f est à valeurs positives. On en conclut que 0 a bien un antécédent.
Soit donc k tel que (on vient de prouver son existence), alors soit , soit . comme f est à valeurs positives, on a nécessairement k=0
Finalement, , et de plus, si , alors, .


supposons (récurrence) que , ... , pour un certain .
Supposons aussi que si alors
Alors, soit et (ces 2 min existent clairement...)

Alors, .

On a, puisque , on a .

Donc par def de p, et par def de m, .
Si on avait , d'après l'hypothèse de récurrence (la deuxième hypothèse), on aurait , et donc : contradiction. On en déduit que .
On en déduit que a un antécédent !

Continuons.
Soit donc h tel que , puisque a bien un antécédent.
donc . Donc (à nouveau par hypothèse de récurrence)
donc donc
donc car sinon, on aurait et on aurait donc , alors que
finalement on a bien , donc l'hérédité est prouvée.


Par récurrence, la propriété est prouvée.



Etant donnée que c'est relativement subtil, et qu'il est tard, merci de me dire si vous voyez des erreurs...
Il doit y avoir plus court, peut être même que ma récurrence ne sert à rien...mais ça a l'air de marcher quand même.

Bonne nuit.

[A voir en vidéo sur Futura]

[Thorin]

NB : vous pouvez poster pour dire que vous ne voyez pas d'erreurs aussi

[ericcc]

C'est un exo d'olympiades : http://michel.quercia.free.fr/alg-gen/n.pdf

[prgasp77]

J'ai peut être quelque chose de plus élégant. L'idée maitresse est de montrer indirectement que et sont croissantes.

Définition
Soit . .



Plus petit élément
Il est évident que ce plus petit élément n'est pas de la forme car lui est inférieur (par définition de ).
Or, . Ainsi, n'est pas ce plus petit élément car lui est inférieur (toujours par définition sur ).
Donc, .



Montrons que
. Or, , ce qui est absurde.
Donc, , . De plus, (puisque est l'unique plus petit élément).
En appliquant cette propriété à on en déduit que et que . Par récurence on démontre ensuite que pour tout , et que .