Raisonnement par récurrence

[invite9e66327d]

Bonsoir,
j'ai un exercice de recherche a effectuer en maths
Seulement, je ne sais pas comment commencer,

On pose le problème suivant : "Quel est le nombre de parties d'un ensemble à n éléments?"

Exemple : On considère l'ensemble E={1;2;3} qui possède 3 éléments. Ses différentes parties sont :
(vide) {1} {2} {3} {1;2} {1;3} {2;3} et E
Il possède donc 8 parties.


Afin de comprendre le raisonnement, j'ai regarder ce qu'il se passe pour l'ensemble E={1;2;3;4}
(vide) {1} {2} {3} {4} {1;2} {1;3} {1;4} {2;3} {2;4} {3;4} et E
Il possède donc 12 parties

de même pour E={1;2;3;4;5}
(vide) {1} {2} {3} {4} {5} {1;2} {1;3} {1;4} {1;5} {2;3} {2;4} {2;5} {3;4} {3;5} {4;5} et E
Il possède donc 17 parties

J'en déduit donc que pour un ensemble à n éléments, on a obligatoirement 1partie (vide) + 1 partie (E) + N partie + ...
-----

[Jon83]

Bonsoir,
Afin de comprendre le raisonnement, j'ai regarder ce qu'il se passe pour l'ensemble E={1;2;3;4}
(vide) {1} {2} {3} {4} {1;2} {1;3} {1;4} {2;3} {2;4} {3;4} et E
Il possède donc 12 parties
...

Tu en oublies quelques uns ...

[invite9e66327d]

lesquels ?

[Jon83]

lesquels ?

{1 2 3}, {1 2 4} ........ {1 2 3 4}

[A voir en vidéo sur Futura]

[invite9e66327d]

en effet, je n'avais pas vu ça comme ça.
Donc pour E={1;2;3;4}
on a (vide) {1} {2} {3} {4} {1;2} {1;3} {1;4} {2;3} {2;4} {3;4} {1;2;3} {1;2;4} {1;3;4} {2;3;4} et E
donc on a donc 16 parties

Pour E={1;2;3;4;5}
on (vide) {1} {2} {3} {4} {5} {1;2} {1;3} {1;4} {1;5} {2;3} {2;4} {2;5} {3;4} {3;5} {4;5} {1;2;3} {1;2;4} {1;2;5} {1;3;4} {1;3;5} {2;3;4} {2;4;5} {3;4;5} {1;2;3;4} {1;3;4;5} {2;3;4;5} et E
donc on a 27 parties


C'est bien ça ?

[Jon83]

Pour E={1;2;3;4;5}
on (vide) {1} {2} {3} {4} {5} {1;2} {1;3} {1;4} {1;5} {2;3} {2;4} {2;5} {3;4} {3;5} {4;5} {1;2;3} {1;2;4} {1;2;5} {1;3;4} {1;3;5} {2;3;4} {2;4;5} {3;4;5} {1;2;3;4} {1;3;4;5} {2;3;4;5} et E
donc on a 27 parties
C'est bien ça ?

Il en manque: tu devrais en avoir 32...Cherche encore un peu!
En résumé:
- pour un ensemble de 3 éléments il y a parties
- pour un ensemble de 4 éléments il y a parties
- pour un ensemble de 5 éléments il y a parties

Tu peux donc conjecturer que pour un ensemble de n éléments il y aura parties.

Reste à établir la démonstration par récurrence!

[invite9e66327d]

Je ne parviens pas a trouver les parties manquantes.. Pouvez-vous m'aider ?

[invite9e66327d]

Problème résolut

[invite9e66327d]

Voilà ce que j'ai fais :

On peut alors conjecturer que pour un ensemble à n éléments, il y aura 2^n parties. On souhaite alors le démontrer :

Démonstration :
On note Pn la propriété définie par
Pn : "n éléments = 2^n parties" avec n E N

Initialisation : On commence par étudier P0 afin de vérifier si cette propriété est vraie, soit :
P0 : " O élément = 2^0 partie"
La propriété P0 est vraie car pour un ensemble E={0} on une seul partie qui est (vide)

Hérédité : Soit n E N. On suppose que la propriété Pn est vraie, soit :
Pn : "n éléments = 2^n parties"
Montrons que la propriété Pn+1 est vraie également, soit :
Pn+1 : "n+1 éléments = 2^(n+1) parties"


Je bloque a partir d'ici..

[Médiat]

Je bloque a partir d'ici..

Un ensemble E(n+1) à n+1 éléments c'est juste un ensemble à n éléments auquel on ajoute un élément ; comment fait-on pour définir un sous-ensemble de E(n+1), en ayant en tête ce nouvel élément (qu'en fait-on).