bonjour,
je suis en premiere année d'économie et j'ai assez de mal avec les mathématiques. notamment avec cet exercice, alors si une personne pourrait m'aider et m'expliquer ca serait vraiment génial ! merci d'avance !
On appelle partie d'un ensemble E un sous ensemble d'éléments de E
Démontrez que le nombre de parties distinctes de {1,2,...n} est2^n en utilisant une démonstration par récurrence et une démonstration directe
ainsi, comme tout ensemble de n éléments est 'isimorphe', il contient 2^n sous ensembles distincts
Bonjour,
par récurrence : pour n=1, il n'y a que deux (21) parties : et {1}.
Soit n quelconque, supposons qu'il y a 2n parties de {1,2,...,n}.
Pour compter les parties de {1,2,...,n+1}, on les sépare en deux catégories :
celles qui ne contiennent pas n+1 : ce sont les parties de {1,2,...,n}
celles qui contiennent n+1 : on les obtient en réunissant n'importe quelle partie de {1,2,...,n} à {n+1}.
On a donc dans chaque catégorie 2n parties, donc en tout 2*2n=2n+1 parties
Salut Rachel
Une démo directe: basée sur un raisonnement de probabilité ou de dénombrements plutot (comme en term!)
tu as tes n éléments et tu dois construire des parties de E (disons des petits paquets) avec ces éléments donnés!
En fait pour chaque élément, tu peux décider de la prendre ou pas (tu as deux choix)
tu dois faire ce choix n fois, ce qui fait bien 2^n paquets possibles!
par récurrence: soit P la propriété cherchée
On verifie P1: l'ensemble {1} a bien 2 parties (attention subtilité) : {1} et {vide} soit 2^1
ensuite on prend E de n éléments, on considère qu'il a 2^n parties
on rajoute un (n+1)eme éléments
pour chacune des 2^n parties existantes on peut soit la rajouter, soit ne pas le rajouter ce qui fait 2*2^n parties qui vaut bien 2^(n+1)
P1 vraie,
Pn entraine P(n+1)
donc P vraie pour tout n
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :