Bonsoir, je suis un eleve de terminal S du lycée Diderot a Lyon.

J'ai un probleme sur un exercice ou il faut démontrer une suite de récurrence.

Voici le probleme, si vous pourriez me donnez quelques indications pour comprendre l'énoncé cela me serait d'une grande aide. Merci d'avance.


Soit un ensemble E ayant n elements.

a) On choisit un élément k quelconque dans E.
Expliquer pourquoi il y a autant de parties de E qui ne contiennent pas k que de partie de E qui contiennent k.

b) Utiliser la propriété établie dans la précédente question pour démontrer par récurence q'un ensemble de k élément possède 2^n parties.

*** message déplacé ***

Si tu as quelque connaissance en informatique je vais pouvoir t aider un petit peu:

Imagine un emplacement memoire de n bits. c'est un ensemble (E) de n bits.
On a ici 2^n nombres possibles.
On peut aussi voir ca comme 2^n partie de E. On aura a chaque fois mis a 1 les bits choisis pour notre partie de E.

Si tu me suis bien resoudre la question a) n'est pas tres complique.
Disons que k est le premiers bit de notre emplacement memoire.
alors il suffit de regarder combien on a de chiffre possible si k=1(ensemble avec k)
et combien si k=O(ensemble sans k).

la question b) ne pose pas de probleme.

Je suis désolé de te dire que je ne comprends pas tout ce que tu dis, j'ai essayé de comprendre ton explication avec les bits mais je ne comprends pas.

En gros faut il y a autant d'emplacement mémoire avec et sans k.
Mais comment démontrer ca ?

je peus pas t en vouloir ... .j ai explique ca un peu vite surtout si tu ne maitrise pas bien le binaire.

Mon explication etait la pour t aider a y voir plus claire avec les ensembles.(une bonne vision du binaire peu beaucoup aider).
repondre a b) par recurrence est simple.

tu supposes la propriete de a) vrai (parties avec k = partie sans k).
de meme on suppose P : partie deE = 2^n
1)initialisation:
parties_de_E(1) = 2, en effet 2^1=2
2)recurrence:
parties_de_E(n) = partie avec k + partie sans k
                 = 2 * partie de E sans k
                 = 2 * parties_de_E(n-1) (on a E avec un element en moins).
3)on a immediatement :
partie de E(n) = 2*2...*2 (n fois) = 2^n

j'espere que ca te va, desole pour ma pedagogie foireuse.

Sinon pour le a)
on dit qu'un ensemble de 3 elements E, c'est /_/_/_/  ,cad 3 cases.
quand on marque 1 dans certaine case c'est qu on les choisit comme partie de E.
On a :
/0/0/0/
/0/0/1/
/0/1/0/
/0/1/1/
/1/0/0/
/1/0/1/
/1/1/0/
/1/1/1/
on a 8 parties distinctes. on voit facilement que rajouter un bit multiplie le nombre de chiffre possible par 2 : c'est le principe du binaire.
si on dit que k est le bit numero 1 on a :
/0/0/0/
/0/0/1/
/0/1/0/
/0/1/1/
les parties sans k et :
/1/0/0/
/1/0/1/
/1/1/0/
/1/1/1/
les parties avec k.
on comprend que partie sans k et partie avec k valent toutes les 2 : 2^n-1
malheureusement mon explication suppose qu on sache deja que le nombre de partie d un ensemble soit 2^n.
enfin j espere que ca te servira .

tchao

Merci beaucoup, pour la démonstration j'ai compris merci, pour le reste je vais me pencher sur le probleme a tete reposer...

Merci

Bonjour,

sans passer par l'informatique, il existe un moyen très simple de démontrer le a):

Soit E_k l'ensemble des parties contenant k
Soit E_-kl'ensemble des parties ne contenant pas k

Je définis l'application de E_k vers E_-k comme suit:
P E_k, je lui associe l'ensemble P' E_-k comme suit:
P P' en construisant P' = P\{k} (je retire k à P)
A toute partie de E contenant k, j'associe donc bien une et une seule partie de E ne contenant pas k
(précisément la partie initiale à laquelle j'ai enlevé k).

Cette relation est une bijection, car à tout élément de E_-k j'ai, par la relation , associé un élément et un seul de E_k (son antécédant par ).
En effet, pour trouver l'antécédant d'une partie ne contenant pas k, il suffit de lui ajouter k:
P P' P = P' {k}

Puisque j'ai une bijection entre eux ensembles (E_k et E_-k), ces deux ensembles ont le même cardinal, c'est à dire, puisque ce sont des ensembles finis, le même nombre d'éléments.

Il y a donc autant de parties de E qui contiennent k que de parties de E qui ne contiennent pas k.

Le b) se déduit alors trivialement par récurrence comme l'a montré "log0"