Exercices TS

[uioka]

Soit A une partie de N∗ contenant 1 et telle que :

i) ∀n ∈ A, 2n ∈ A et ii) ∀n ∈ N∗, n + 1 ∈ A ⇒ n ∈ A.

a) Montrer :

∀m ∈ N, 2^m ∈ A.
b) Montrer : A = N*.

Je vous sollicite afin de savoir si ce que j'ai réalisé est correct puisque cette exercice n'a pas été corrigé. (N ici représente l'ensemble et non un paramètre je ne sais pas comment faire le signe sur clavier.)

a)
conjecture:

∀m ∈ N*, 2^m = q où q est un entier naturel pair

Pm " 2^m = q " pour tout m ∈ N*.

Initialisation

P1 = 2 P1 est vraie.

Hérédité

Fixons m ∈ N* tel que Pm soit vraie, on a donc:

2^m = q
2^(m)*2= 2q
2^(m+1)= 2q

Or 2q est un nombre entier pair, car nous avons la multiplication de deux nombres pairs.

Donc il s'agit de Pm+1 ( je ne sais pas si on peut dire que c'est réellement Pm+1 puisque Pm+1 " 2^(m+1) = q " or ici q veut simplement dire qu'il s'agit d'une valeur positive paire et non un paramètre )



On sait que:

∀n ∈ A, 2n ∈ A et 1 ∈ A

Donc 2 ∈ A 4 ∈ A

Conjecture:

Pn " 2n = q " pour n ∈ N q est un entier naturel pair

Initialisation

2*0=0 P0 est vraie

Hérédité

2n = q

2(n+1) = 2q

Il s'agit de P(n+1) (même chose qu'au dessus)

Donc A contient tout les entiers naturels pairs, hormis 0 car A est une partie de N*,

donc 2^m ∈ A avec m ∈ N*.

Pour m = 0,

2^m = 1 or 1 ∈ A.

Donc, 2^m ∈ A pour tout m ∈ N.




En ce qui concerne la deuxième question je vois pas en quoi la première peut nous aider (hormis si elles sont indépendantes),
puisque N* représente les valeurs positifs pairs et non pairs or on peut montrer que A ∈ N* uniquement avec ce qui est proposer dans l'énoncé .

De plus un deuxième problème cette exercice fait partie des raisonnement par "récurrence à deux termes" et "récurrence forte", or je n'ai pas l'impression d'avoir fait un de ces deux raisonnements sauf s'il s'agit d'une récurrence forte ( je comprends pas réellement le sens sur récurrence forte )

Merci

S.A
-----

[henryallen]

Bonjour,

Pour la question 1:

Je dois avouer que je n'ai pas tout lu, mais on dirait que tu prouves des évidences ... Le plus simple c'est de prendre . On a vraie d'après l'énoncé, et maintenant tu montres que en utilisant une information donnée dans l'énoncé.

Pour la question 2:

Dans le cas de la récurrence simple, on dispose d'une proposition portant sur . On cherche à montrer que .
Dans le cas d'une récurrence forte, on cherche à montrer que si, pour tout , est vraie, alors est vraie.
Donc au lieu de montrer que , tu vas montrer que .

Ici, il est en effet possible d'utiliser une telle récurrence. Déjà, tu peux voir facilement que . Reste à montrer l'inclusion réciproque, donc que tout élément de est dans . Ce que tu peux faire, c'est donc utiliser une récurrence forte et distinguer les cas où est pair et les cas où est impair.

Donc, pour , soit : . est vérifiée d'après l'énoncé. Reste à montrer que . Donc si est pair, que peux-tu dire (comment peut-il s'écrire) ? Et au contraire, s'il est impair, que peux-tu dire de ? Et à partir de là et en utilisant l'énoncé, montre que .

J'espère avoir été clair, ce qui n'est cependant probablement pas le cas
N'hésite pas à reposer des questions si besoin.

PS: si tu veux écrire , tu peux taper:

[tex]\mathbb{N}[/tex]

(ne fais pas attention au HTML, c'est juste pour qu'il ne remplace pas le code par le symbole).

[gg0]

Bonjour Iuoka.

Pour le 1, démontrer autre chose que ce qui est demandé n'a aucun intérêt. Pourquoi as-tu écrit ça ? (pose-toi la question et trouve en toi la réponse, c'est urgent !).

