Une autre formule impliquant le symbole combinatoire est la suivante, parfois appelée
relation de Pascal.
Relation de Pascal
Pour $k, n \in \mathbb{N}$ avec $0 \leq k < n$, on a
$$C_{n+1}^{k+1} = C_n^k + C_n^{k+1}.$$
Démonstration
On peut à nouveau utiliser le binôme de Newton pour démontrer ce résultat, ou encore le faire à partir de la formule, mais le plus simple est à nouveau de raisonner à partir de la définition combinatoire de $C^k_n$. En effet, $C_{n+1}^{k+1}$ représente le nombre de façons de choisir $k+1$ objets parmi $n+1$. Lors de notre choix, on peut ou non choisir le premier objet. Si on le choisit, alors il nous reste à choisir $k$ autres objets parmi les $n$ objets restants. Si on ne le choisit pas, alors on doit encore choisir nos $k+1$ objets parmi les $n$ autres objets. On a donc directement la formule annoncée.
L'intérêt de cette formule est que l'on peut déduire la valeur des $C^k_{n+1}$ (avec $n$ fixé) directement de la valeur des $C^k_n$. Le triangle de Pascal permet justement de visualiser ce résultat. Sur la $(n+1)^\text{ème}$ ligne de ce triangle, on retrouve les valeurs de $C^0_n, C^1_n, \ldots, C^n_n$. Puisque $C^0_n = C^n_n = 1$, chaque ligne commence et se termine par un $1$.
$$\begin{array}{ccccccccc}
& & & & C^0_0 & & & & \\
& & & C^0_1 & & C^1_1 & & & \\
& & C^0_2 & & C^1_2 & & C^2_2 & & \\
& C^0_3 & & C^1_3 & & C^2_3 & & C^3_3 & \\
\ldots & &\ldots & & \ldots & & \ldots & & \ldots
\end{array}$$ En valeurs, on obtient :
$$\begin{array}{ccccccccccccc}
& & & & & & 1 & & & & & & \\
& & & & & 1 & & 1 & & & & & \\
& & & & 1 & & 2 & & 1 & & & & \\
& & & 1 & & 3 & & 3 & & 1 & & & \\
& & 1 & & 4 & & 6 & & 4 & & 1 & & \\
& 1 & & 5 & & 10 & & 10 & & 5 & & 1 \\
\ldots & & \ldots & & \ldots & & \ldots & & \ldots & & \ldots & & \ldots
\end{array}$$ On peut observer les différents résultats que nous avons jusqu'ici obtenus sur ce triangle de Pascal. Tout d'abord, pour avoir les coefficients du développement de $(x+y)^n$, il suffit de regarder la $(n+1)^\text{ème}$ ligne du triangle. Par exemple, on a
$$(x+y)^4 = x^4 + 4x^3 y + 6 x^2 y^2 + 4 x y^3 + y^4$$ D'autre part, on retrouve aussi les puissances de $2$ en additionnant les éléments d'une même ligne. Enfin, ce triangle est très simple à construire puisqu'on sait que le premier et le dernier élément de chaque ligne vaut $1$ et que chaque élément est égal à la somme des deux éléments situés juste au dessus (car $C_{n+1}^{k+1} = C_n^k + C_n^{k+1}$).
Le triangle de Pascal possède en fait un grand nombre d'autres propriétés. Nous ne les donnons pas toutes, mais le lecteur intéressé pourra facilement trouver des articles consacré à ce fameux triangle. Pour notre part, nous évoquons encore une curiosité : on peut retrouver les nombres de Fibonacci dans le triangle de Pascal ! Il faut pour cela réécrire le triangle sous une forme parfois préférée à la forme précédente :
$$\begin{array}{ccccccc}
1 & & & & & & \\[2mm]
1 & 1 & & & & & \\[2mm]
1 & 2 & 1 & & & & \\[2mm]
1 & 3 & 3 & 1 & & & \\[2mm]
1 & 4 & 6 & 4 & 1 & & \\[2mm]
1 & 5 & 10 & 10 & 5 & 1 & \\[2mm]
1 & 6 & 15 & 20 & 15 & 6 & 1
\end{array}$$ Pour observer les nombres de Fibonacci, il faut calculer la somme des éléments des diagonales de ce triangle. On retrouve alors $\boxed{1}$, $\boxed{1}$, $1+1 = \boxed{2}$, $1+2 = \boxed{3}$, $1+3+1 = \boxed{5}$, $1+4+3 = \boxed{8}$, $1+5+6+1 = \boxed{13}$, ... Rappelons que les nombres de Fibonacci sont définis par
$$\left\{\begin{array}{ll}
F_1 = F_2 = 1 & \\
F_n = F_{n-1} + F_{n-2} & \text{ si } \ n \geq 3
\end{array}\right.$$ Cette observation s'écrit en formules par
Propriété (Fibonacci et Pascal réunis)
Pour $n \in \mathbb{N}$, on a
$$C_n^0 + C_{n-1}^1 + \ldots + C_{\left\lfloor \frac{n+1}{2} \right\rfloor}^{\left\lceil \frac{n-1}{2} \right\rceil} = F_{n+1}.$$
Les notations $\lceil x \rceil$ et $\lfloor x \rfloor$ permettent de ne pas distinguer le cas où $n$ est pair de celui où $n$ est impair, mais cela veut tout simplement dire que
$$C_n^0 + C_{n-1}^1 + \ldots + C_{\left(\frac{n}{2}\right)}^{\left(\frac{n}{2}\right)} = F_{n+1} \quad \text{ si $n$ est pair},$$ $$C_n^0 + C_{n-1}^1 + \ldots + C_{\left(\frac{n+1}{2}\right)}^{\left(\frac{n-1}{2}\right)} = F_{n+1} \quad \text{ si $n$ est impair}.$$
La démonstration de ce résultat se fait par récurrence : on a vu que la formule était correcte pour $n = 1$ et $n = 2$ sur le triangle, et il suffit alors d'utiliser la relation de Pascal pour montrer que si la formule est vérifiée pour $n-2$ et $n-1$, alors elle l'est également pour $n$. Nous ne donnons pas les détails.