Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup LogiqueTopics traitant de logique [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Partager :

Récurrence forte bijectivité

Posté par
Dreamyy 20-09-18 à 20:40

Bonjour,

Je suis actuellement en MPSI et nous avons fait une récurrence forte. Cependant, la rédaction n'est pas top je trouve (j'ai mal recopié le cours).

Serait-il possible de me rédiger la récurrence ?

Voici l'énoncé :

Soient n et f une bijection de[\![0,n]\!] dans lui-même telle que pour tout k [\![0, n]\!], f(k) \leq k..
Montrer que pour tout k [\![0,n]\!] , f(k) = k.

Ce que j'ai écris :


P(k) = "f(k) =k"

Init : k= 0

f(0) [\![0,n]\!]
f(0) 0
donc f(0) = 0

Hérédité :
Soit k [\![0,n-1]\!]

j[\![0,k]\!], f(j) = j

Par hypothèse,  f(k+1) k+1

et f(k+1) \begin{Bmatrix} f(j) , j \in [\![0,k]\!] \end{Bmatrix}

Or j [\![0,k]\!], f(j) = j
donc f(k+1) [\![0,k+1]\!] \ [\![0,k]\!]
donc f(k+1) = k+1
ce qui achève l'hérédité

Pouvez-vous m'aider, le truc avec j je ne comprends pas tout ...

Posté par
carpediemre : Récurrence forte bijectivité 20-09-18 à 21:19

salut

parce que tu as oublié l'hypothèse de bijectivité !!

je mets des < pour =< ...

H(k) : 0 < i < k => f(i) = k

or f(k + 1) < k + 1 et par bijectivité f(k + 1) <> f(i) pour 0 < i < k donc f(k + 1) < k + 1 et f(k + 1) > k + 1 => f(k + 1) = k + 1

...

Posté par
jsvdbre : Récurrence forte bijectivité 20-09-18 à 21:24

Bonsoir Dreamyy.

Ton hérédité commence par \forall j \in [[0,k]],~ f(j) = j . Autrement dit, les valeurs de f sont connues sur [[0;k]].

Par conséquent, f(k+1) n'est pas l'une de ces valeurs puisque f est une permutation de [[0;n]].

Donc, avec des quantificateurs, cela donne, \forall j \in [[0;k]],~f(k+1) \neq f(j)

ou encore f(k+1) \notin \{f(j)~/~j\in [[0;k]]\}.

Posté par
Dreamyyre : Récurrence forte bijectivité 21-09-18 à 17:06

Bonjour,
Dsl du temps de réponse, j'ai pas eu vraiment le temps de regarder.

Merci pour vos réponses ^^

Je ne comprends pas trop ce que tu as écrit (carpediem)

jsvdb,
Le truc où j'ai du mal, c'est avec le j. J'ai l'impression que la récurrence est mal rédigée ...

Posté par
carpediemre : Récurrence forte bijectivité 21-09-18 à 17:12

c'est pourtant limpide ...

hypothèse de récurrence : H(k)  :  0 \le i \le k => f(i) = i

or f(k + 1) \le k + 1  et f est bijective

donc 0 \le i \le k => f(i) \ne f(k + 1) => k + 1 \le f(k + 1) \le k + 1 \iff f(k + 1) = k + 1

donc H(k) => H(k + 1)

Posté par
Dreamyyre : Récurrence forte bijectivité 21-09-18 à 17:20

Nous n'avons pas encore fait le cours sur la bijectivité ... etc

Pourquoi f(k+1) k+1 ?  
Je ne comprends pas ça m'énerve. J'suis Désolé

Posté par
carpediemre : Récurrence forte bijectivité 21-09-18 à 17:41

Dreamyy @ 20-09-2018 à 20:40

Soient n et f une bijection de[\![0,n]\!] dans lui-même telle que pour tout k [\![0, n]\!], \red f(k) \leq k..

Montrer que pour tout k [\![0,n]\!] , f(k) = k.
un peu de sérieux !!! tu fais un exercice sans savoir de quoi tu parles !!

un peu de sérieux !!! quelle est l'hypothèse sur f ??

Posté par
Dreamyyre : Récurrence forte bijectivité 21-09-18 à 17:42

Ah d'accord, je vois. Mercii. Le problème c'est que j'ai du mal avec j, k, n etc ...

Posté par
jsvdbre : Récurrence forte bijectivité 21-09-18 à 18:09

Ce ne sont que des lettres.
Il est donc important de connaître leurs place, fonction et rôle dans un raisonnement


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !