$\displaystyle\sum_{i+j=k}\binom{m}{i}\binom{n}{j}=\binom{m+n}{k}$

Dr_Piradian

Bonjour, dans le cadre d'un exercice je dois démontrer $\displaystyle\sum_{i+j=k}\binom{m}{i}\binom{n}{j}=\binom{m+n}{k}$ (et je ne sais même pas à ce stade si cette égalité est vraie).

Je remarque que cette égalité est équivalente à

$\displaystyle\sum_{j=0}^{k}\binom{m}{k-j}\binom{n}{j}=\binom{m+n}{k}$

J'ai tenté un raisonnement par récurrence. Cette égalité est vraie pour $k=0$.

On suppose donc

$\displaystyle\sum_{j=0}^{k}\binom{m}{k-j}\binom{n}{j}=\binom{m+n}{k}$

et on doit démontrer que $\displaystyle\sum_{j=0}^{k+1}\binom{m}{k+1-j}\binom{n}{j}=\binom{m+n}{k+1}$

On a $\displaystyle\sum_{j=0}^{k+1}\binom{m}{k+1-j}\binom{n}{j}=\displaystyle\sum_{j=0}^{k+1}\dfrac{m!}{(k+1-j)(k-j)!(m-k-1+j)!}\times\binom{n}{j}=\displaystyle\sum_{j=0}^{k+1}\binom{m}{k-j}\times\dfrac{m-k+j}{k+j-1}\times\binom{n}{j}$

À partir de là je suis bloqué, je ne sais pas quoi faire.

J'ai donc essayé une autre approche (toujours avec l'hypothèse de récurrence):

$\displaystyle\sum_{j=0}^{k+1}\binom{m}{k+1-j}\binom{n}{j}=\displaystyle\sum_{j=0}^{k+1}((\binom{m-1}{k-j}+\binom{m}{k-j})\binom{n}{j})=\displaystyle\sum_{j=0}^{k+1}\binom{m}{k-j}\binom{n}{j}+\displaystyle\sum_{j=0}^{k+1}\binom{m-1}{k-j}\binom{n}{j}=$

$\binom{m+n}{k}+\binom{m}{-1}\binom{n}{j}+\binom{m+n-1}{k}+\binom{m-1}{-1}\binom{n}{j}$

(je crois que je viens de résoudre en même temps que je tape sur mon écran d'ordinateur, c'était pas prévu).

Est-ce qu'on a le droit d'écrire une notation de la forme $\binom{m}{-1}$ avec un entier négatif si on suppose qu'une telle notation est égale à $0$ ? car si elle est égale à $0$, alors j'ai trouvé le résultat, il est égal à $\binom{m+n}{k+1}$. Et si une telle notation est interdite, comment aurais-je dû m'y prendre ? Merci.

JLapin

Tu peux montrer ton identité très rapidement en examinant le coefficient devant $X^{m+n}$ des polynômes $(X+1)^m(X+1)^n$ et $(X+1)^{m+n}$.

Sinon, oui, on peut généraliser comme tu le proposes les binomiaux. Cela simplifie certaines utilisations de la formule d'addition comme celle que tu proposes.

Dr_Piradian

Merci. En effet ta méthode est plus directe.

GaBuZoMeu

Bonjour,

On a ausi une démonstration combinatoire facile : Soit $E$ un ensemble à $m+n$ éléments, $A$ une partie de $E$ à $m$ éléments.

Se donner une partie de $E$ à $k$ éléments, c'est se donner une partie de $A$ à $i$ éléments avec  $0\leq i\leq k$ et une partie de $E\setminus A$ à $k-i$ éléments.

GTG

Et pour le plaisir, une méthode par diagramme (A. Engel, Stochastik)

Chaurien

C'est l'identité de convolution de Vandermonde. On en a parlé plusieurs fois sur ce forum, mais je n'ai pas envie de chercher...

Pour énoncer cette identité sans trop s'embêter, on pose pour tout $m \in \mathbb N$ et tout $n \in \mathbb N$  : $\binom{m}{n}=\frac 1{n!} m(m-1)...(m-n+1)$, avec bien sûr  $\binom{m}{0}=1$.

On a ainsi   $\binom{m}{n}=0$ si $m \in \mathbb N$  et $n \in \mathbb N$ et $m<n$, et c'est cohérent avec la définition combinatoire de $\binom{m}{n}$.

