Raisonnement par reccurence

[izamane95]

bonjour
trouver toutes les applications injectives de N ds lui meme qui verifient pour tt n N , f(n) [B]<= n[/B]
je commence déjà par faire une conjecture sur f
f(0)<= 0 pour n=0
f(1)<= 1 et non 0 car injective
f(2)<= 2 je constate donc que f est l'identité mais j'arrive pas à le prouver par recurrence
aidez moi s'il vous plait

[klevia]

Amoins que ton titre soit faux...

tu cherches des applications injectives de IN dans IN tel que pour tout n,
f(n)f(0)<0 dans IN => f(0) n'existe pas ... donc f n'existe pas
et pas besoin de récurrence ...

[izamane95]

non non c'est pas strict c'est inférieur ou egale je m'excuse ...!!!
merci pour ta reponse en tt cas
en fait pour la recurrence je suppose que f(n)=n
il suffit de montrer dc que f(n+1)=n+1
on a f(n+1)<= n+1 et n comme f est injective f(n+1)= n+1 cqfd
vous etes d'accord avec moi???????????????

[ThSQ]

Par l'absurde : tu prends le plus petit n pour lequel
Alors ça veut dire qu'on a réussi à caser n+1 valeurs dans 0..f(n) ce qui est impossible.

[bruce.ml]

Salut,

si tu souhaites absolument le faire par recurrence tu peux le dire ainsi :
pour n=0, c'est facile tu l'as fait. Sinon, supposons que ce soit vrai pour un n fixé, et considérons une application injective , on a , comme f est injective, . Considérons l'application , c'est une bijection. vérifie les hypothèses de récurrence, elle est donc injective, et par suite f aussi !

[izamane95]

Salut,

si tu souhaites absolument le faire par recurrence tu peux le dire ainsi :
pour n=0, c'est facile tu l'as fait. Sinon, supposons que ce soit vrai pour un n fixé, et considérons une application injective , on a , comme f est injective, . Considérons l'application , c'est une bijection. vérifie les hypothèses de récurrence, elle est donc injective, et par suite f aussi !

d'abord merci pour ta réponse et aussi pour ThsQ mais j'ai pas trés bien compris ; moi j'ai procédé autrement :
hypoth de rec: on suppose que f(n)=n
montrons que c'est vraie au rong n+1
on a f(n+1) <= n+1 mais par injectivité de f f(n+1)=n+1 cqfd
mais ce qui me gene ds mon raisonnement c'est que je n'est pas utilisé l'hypothese de recurrence ...où est mon erreu ??
PS: ThsQ c'est ptet une autre maniere de faire mais moi j'aime pas utilisé l'absurde ds ce genre de cituation....pour la recurrence as tu une idee?

[bruce.ml]

En fait tu n'expliques pas bien ce que tu fais :P enfin je crois que je viens de comprendre, et de me rendre compte que j'ai fait un chouille compliqué, il vaut mieux le faire dans l'autre sens.

Soit f de [0,n+1] dans lui même, alors la restriction de f à [0,n] verifie l'hypothèse de recurrence, donc pout tout -1 < k < n+1, f(k) = k, donc f([0,n]) = [0,n], or f est injective donc il ne reste qu'une seule possibilité pour f(n+1) : n+1. et on a fini :) pas besoin de s'embêter à décaler tout ça vers 0.