Bonjour, alors tu sembles utiliser des formules un poil compliquées (personnellement j'ai tout oublié), lorsque tu ne t'en sors pas avec ce genre de démonstration, il faut essayer par tâtonnements.
Pour l'initialisation, tu as raison.
Pour l'hérédité, supposons que la propriété est vraie pour n supérieur ou égal à 0 fixé (n'oublie pas de l'écrire qu'il est fixé, c'est très important), pouvons qu'elle l'est au rang n+1.
Déjà, par hypothèse de récurrence, on sait que Card (P(n)) = 2^n. En imaginant cet ensemble, on peut l'écrire P(n) = { Ensemble vide, {1}, {2},..., {n} (n éléments) , {1,2}, {1,3},..., {1,n} (n-1) éléments etc}.
Tu supposes donc, que P(n) soit exactement écrit de cette façon. On commence par les ensembles constitués d'un seul élément, puis 2, puis 3 etc jusqu'à n elements, et on les dénombre tous.
Comptons déjà le nombre d'ensembles, constitués d'ensembles d'un seul élément. C'est facile tu en as n+1, Ensemble vide, {1}, jusqu'à {n}.
Pour ceux à 2 elements, pour les ensembles constitués du chiffre 1, on commence à {1,2} (on ne recompte pas le même élément), ce qui fait n-1 éléments. Pour le chiffre 2, on exclut la même chose, avec {2,1} en prime, donc (n-2) éléments.
On continue, jusqu'à {n,n} qui est impossible.
Donc pour l'instant, on dénombre : (n+1) + (n-1) + (n-2) +... + 1 elements.
Pour ceux à 3 elements, même procédé, au début on aura n-2 + (n-3) +... + 1 elements. En effet, on commence à {1,2,3} jusqu'à {1,2,n} puis {2,3,4} jusqu'à {2,3,n}, puis {3,4,5} jusqu'à {3,4,n} jusqu'à aboutir au {n-2,n-1,n}.
À chaque fois qu'on augmente le nombre d'éléments de 1, on dénombrera 1 élément en moins dans le dénombrement, ce qui est logique.
On pose S1 = n+1 pour le 1er compte, S2 = (n+1) + (n-1)+...+1 = S1 + 1 +... +(n-1).
Puis S3 = S1 + S2 + 1 +... +(n-2). On déduit finalement, que Sn = Card (P(n)) = 2^n par hypothèse de récurrence.
Par conséquent, Card(P(n+1)) = S(n+1) = Sn + S(n-1) +...+S1. Or, on a prouvé que Sn = S(n-1)+...+S1 d'où S(n+1) = 2*Sn = 2^(n+1).
Ou bien, tu as encore plus simple mais c'est le genre d'astuce qui, si tu la trouves, t'énerve. Il s'agit ici, de la somme du nombre de combinaisons sans répétition des éléments de E. Donc, tu peux procéder sans récurrence.
Par exemple, si tu veux trouver le nombre de parties d'un ensembles à 3 éléments, tu as {Ensemble vide}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} = 8 éléments.
Il faut donc : Combinaisons de 1 élément parmi 3 = (1 parmi 3) = 3! / (1!(3-1)!) = 3. Puis, combinaisons de 2 éléments parmi 3, 2 parmi 3 = 3. Et enfin, combinaisons de 3 éléments parmi 3, donc une.
Et on ajoute l'ensemble vide à la fin, qui correspond à 0 éléments parmi 3.
Pour n elements, tu fais la somme (0 parmi n) + (1 parmi n) + (2 parmi n) +... + (n parmi n).
Et miraculeusement, on reconnaît le Binôme de Newton, Somme des k parmi n, pour k allant de 0 à n de (1*1) = Somme des k parmi n, pour k allant de 0 à n de (1^k * 1^(n-k)) = (1+1)^n = 2^n.
3 votes Thanks 2
broucealways
Remarque : Par récurrence, c'est très complexe, peut-être que tu aurais pu réussir, mais faut pas se louper et être rigoureux dans le dénombrement
frolgarance
oui on est en train de l'apprendre et tu ne fais que confirmer que c'est ultra complexe, je lirai ça en détail ce soir mais merci bcp déjà !
broucealways
Au début si tu n'y arrives pas, je te conseille d'acheter des billes, ou des cartes, de les manipuler un peu en les comptant, avec l'habitude ça ne t'effrayera plus
frolgarance
je suis pas sûre de trouver n+1 cartes mais j'essayerai ^^
Lista de comentários
Explications étape par étape:
Bonjour, alors tu sembles utiliser des formules un poil compliquées (personnellement j'ai tout oublié), lorsque tu ne t'en sors pas avec ce genre de démonstration, il faut essayer par tâtonnements.
Pour l'initialisation, tu as raison.
Pour l'hérédité, supposons que la propriété est vraie pour n supérieur ou égal à 0 fixé (n'oublie pas de l'écrire qu'il est fixé, c'est très important), pouvons qu'elle l'est au rang n+1.
Déjà, par hypothèse de récurrence, on sait que Card (P(n)) = 2^n. En imaginant cet ensemble, on peut l'écrire P(n) = { Ensemble vide, {1}, {2},..., {n} (n éléments) , {1,2}, {1,3},..., {1,n} (n-1) éléments etc}.
Tu supposes donc, que P(n) soit exactement écrit de cette façon. On commence par les ensembles constitués d'un seul élément, puis 2, puis 3 etc jusqu'à n elements, et on les dénombre tous.
Comptons déjà le nombre d'ensembles, constitués d'ensembles d'un seul élément. C'est facile tu en as n+1, Ensemble vide, {1}, jusqu'à {n}.
Pour ceux à 2 elements, pour les ensembles constitués du chiffre 1, on commence à {1,2} (on ne recompte pas le même élément), ce qui fait n-1 éléments. Pour le chiffre 2, on exclut la même chose, avec {2,1} en prime, donc (n-2) éléments.
On continue, jusqu'à {n,n} qui est impossible.
Donc pour l'instant, on dénombre : (n+1) + (n-1) + (n-2) +... + 1 elements.
Pour ceux à 3 elements, même procédé, au début on aura n-2 + (n-3) +... + 1 elements. En effet, on commence à {1,2,3} jusqu'à {1,2,n} puis {2,3,4} jusqu'à {2,3,n}, puis {3,4,5} jusqu'à {3,4,n} jusqu'à aboutir au {n-2,n-1,n}.
À chaque fois qu'on augmente le nombre d'éléments de 1, on dénombrera 1 élément en moins dans le dénombrement, ce qui est logique.
On pose S1 = n+1 pour le 1er compte, S2 = (n+1) + (n-1)+...+1 = S1 + 1 +... +(n-1).
Puis S3 = S1 + S2 + 1 +... +(n-2). On déduit finalement, que Sn = Card (P(n)) = 2^n par hypothèse de récurrence.
Par conséquent, Card(P(n+1)) = S(n+1) = Sn + S(n-1) +...+S1. Or, on a prouvé que Sn = S(n-1)+...+S1 d'où S(n+1) = 2*Sn = 2^(n+1).
Ou bien, tu as encore plus simple mais c'est le genre d'astuce qui, si tu la trouves, t'énerve. Il s'agit ici, de la somme du nombre de combinaisons sans répétition des éléments de E. Donc, tu peux procéder sans récurrence.
Par exemple, si tu veux trouver le nombre de parties d'un ensembles à 3 éléments, tu as {Ensemble vide}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} = 8 éléments.
Il faut donc : Combinaisons de 1 élément parmi 3 = (1 parmi 3) = 3! / (1!(3-1)!) = 3. Puis, combinaisons de 2 éléments parmi 3, 2 parmi 3 = 3. Et enfin, combinaisons de 3 éléments parmi 3, donc une.
Et on ajoute l'ensemble vide à la fin, qui correspond à 0 éléments parmi 3.
Pour n elements, tu fais la somme (0 parmi n) + (1 parmi n) + (2 parmi n) +... + (n parmi n).
Et miraculeusement, on reconnaît le Binôme de Newton, Somme des k parmi n, pour k allant de 0 à n de (1*1) = Somme des k parmi n, pour k allant de 0 à n de (1^k * 1^(n-k)) = (1+1)^n = 2^n.