On peut alors énoncer ainsi l'identité : $\displaystyle\sum_{i=0}^k\binom{m}{i}\binom{n}{k-i}=\binom{m+n}{k}$, et elle est bien définie quels que soient $m,n,k$ entiers naturels, alors que si l'on ne définissait $\binom{m}{n}$ que pour $m \ge n$, cette identité serait déjà bien embêtante à définir, sans parler même de sa démonstration. Noter que dans la somme $\displaystyle\sum_{i=0}^k\binom{m}{i}\binom{n}{k-i}$ des termes peuvent être nuls, peut-être même tous, mais peu importe, l'identité est toujours vraie. Après, on peut toujours déterminer le nombre de termes non nuis de cette somme, selon les valeurs de $m,n,k$ entiers naturels.

Comme il a été dit, il y a trois démonstrations : par récurrence sur $m$ ou $n$, ou fonction génératrice polynomiale, ou combinatoire. la combinatoire pouvant porter sur des tirages ou des trajets sur un quadrillage.

Chaurien

Prolongement. Les coefficients binomiaux peuvent se généraliser. On peut poser pour tout $x \in \mathbb R$ (ou même  $x \in \mathbb C$) et tout $n \in \mathbb N$  : $\binom{x}{n}=\frac 1{n!} x(x-1)...(x-n+1)$, avec bien sûr  $\binom{x}{0}=1$. L'identité de convolution de Vandermonde est encore vraie pour tout $x \in \mathbb R$, tout $y \in \mathbb R$, tout $k\in \mathbb N$   :  $\displaystyle\sum_{i=0}^k\binom{x}{i}\binom{y}{k-i}=\binom{x+y}{k}$,

Mais ici il faut envisager d'autres démonstrations...

On a déjà dit tout ça sur ce forum, il faut retrouver...

Chaurien

J'ai rencontré autrefois G. Th. Guilbaud (1912-2008) dont j'ai gardé le souvenir d'un vieux monsieur plein d'humour. Très intéressé par les phénomènes d’approximation, il a laissé un livre très original : leçons d'à peu près, Christian Bourgois 1985, dont la couverture s'orne d'un beau pied à coulisse.

Math Coss

Une note de lecture : https://www.persee.fr/doc/mots_0243-6450_1986_num_13_1_1318.
Pourquoi parles-tu de Georges Th. Guilbaud ici, @Chaurien ?

GTG

@Math Coss Chaurien a eu ce mot sympthatique parce qu'il a vu ma signature au bas de mes messages, où il est question de Guilbaud. Je pense qu'il n'a pas vu que c'était une signature. Je lui ai répondu en privé.

Foys

Chaurien a dit :

L'identité de convolution de Vandermonde est encore vraie pour tout $x \in \mathbb R$, tout $y \in \mathbb R$, tout $k\in \mathbb N$   :  $\displaystyle\sum_{i=0}^k\binom{x}{i}\binom{y}{k-i}=\binom{x+y}{k}$,

Mais ici il faut envisager d'autres démonstrations...

On a déjà dit tout ça sur ce forum, il faut retrouver...

Soit $A$ un anneau intègre. A l'aide d'une récurrence sur l'entier $n$, on montre que pour $n$-uplet de parties infinies $(I_1,...,I_n)$ de $A$ et tout polynôme $F\in A[X_1,...,X_n]$, si pour tout $v \in \prod_{k=1}^n I_k$, $F(v_1,...,v_n) = 0$, alors $F=0$ (songer que $A[X_1,...,X_n]$ est isomorphe à $A[X_1,...,X_{n-1}][X_n]$ lorsque $n \geq 1$).

