Sommation/Formule du binôme

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Lemme préliminaire

Nous aurons besoin pour la démonstration de la formule du binôme du lemme suivant sur les coefficients binomiaux :

Début d'un lemme

Formule de Pascal

${n \choose k-1}+{n \choose k}={n+1 \choose k}$

Fin du lemme

Démonstration de la formule de Pascal On a : ${\begin{aligned}{n \choose k-1}+{n \choose k}&={\frac {n!}{(k-1)!\;(n-k+1)!}}+{\frac {n!}{k!\;(n-k)!}}\\&={\frac {n!\;k}{k!\;(n-k+1)!}}+{\frac {n!\;(n-k+1)}{k!\;(n-k+1)!}}\\&={\frac {n!\;(k+n-k+1)}{k!\;(n-k+1)!}}\\&={\frac {n!\;(n+1)}{k!\;(n+1-k)!}}\\&={\frac {(n+1)!}{k!\;(n+1-k)!}}\\&={n+1 \choose k}.\end{aligned}}$ Voir aussi la démonstration combinatoire (chap. 1) de la formule de Vandermonde ${\binom {n+m}{r}}=\sum _{k}{\binom {n}{k}}{\binom {m}{r-k}}$, dont la formule de Pascal est le cas particulier $m=1$.

Démonstration de la formule du binôme

Tout le monde connaît bien la formule :

$(a+b)^{2}=a^{2}+2ab+b^{2}$

Et probablement aussi la formule :

$(a+b)^{3}=a^{3}+3a^{2}b+3ab^{2}+b^{3}$

Ces deux formules sont des cas particuliers d'une formule plus générale appelée formule du binôme que l’on énonce ainsi :

Début d’un théorème

Formule du binôme

Soient, dans un anneau, deux éléments $a$ et $b$ tels que $ab=ba$ (par exemple : deux nombres complexes).

Pour tout entier naturel $n$, nous avons :

$(a+b)^{n}=\sum _{k=0}^{n}{n \choose k}a^{k}b^{n-k}$

Fin du théorème

Début d'une démonstration

Démonstration

Au premier rang, on a bien :

$(x+y)^{0}=1={0 \choose 0}x^{0}y^{0}$.

Pour n entier supérieur ou égal à 1, nous démontrerons la formule du binôme par récurrence. (On a traité à part le cas n = 0 car au cours de la démonstration ci-dessous apparaîtront des sommes de la forme $\sum _{k=1}^{n}\dots$, qui n'auraient pas de sens dans ce cas. Un autre démonstration par récurrence, consistant à intégrer au lieu de multiplier — cf. exercice 4-9 — évite cet écueil.)

Initialisation

Au premier rang, on a bien :

$(x+y)^{1}=x+y={1 \choose 0}x^{1}y^{0}+{1 \choose 1}x^{0}y^{1}$.

Caractère héréditaire

Soit n un entier supérieur ou égal à 1 tel que l'hypothèse de récurrence soit vraie, montrons que la relation est vraie aussi pour n + 1 :

Par hypothèse de récurrence :

$(x+y)^{n+1}=(x+y)~\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}.$

Par distributivité de la multiplication par rapport à l'addition :

$(x+y)^{n+1}=x^{n+1}+x~\sum _{k=1}^{n}{n \choose k}x^{n-k}y^{k}+y~\sum _{k=0}^{n-1}{n \choose k}x^{n-k}y^{k}+y^{n+1}.$

Par factorisation :

$(x+y)^{n+1}=x^{n+1}+\sum _{k=1}^{n}\left\lbrack {n \choose k}+{n \choose {k-1}}\right\rbrack x^{n-k+1}y^{k}+y^{n+1}.$

En utilisant la formule de Pascal :

${\begin{aligned}(x+y)^{n+1}&=x^{n+1}+\sum _{k=1}^{n}{{n+1} \choose k}~x^{n-k+1}y^{k}+y^{n+1}\\&=\sum _{k=0}^{n+1}{{n+1} \choose k}~x^{n-k+1}y^{k},\end{aligned}}$

le principe de récurrence termine alors la démonstration.

Fin de la démonstration

Remarque Comme l’objet de notre propos est de réaliser des sommations, il est nécessaire de bien connaître la formule du binôme dans les deux sens. Il est donc recommandé de bien la connaître aussi sous la forme : $\sum _{k=0}^{n}{n \choose k}a^{k}b^{n-k}=(a+b)^{n}$

Triangle de Pascal

On peut commodément représenter sous forme de tableau triangulaire la valeur des $\textstyle {n \choose p}$. Sur le tableau ci-contre, à l'intersection de la ligne n et de la colonne p, nous avons la valeur numérique de $\textstyle {n \choose p}$. Ce tableau, appelé triangle de Pascal, donne les coefficients du développement d'une expression de la forme (a + b)ⁿ. Supposons que l’on veuille, par exemple, calculer (a + b)⁵. En utilisant la ligne correspondant à n = 5, nous voyons que nous obtenons :

