Binôme de Newton et coefficients binomiaux

(i) Les trois premières assertions se démontrent par récurrence sur $n$, à partir de la relation de Pascal ; pour $n = 0$, ce sont les valeurs $\binom 00 = 1$ et $\binom 0k = 0$ pour $k \geqslant 1$. Au rang $n + 1$, si $k > n + 1$, alors $k - 1 > n$ et $\binom{n+1}{k} = \binom n{k-1} + \binom nk = 0 + 0$ ; puis $\binom{n+1}{n+1} = \binom nn + \binom n{n+1} = 1 + 0$, et $\binom{n+1}1 = \binom n0 + \binom n1 = 1 + n$.

Pour la dernière, raisonnons aussi par récurrence sur $n$. Si $n = 0$, les deux membres valent $1$ pour $k = 0$ et $0$ pour $k \geqslant 1$. Supposons-la vraie au rang $n$ pour tout $k$. Pour $k = 0$, les deux membres de l'égalité au rang $n + 1$ valent $n + 2$. Pour $k \geqslant 1$, la relation de Pascal et l'hypothèse, appliquée en $k$ et en $k - 1$, donnent $$\begin{aligned} &(k + 1)\binom{n+2}{k+1} \\ &= \binom{n+1}k + k\binom{n+1}k \\ &\quad + (k + 1)\binom{n+1}{k+1} \\ &= \binom{n+1}k + (n + 1)\binom n{k-1} \\ &\quad + (n + 1)\binom nk \\ &= (n + 2)\binom{n+1}k. \end{aligned}$$

(ii) Par récurrence sur $n$, le cas $n = 0$ étant clair. En développant $(a + b)^{n+1} = (a + b)^n\,(a + b)$ par la distributivité étendue aux sommes finies et la commutativité, avec $a^ka = a^{k+1}$ et $b^{n-k}b = b^{n+1-k}$ (Sommes finies, (v) et (vi)), $$\begin{aligned} (a + b)^{n+1} &= \sum_{k=0}^n \binom nk a^{k+1}b^{n-k} \\ &\quad + \sum_{k=0}^n \binom nk a^kb^{n+1-k}. \end{aligned}$$ Après le changement d'indice $k + 1 \mapsto k$ dans la première somme, le coefficient de $a^kb^{n+1-k}$ est $$\binom n{k-1} + \binom nk = \binom{n+1}k$$ pour $1 \leqslant k \leqslant n$, et $1$ pour $k = 0$ et $k = n + 1$ ; on a utilisé $u \cdot x + v \cdot x = (u + v) \cdot x$ pour les multiples (Anneau A[X]).

(iii) Par (i), $k\binom pk = p\binom{p-1}{k-1}$, donc $p$ divise $k\binom pk$. Comme $0 < k < p$, $p$ ne divise pas $k$, et le lemme d'Euclide (Nombres premiers, (i)) donne $p \mid \binom pk$.

(iv) Pour $0 < k < p$, écrivons $\binom pk = pu$ ; alors $\binom pk \cdot x = u \cdot \big((p \cdot 1)\,x\big) = 0$ pour tout $x \in A$. Les termes intermédiaires de (ii) disparaissent, et $(a + b)^p = a^p + b^p$.

Par récurrence, $$\begin{aligned} (a + b)^{p^{r+1}} &= \big(a^{p^r} + b^{p^r}\big)^p \\ &= a^{p^{r+1}} + b^{p^{r+1}}. \end{aligned}$$ Enfin $(ab)^p = a^pb^p$ par commutativité, et $1^p = 1$.

(v) Par récurrence sur $n$. Un ensemble vide n'a qu'une partie, $\varnothing$, à $0$ élément, et $\binom 00 = 1$, $\binom 0k = 0$ pour $k \geqslant 1$.

Pour un ensemble fini $B$ et $b \notin B$, l'ensemble $B \cup \{b\}$ est fini, avec $|B \cup \{b\}| = |B| + 1$ : on prolonge une bijection de $|B|$ sur $B$ en envoyant $|B|$ sur $b$, et l'on conclut par l'unicité du nombre d'éléments (Ensembles finis, (ii)). Par récurrence sur $|Y|$, la réunion de deux ensembles finis disjoints $X$ et $Y$ est donc finie, avec $|X \cup Y| = |X| + |Y|$.

Soit $E$ à $n + 1$ éléments, $a \in E$ et $E' = E \setminus \{a\}$, qui est fini (Ensembles finis, (iii)) ; comme $|E'| + 1 = |E| = n + 1$ par ce qui précède, il a $n$ éléments, par simplification (Propriétés des opérations, (i)). La seule partie à $0$ élément est $\varnothing$, et $\binom{n+1}0 = 1$.

Les parties de $E$ à $k + 1$ éléments se répartissent en deux familles disjointes : celles qui ne contiennent pas $a$, qui sont les parties de $E'$ à $k + 1$ éléments, au nombre de $\binom n{k+1}$ par hypothèse de récurrence ; et celles qui contiennent $a$, que $B \mapsto B \setminus \{a\}$ met en bijection avec les parties de $E'$ à $k$ éléments, au nombre de $\binom nk$.

Le nombre d'éléments de la réunion de ces deux familles disjointes étant la somme de leurs nombres d'éléments, par le premier paragraphe, on obtient $\binom nk + \binom n{k+1} = \binom{n+1}{k+1}$ par la relation de Pascal.