Lorsque $A$ est un corps de caractéristique nulle le résultat précédent s'applique pour tout entier $k$ au polynôme $F(X,Y):=\binom{X+Y}{k} - \sum_{i=0}^k \binom {X}{i} \binom {Y}{k-i}$ qui s'annule sur $\N^2$ (edit: plutôt sur $\{n \mid n \in \N, n \geq k\}^2$ mais cela est suffisant: c'est démontré dans le présent fil).

Chaurien

• La formule de Vandermonde générale peut se démontrer comme dit @Foys par une considération de « densité algébrique ». Si l'on veut juste le résultat sans généraliser, on peut se ramener au résultat connu pour les polynômes à une variable et procéder en deux temps. Pour $n$ et $k$ entiers naturels donnés, la fonction $x  \mapsto F_{n,k}(x)=\binom{x+n}{k}-\sum_{i=0}^k\binom{x}{i}\binom{n}{k-i}$, de $\mathbb R$ dans $\mathbb R$ (ou de $\mathbb C$ dans $\mathbb C$) est une fonction-polynôme qui s'annule sur $\mathbb N$, donc qui est nulle. Ensuite, rebelote pour la seconde variable.

• J'en avais parlé dans une discussion sur la récurrence 

https://les-mathematiques.net/vanilla/discussion/comment/1378710/#Comment_1378710

• Il y a une autre démonstration, avec la fonction génératrice de $\binom{\alpha}{n}$, série entière ou développement limité, en corollaire de $(1+x)^{\alpha}$ $(1+x)^{\beta}$ $=(1+x)^{\alpha+\beta}$.

• Dans la discussion susdite, j'ai donné une troisième démonstration, fondée sur la formule $\displaystyle (x+y)_{p}=\overset{p}{\underset{k=0}{\sum }}(_{k}^{p})(x)_{k}(y)_{p-k}$, où $x \in \mathbb R$, $y \in \mathbb R$, $p \in \mathbb N$, Avec par définition : $(x)_{p}=x(x-1)...(x-p+1)$ (notamment $(x)_0=1$).

• Je rappelle aussi la formule que mon regretté collègue Jean-Louis Roque (1949-2022) appelait de Ednomrednav (en zorglangue), pour $m \in \mathbb N$, $n \in \mathbb N$, $p \in \mathbb N$  : $\displaystyle \overset{m}{\underset{k=0}{\sum }}(_{n}^{k})(_{~~~p}^{m-k})=(_{...}^{...})$. Je vous laisse trouver la valeur de cette somme.

Bonne journée.

Fr. Ch.

Chaurien

Dans la formule de Vandermonde « à l'envers » $\displaystyle \overset{m}{\underset{k=0}{\sum }}(_{n}^{k})(_{~~~~p}^{m-k})=(_{...}^{...})$, on s'attendrait à ce que le résultat soit  $(_{n+p}^{~~m})$, par analogie avec Vandermonde « à l'endroit ». En fait, c'est presque ça, mais pas tout à fait. Cette formule est utile notamment dans des calculs d'espérance et variance de certaines variables aléatoires discrètes. J'aimerais avoir des références pour cette formule, je ne me souviens plus où j'ai pu la trouver.

incognito

Je propose la formule :

$$\sum_{k=0}^m \binom kn \binom{m-k}p = \binom{m+1}{n+p+1}$$

Si on connaît le formule alors on peut la démontrer par récurrence sur $m$ avec la formule du triangle de Pascal.

Sinon on peut faire le raisonnement de combinatoire suivant : si $k$ désigne un entier entre $0$ et $m$, combien y-a-t'il de $(n+p+1)$ listes strictement croissantes d'entiers de l'intervalle d'entiers $[1;m+1]$  dont le $n+1$-ième élément est $k+1$ ?

On peut également obtenir cette formule à partir de la fraction $\dfrac1{1-X}$ et son développement en série formelle, par des considérations sur ses dérivées.

jandri

Cette dernière formule peut se déduire de la formule de Vandermonde (généralisée comme l'a expliqué Chaurien)  pour $x,y$ réels  : $$\displaystyle\sum_{k=0}^n\binom{x}{k}\binom{y}{n-k}=\binom{x+y}{n}$$
Puisque $(-1)^k\dbinom{x}{k}=\dbinom{-x+k-1}{k}$ on peut encore l'écrire : $\displaystyle\sum_{k=0}^n\binom{-x+k-1}{k}\binom{-y+n-k-1}{n-k}=\binom{-x-y+n-1}{n}$.

Si $p=-x-1\in\N$ et $q=-y-1\in\N$ on la réécrit : $\displaystyle\sum_{k=0}^n\binom{p+k}{p}\binom{q+n-k}{q}=\binom{p+q+n+1}{p+q+1}$.

Enfin en posant $m=p+q+n$ et $k'=p+k$ on obtient $\displaystyle\sum_{k'=p}^{m-q}\binom{k'}{p}\binom{m-k'}{q}=\binom{m+1}{p+q+1}$