$(a+b)^{5}=a^{5}+5a^{4}b+10a^{3}b^{2}+10a^{2}b^{3}+5ab^{4}+b^{5}$

Généralement, les lignes et les colonnes ne sont pas représentées et nous avons simplement le tableau ci-contre à gauche. C'est à nous d'imaginer mentalement quelle est la valeur de n et de p. Il suffit de remarquer que la valeur de n est la première valeur différente de 1 que l’on trouve sur la ligne et cette première valeur différente de 1 correspond à la colonne p = 1.

Pour construire ce triangle, nous utilisons la formule de Pascal qui se traduit par le fait que chaque nombre du triangle est la somme des deux nombres qui sont immédiatement dessus. Voir l'animation à droite.

Pour plus de détails, voir l'article « Triangle de Pascal » sur Wikipédia.

Puissances impaires et carrés

Pour $n=2m+1$ , les termes peuvent se regrouper et étonnamment faire apparaître des carrés

Début d'un lemme

Formules des puissances impaires $n=2m+1$

$(x-y)^{n}=xf(x,y)^{2}-yf(y,x)^{2},~~~~~f(x,y)=\sum _{k=0}^{m}{n \choose 2k}x^{m-k}y^{k}$

Fin du lemme

Exemples dans l'anneau $\mathbb {Z}$:

$${\begin{array}{lll}17^{3}&=(5+12)^{3}=5\times 31^{2}&+12\times 3^{2}\\17^{5}&=(5+12)^{5}=5\times 145^{2}&+12\times 331^{2}\\17^{7}&=(5+12)^{7}=5\times 6929^{2}&+12\times 3767^{2}\\17^{9}&=(5+12)^{9}=5\times 138911^{2}&+12\times 42921^{2}\end{array}}$$

Début d'une démonstration

Démonstration

En séparant les termes pairs et impairs dans la formule du binôme :

$$(x-y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}(-y)^{k}=\sum _{k=0}^{m}{n \choose 2k}x^{2m+1-2k}y^{2k}-\sum _{k=0}^{m}{n \choose 2k+1}x^{2m-2k}y^{2k+1}$$

$$(x-y)^{n}=x\sum _{k=0}^{m}{n \choose 2k}x^{2m-2k}y^{2k}-y\sum _{k=0}^{m}{n \choose 2k+1}x^{2m-2k}y^{2k}$$

Par symétrie du coefficient binomial :

$$(x-y)^{n}=xf(x^{2},y^{2})-yf(y^{2},x^{2}),f(x,y)=\sum _{k=0}^{m}{n \choose 2k}x^{m-k}y^{k}$$

qu'on peut également écrire en prenant $-y$

$$(x+y)^{n}=xf(x^{2},y^{2})+yf(y^{2},x^{2})$$

En multipliant les deux dernières expressions, on obtient :

$$(x^{2}-y^{2})^{n}=x^{2}f(x^{2},y^{2})^{2}-y^{2}f(y^{2},x^{2})^{2}$$

D'où la formule en substituant $(x,y)$ à $(x^{2},y^{2})$ .

Fin de la démonstration

Comme on peut le remarquer dans l'exemple, on a en plus le résultat général suivant:

$$x\wedge 2y=1\Rightarrow f(x,2y)\wedge f(2y,x)=1$$

Début d'une démonstration

Démonstration

Soient $(x,y)$ deux entiers de parité différentes.

Dans ce cas, $f(x,y)$ et $f(y,x)$ sont impairs. Considérons $p$ un diviseur premier impair commun. On a donc $f(x,y)\equiv f(y,x)\equiv 0~[p]$ . La formule des carrés implique alors $x\equiv y~[p]$

En réinjectant dans la définition de $f$, on obtient:

$f(x,y)\equiv \sum _{k=0}^{m}{n \choose 2k}x^{m-k}x^{k}\equiv x^{m}\sum _{k=0}^{m}{n \choose 2k}\equiv x^{m}2^{m-1}~[p]$

Par conséquent $f(x,y)\equiv 0\Rightarrow x\equiv 0~[p]$. Même résultat pour $y$

Ainsi tout diviseur premier commun à $f(x,y)$ et $f(y,x)$ divise aussi $x$ et $y$.

Fin de la démonstration

Enfin, on peut aussi donner une condition de coprimalité entre $x$ et $f(x,y)$:

$$x\wedge ny=1\Rightarrow x\wedge f(x,y)=1$$

Début d'une démonstration

Démonstration

En reprenant la définition, $f(x,y)$ s'écrit sous la forme $f(x,y)=ny^{m}+xP(x,y)$ . Si $x\wedge ny^{m}=1$, alors $x\wedge f(x,y)=1$, le pgcd étant conservé par ajout de multiples de $x$

Fin de la démonstration