Bonjour les kheys, je passe le CCG en maths et j'aimerai votre aide pour cette démonstration :

\[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\]

Pour l'instant j'ai trouvé ça :

\[\binom{n}{k}=\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}\]

Mais je sais pas aller plus loin. Merci d'avance

Et bah ? t'as direct le résultat du coup non?

Le 11 février 2020 à 17:52:48 TheLelouch5 a écrit :
Et bah ? t'as direct le résultat du coup non?

Comment ça ?

Le premier terme c'est le 1er coeff binomial et le 2e c'est le 2e coeff binomial, vu que tu connais la formule de k parmi n avec les factoriels tu devrais les reconnaître non

Le 11 février 2020 à 17:57:12 TheLelouch5 a écrit :
Le premier terme c'est le 1er coeff binomial et le 2e c'est le 2e coeff binomial, vu que tu connais la formule de k parmi n avec les factoriels tu devrais les reconnaître non

Je t'avoue que je ne t'ai bien pas compris .

Tu sais que $ \binom{n}{k}=\frac{n!}{k!(n-k)!} $ non ?

Le 11 février 2020 à 18:06:23 TheLelouch5 a écrit :
Tu sais que $ \binom{n}{k}=\frac{n!}{k!(n-k)!} $ non ?

Oui je sais ça

$\frac{(n-1)!}{k!(n-1-k)!}=\binom{n-1}{k}$ et $\frac{(n-1)!}{(k-1)!(n-k)!}=\binom{n-1}{k-1}$ du coup faut juste remplacer k par k-1 et n par n-1 dans la formule

Le 11 février 2020 à 18:10:24 TheLelouch5 a écrit :
$\frac{(n-1)!}{k!(n-1-k)!}=\binom{k}{n-1}$ et $\frac{(n-1)!}{(k-1)!(n-k)!}=\binom{k-1}{n-1}$ du coup faut juste remplacer k par k-1 et n par n-1 dans la formule

Oui mais moi je suis parti de ce que tu as écrit là.

Donc j'ai trouvé ça :

\[\binom{n-1}{k}+\binom{n-1}{k-1}=\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}\]

Et à la fin je dois trouver ça :

\[\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{n!}{k!(n-k)!}\]

Parce que :
\[\frac{n!}{k!(n-k)!}=\binom{n}{k}\]

Ah ok mais tu as écrit que la somme valait $\binom{n}{k} $ dans ton post de départ en fait
Met au même dénominateur en utilisant n!=n*(n-1)! et ça devrait se simplifier

Le 11 février 2020 à 18:15:47 JRm11111111111 a écrit :

Le 11 février 2020 à 18:10:24 TheLelouch5 a écrit :
$\frac{(n-1)!}{k!(n-1-k)!}=\binom{k}{n-1}$ et $\frac{(n-1)!}{(k-1)!(n-k)!}=\binom{k-1}{n-1}$ du coup faut juste remplacer k par k-1 et n par n-1 dans la formule

Oui mais moi je suis parti de ce que tu as écrit là.

Donc j'ai trouvé ça :

\[\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{n!}{k!(n-k)!}\]

Et à la fin je dois trouver ça :

\[\binom{n-1}{k}+\binom{n-1}{k-1}=\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}\]

Parce que :
\[\frac{n!}{k!(n-k)!}=\binom{n}{k}\]

Le 11 février 2020 à 18:18:03 TheLelouch5 a écrit :
Ah ok mais tu as écrit que la somme valait $\binom{n}{k} $ dans ton post de départ en fait
Le 11 février 2020 à 18:18:03 TheLelouch5 a écrit :
Ah ok mais tu as écrit que la somme valait $\binom{n}{k} $ dans ton post de départ en fait
Met au même dénominateur en utilisant n!=n*(n-1)! et ça devrait se simplifier

Met au même dénominateur en utilisant n!=n*(n-1)! et ça devrait se simplifier

Oui j'aurais du le préciser dsl. Merci pour ton aide et ta patience

Si jamais tu veux une démonstration non calculatoire, (k parmi n) c'est le nombre d'entiers naturels écrits en binaire avec n chiffres dont k 0 et n-k 1 (c'est le nombre de mots à n lettres sur un alphabet à 2 lettres {0,1} tels que le mot contienne k 0 et n-k 1)

À partir de là on comprend bien que pour former un mot à n+1 chiffres binaires dont k+1 0 et n-k 1, il suffit de partir d'un mot binaire à n chiffres dont k 0 et n-k 1 et lui rajouter un 0, ou de partir d'un mot binaire à n chiffres dont k+1 0 et n-k-1 1 et de lui rajouter un 1. Autrement dit, (k + 1 parmi n + 1) = (k parmi n) + (k+1 parmi n).

Un exemple : (2 parmi 4) c'est le nombre de mots binaires à 4 chiffres dont 2 0 et 2 1, autrement dit y a tout ça :

0011
0101
0110
1001
1010
1100

On sépare ce paquet en deux, d'un côté les mots binaires avec un 0 tout à gauche et ceux avec un 1 tout à gauche

0011
0101
0110

1001
1010
1100

en oubliant le chiffre tout à gauche, on retombe sur des mots à 3 lettres ayant soit 2 0 et 1 1 soit 1 0 et 2 1, on retombe sur notre 1 parmi 3 et 2 parmi 3.

Y-a ce type de truc au CG ?

Le 11 février 2020 à 20:16:25 Nathyll a écrit :
Si jamais tu veux une démonstration non calculatoire, (k parmi n) c'est le nombre d'entiers naturels écrits en binaire avec n chiffres dont k 0 et n-k 1 (c'est le nombre de mots à n lettres sur un alphabet à 2 lettres {0,1} tels que le mot contienne k 0 et n-k 1)

À partir de là on comprend bien que pour former un mot à n+1 chiffres binaires dont k+1 0 et n-k 1, il suffit de partir d'un mot binaire à n chiffres dont k 0 et n-k 1 et lui rajouter un 0, ou de partir d'un mot binaire à n chiffres dont k+1 0 et n-k-1 1 et de lui rajouter un 1. Autrement dit, (k + 1 parmi n + 1) = (k parmi n) + (k+1 parmi n).

Un exemple : (2 parmi 4) c'est le nombre de mots binaires à 4 chiffres dont 2 0 et 2 1, autrement dit y a tout ça :

0011
0101
0110
1001
1010
1100

On sépare ce paquet en deux, d'un côté les mots binaires avec un 0 tout à gauche et ceux avec un 1 tout à gauche

0011
0101
0110

1001
1010
1100

en oubliant le chiffre tout à gauche, on retombe sur des mots à 3 lettres ayant soit 2 0 et 1 1 soit 1 0 et 2 1, on retombe sur notre 1 parmi 3 et 2 parmi 3.

Oula . Compliqué mais compréhensible.

Le 11 février 2020 à 21:00:39 Ayfrino a écrit :
Y-a ce type de truc au CG ?

Oui sans doute, j'ai pris une liste d'exos et de leçons sur Internet pour se préparer au CG.

Un tiroir contient n cravates dont n-1 bleues et une rouge.

Choisir k cravates parmi ces n cravates (il y a \binom{n}{k} choix), c'est soit choisir k cravates parmi les n-1 cravates bleues (il y a \binom{n-1}{k} choix), soit choisir la cravate rouge puis k-1 autres cravates parmi les n-1 cravates bleues (il y a \binom{n-1}{k-1} choix), d'où l'égalité \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.

Compréhensible et simple.