Raisonnement par reccurence
Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
-
izamane95
- Membre Rationnel
- Messages: 620
- Enregistré le: 31 Aoû 2006, 23:08
-
par izamane95 » 29 Oct 2007, 11:32
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
- Membre Relatif
- Messages: 318
- Enregistré le: 04 Oct 2007, 21:00
-
par klevia » 29 Oct 2007, 11:39
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
- Membre Rationnel
- Messages: 620
- Enregistré le: 31 Aoû 2006, 23:08
-
par izamane95 » 29 Oct 2007, 11:51
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
- Membre Complexe
- Messages: 2077
- Enregistré le: 10 Oct 2007, 18:40
-
par ThSQ » 29 Oct 2007, 18:29
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
- Membre Rationnel
- Messages: 630
- Enregistré le: 19 Juin 2007, 00:54
-
par bruce.ml » 29 Oct 2007, 18:48
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
- Membre Rationnel
- Messages: 620
- Enregistré le: 31 Aoû 2006, 23:08
-
par izamane95 » 29 Oct 2007, 19:31
bruce.ml a écrit: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
- Membre Rationnel
- Messages: 630
- Enregistré le: 19 Juin 2007, 00:54
-
par bruce.ml » 29 Oct 2007, 21:07
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.
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 119 invités