Cordialement.

[eudea-panjclinne]

Le Pm écrit ne traduit pas correctement l'énoncé ni dans l'exercice 1, ni dans le 2.

[A voir en vidéo sur Futura]

[uioka]

Tout d'abord merci pour vos réponses.

OH oui quel horrible raisonnement de ma part (je me suis trop focaliser sur les valeurs que pouvait prendre 2^m), voici ce qui est sûrement attendu:

a)

Pm " 2^m ∈ A " pour tout m ∈

Initialisation

2^0 = 1 P(0) est vraie.

Hérédité
Fixons m ∈ tel que Pm soit vraie, on a donc:
2^m ∈ A


2^(m+1) = 2*2^m

2*2^m car pour tout n ∈ A, 2n ∈ A.

Il s'agit de P(m+1)

b)

Pn " n ∈ A " n ∈

I

1 ∈ A P(1) est vraie.

H

Supposons que Pk est vraie k {1,....,n}. Montrons que n+1 ∈ A.

- Soit n+1 est pair
n +1 ∈ A car 2n ∈ A
Donc tous les entier naturel pair ∈ sont contenus dans A

- Soit n+1 est impair donc n+2 est pair

Or on sait que pour tout n ∈ , n+1 ∈ A -> n ∈ A

Sachant que n+2 ∈ A alors n+1 ∈ A.

Donc n ∈ A, avec n ∈
Donc A =

Est-ce correct à présent ?

[uioka]

Euh non pour la b)
- Soit n+1 est pair
n +1 ∈ A car 2^m ∈ A m ∈ N
Donc tous les entier naturel pair ∈ sont contenus dans A

[ansset]

Ce que tu peux faire, c'est donc utiliser une récurrence forte et distinguer les cas où est pair et les cas où est impair.

je ne pense pas que celà soit l'approche la plus simple.
le i) permet de montrer que toute les puissances de 2 app à A
on peut aussi affirmer que pour tout n, il existe m tel que 2^m >n et 2^m app à A
ensuite , avec la deuxième proposition ii) tout entier < 2^m app à A. ( récurrence par "soustraction'" liée à la deuxième assertion )
donc n app à A

[henryallen]

Hum, un entier pair n'est pas forcément une puissance de 2 (pour le message #6).

Pour reprendre ton post d'avant (#5) je suis d'accord avec la a).

Pour la b), il y a un petit truc que tu as négligé. Si n+1 est pair, alors n+1=2k. Mais il faut montrer qu'on a k<n+1, et donc que k appartient à A (d'après l'hypothèse de récurrence).
De même, si n+1 est impair et donc n+2 pair, n+2=2k, et il faut montrer que k appartient à A.

Sinon le reste me paraît bien (mais peut-être que quelqu'un d'autre trouvera quelque chose à redire, là je suis un peu pressé je regarderai de nouveau ce soir si j'ai le temps).

Sinon peut-être est-il possible d'utiliser la question 1. En effet, toutes les puissances (entières) de 2 sont dans A. Si on prend un entier naturel k, on peut trouver n tel que 2^n<=k<2^(n+1). 2^(n+1) appartient à A, donc 2^(n+1)-1 aussi d'après l'énoncé), et de fil en aiguille k aussi. Évidemment, la rigueur n'est pas de mise dans ce que je viens d'écrire, mais l'idée est là.

Bonne journée

EDIT: totalement grillé par ansset

[gg0]

"Soit n+1 est pair
n +1 ∈ A car 2^m ∈ A m ∈ N"

Tu ne dis pas vraiment pourquoi (n+1) est dans A. Aucune référence à l'hypothèse de récurrence, un m qui apparaît sans lien avec ce qui précède. Explique-toi clairement (tu as le droit de faire des phrases en français courant). Évite ce genre de choses : " ... Pk est vraie k {1,....,n}", tu communiques, ce n'est pas ton brouillon.
Je continue sur "n+1 est pair" : "Donc tous les entier naturel pair ∈ [IMG]https://blogs.futura-sciences.com/cgi-bin/mimetex.cgi?\mathbb{N}*[/IMG] sont contenus dans A" Non, tu n'as pas prouvé ça, seulement que n+1 et un entier pair contenu dans A, tu ne sais rien des autres pairs strictement plus grands, n+3, n+5, ... et tu ne peux pas appliquer la récurrence, car tu es en plein dans la phase hérédité qui n'est pas finie.

Du coup, pour n+1 impair, tu ne peux pas dire comme ça n+2 est dans A, il faut le prouver.

Cordialement.

[Akasuna]

Serais-tu, par hasard, en train de faire les exercices préparatoires à la prépa de Louis le Grand?
Sinon, j'aurai fait la même chose pour le a), mais pour le b), je sèche.

[gg0]

Pour le b, il faut utiliser une "récurrence complète", c'est à dire utiliser l'hypothèse "pour tout indice m entre 1 et n, m est dans A". On initialise pour n=1, puis on commence par n impair, et on utilise le fait que (n+1)/2 est entre 1 et n; puis on traite n pair, on utilise n+2, dont la moitié est entre 1 et n, donc qui est dans A par i) puis on applique ii). On conclut de cela que n+1 est dans A dans tous les cas.

Cordialement.

[eudea-panjclinne]

Une démo par l'absurde de b):
Supposons qu'il existe m0>0 n'appartenant pas à A.

La contraposée de ii) donne
Pour tout n>0 entier naturel, n non dans A implique n+1 non dans A.
Ce qui montre par récurrence que pour tout n>=m0, n non dans A.

Or, avec 1), pour tout n entier, tous les 2^n sont dans A.
D'autre part, pour n entier naturel, 2^n n'est pas borné, il existe au moins un des ces nombres qui est plus grand que m0 donc n'est pas dans A .
Ainsi, on a trouvé un entier dans A et pas dans A...

[0sKiDo]

Pour la b)
posons n = 2^m -1 ∈ IN*, par ii) n+1 = 2^m ∈ A donc 2^m-1 ∈ A
Par descente finie [I 1, 2^m-1 I] ∈ A (disons cet interval =Jm
Pour m-> +inf on a bien IN* c A (car pour n'importe quel k ∈ IN*, il suffit de prendre m assez grand pour que k ∈ l'intervalle Jm ∈ A

Et puisque A c ∈ IN* de manière évidente on a bien l'égalité

Mon raisonnement me semble correcte, dites moi si vous êtes du même avis ^^

Oscar.

[gg0]

Bonjour.

5 ans après, était-ce utile ?
D'autant que ce n'est pas une preuve entièrement rédigée, seulement un schéma de preuve (*). Qui reprend, de façon informelle ce qui a été dit il y a 5 ans.

Cordialement.

(*) et mal rédigé, comme le passage "Pour m-> +inf on a bien IN* c A", comme si IN* et A dépendaient d'une variable m.

[0sKiDo]

A ce que je sache, l'exercice existe toujours (fiche LLG) et mérite de trouver solution non ? Même 5 ans après.

Surtout que si ma réponse est mal rédigée je serai ravi de savoir comment mettre tout ça au propre. (Je reconnais après relecture avoir inversé des symboles appartient et inclus, c'est très grossier comme erreur et je m'en excuse).

Bien à vous.
O.

[gg0]

Il y a tout ce qu'il faut dans les messages pour écrire une solution complète (et même plusieurs). Comme l'exercice est public, en écrire un corrigé n'est pas utile (et ce n'est pas le rôle du forum). Mais comme tu veux essayer de faire cet exercice, si tu en rédiges un corrigé, on pourra te dire ce qu'il vaut. Attention : Un corrigé rédigé, sinon de sera de la redite.