Récurrence et dénombrement : cours de maths en L1 en PDF.

L’ensemble \(\mathbb{N}\) vérifie les trois propriétés suivantes.

• Toute partie non vide de \(\mathbb{N}\) possède un plus petit élément : c’est la propriété du bon ordre.
• Toute partie non vide et majorée de \(\mathbb{N}\) possède un plus grand élément.
• L’ensemble \(\mathbb{N}\) n’est pas majoré.

Montrons la deuxième propriété à partir du bon ordre. Soit \(A\) une partie non vide de \(\mathbb{N}\) majorée par un entier \(M\). L’ensemble \(B\) des majorants de \(A\) dans \(\mathbb{N}\) contient \(M\), donc il est non vide. Par le bon ordre, \(B\) admet un plus petit élément \(b\). Si \(b = 0\), alors \(A = \{0\}\) et le résultat est clair. Sinon, \(b-1\) n’est pas un majorant de \(A\) : il existe donc \(a \in A\) avec \(a > b-1\), c’est-à-dire \(a \geq\, b\). Comme \(a \leq\, b\), on obtient \(a = b\). Ainsi \(b\) appartient à \(A\) et le majore : c’est son plus grand élément.

Il n’existe pas de suite \((u_n)\) d’entiers naturels strictement décroissante. En effet, l’ensemble \(\{u_n,\ n \in \mathbb{N}\}\) est une partie non vide de \(\mathbb{N}\). Il a donc un plus petit élément \(u_p\). Or \(u_{p+1} < u_p\), ce qui contredit la minimalité. Ce principe s’appelle la descente infinie.

Soit \(n_0 \in \mathbb{N}\) et \(\mathcal{P}(n)\) une propriété définie pour \(n \geq\, n_0\). On suppose :

• (initialisation) \(\mathcal{P}(n_0)\) est vraie ;
• (hérédité) pour tout \(n \geq\, n_0\), \(\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)\).

Alors \(\mathcal{P}(n)\) est vraie pour tout entier \(n \geq\, n_0\).

Raisonnons par l’absurde. Supposons que l’ensemble \(F = \{n \geq\, n_0 : \mathcal{P}(n) \text{ fausse}\}\) soit non vide. Par le bon ordre, il possède un plus petit élément \(m\). D’abord, \(m \neq n_0\) car \(\mathcal{P}(n_0)\) est vraie. Donc \(m – 1 \geq\, n_0\), et \(m-1 \notin F\) par minimalité de \(m\). Ainsi \(\mathcal{P}(m-1)\) est vraie. Par hérédité, \(\mathcal{P}(m)\) est vraie, ce qui contredit \(m \in F\). Finalement, \(F\) est vide.

Pour rédiger une récurrence correctement :

• énoncez la propriété \(\mathcal{P}(n)\) avec précision, en fixant \(n\) ;
• vérifiez l’initialisation par un calcul explicite ;
• pour l’hérédité, fixez un entier \(n \geq\, n_0\), supposez \(\mathcal{P}(n)\), puis démontrez \(\mathcal{P}(n+1)\) ;
• concluez en citant le principe de récurrence.

N’écrivez jamais « supposons \(\mathcal{P}(n)\) vraie pour tout \(n\) » : c’est justement ce qu’il faut démontrer.

Montrons que \(2^n \geq\, n+1\) pour tout \(n \in \mathbb{N}\). Pour \(n = 0\), on a \(2^0 = 1 \geq\, 1\). Soit ensuite \(n \in \mathbb{N}\) tel que \(2^n \geq\, n+1\). Alors \(2^{n+1} = 2 \cdot 2^n \geq\, 2n + 2 \geq\, n + 2\). La propriété est donc héréditaire. Par récurrence, elle est vraie pour tout \(n\).

Les deux étapes sont indispensables. Par exemple, la propriété « \(9\) divise \(10^n + 1\) » est héréditaire, car \(10^{n+1} + 1 = 10(10^n+1) – 9\). Pourtant, elle n’est jamais vraie : \(10^n + 1\) a pour reste \(2\) dans la division par \(9\).

(Récurrence double) Si \(\mathcal{P}(n_0)\) et \(\mathcal{P}(n_0+1)\) sont vraies et si, pour tout \(n \geq\, n_0\), \(\big(\mathcal{P}(n) \text{ et } \mathcal{P}(n+1)\big) \Rightarrow \mathcal{P}(n+2)\), alors \(\mathcal{P}(n)\) est vraie pour tout \(n \geq\, n_0\).

(Récurrence forte) Si \(\mathcal{P}(n_0)\) est vraie et si, pour tout \(n \geq\, n_0\), la validité de \(\mathcal{P}(n_0), \ldots, \mathcal{P}(n)\) entraîne celle de \(\mathcal{P}(n+1)\), alors \(\mathcal{P}(n)\) est vraie pour tout \(n \geq\, n_0\).

Les deux énoncés se ramènent à une récurrence simple. Pour la récurrence forte, posons \(\mathcal{Q}(n)\) : « \(\mathcal{P}(k)\) est vraie pour tout \(k \in [\![n_0, n]\!]\) ». D’abord, \(\mathcal{Q}(n_0)\) équivaut à \(\mathcal{P}(n_0)\). Ensuite, si \(\mathcal{Q}(n)\) est vraie, l’hypothèse donne \(\mathcal{P}(n+1)\), donc \(\mathcal{Q}(n+1)\). Ainsi \(\mathcal{Q}(n)\) est vraie pour tout \(n\), et a fortiori \(\mathcal{P}(n)\). Pour la récurrence double, on applique le même argument à \(\mathcal{Q}(n)\) : « \(\mathcal{P}(n)\) et \(\mathcal{P}(n+1)\) ».

Tout entier \(n \geq\, 2\) est un produit de nombres premiers. En effet, \(2\) est premier. Soit \(n \geq\, 2\) tel que tous les entiers de \([\![2, n]\!]\) soient des produits de nombres premiers. Si \(n+1\) est premier, c’est terminé. Sinon, \(n + 1 = ab\) avec \(2 \leq\, a, b \leq\, n\). Par hypothèse de récurrence forte, \(a\) et \(b\) sont des produits de nombres premiers, donc \(n+1\) aussi.

Soit \(m \leq\, n\) deux entiers et \(a_m, \ldots, a_n\) des nombres réels ou complexes. On note

\[\sum_{k=m}^{n} a_k = a_m + a_{m+1} + \cdots + a_n \quad \text{et} \quad \prod_{k=m}^{n} a_k = a_m \times a_{m+1} \times \cdots \times a_n.\]

Si \(m > n\), la somme vide vaut \(0\) et le produit vide vaut \(1\). L’indice \(k\) est muet : on peut le renommer sans rien changer.

Pour des nombres \(a_k\), \(b_k\) et des scalaires \(\lambda\), \(\mu\) :

• linéarité : \(\sum_{k=m}^{n} (\lambda a_k + \mu b_k) = \lambda \sum_{k=m}^{n} a_k + \mu \sum_{k=m}^{n} b_k\) ;
• relation de Chasles : \(\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k\) pour \(m \leq\, p < n\) ;
• somme d’une constante : \(\sum_{k=m}^{n} c = (n – m + 1)\, c\) ;
• produit : \(\prod_{k=m}^{n} (a_k b_k) = \prod_{k=m}^{n} a_k \prod_{k=m}^{n} b_k\) et \(\prod_{k=m}^{n} \lambda = \lambda^{n-m+1}\).

En général, \(\sum a_k b_k \neq \sum a_k \sum b_k\) et \(\prod (a_k + b_k) \neq \prod a_k + \prod b_k\). De même, \(\prod_{k=1}^{n} (\lambda a_k) = \lambda^n \prod_{k=1}^{n} a_k\), et non \(\lambda \prod a_k\).

\[\sum_{k=m}^{n} a_{k+p} = \sum_{j=m+p}^{n+p} a_j \qquad \text{et} \qquad \sum_{k=0}^{n} a_{n-k} = \sum_{j=0}^{n} a_j.\]

Calculons \(S_n = \sum_{k=0}^{n} k\) par retournement. On a aussi \(S_n = \sum_{k=0}^{n} (n – k)\). En additionnant, \(2S_n = \sum_{k=0}^{n} n = n(n+1)\). Donc \(S_n = \dfrac{n(n+1)}{2}\). La figure ci-dessous traduit ce calcul : deux escaliers identiques forment un rectangle de \(n \times (n+1)\) cases.

Pour tous nombres \(u_m, \ldots, u_{n+1}\), on a \(\sum_{k=m}^{n} (u_{k+1} – u_k) = u_{n+1} – u_m\). De même, si les \(u_k\) sont non nuls, \(\prod_{k=m}^{n} \dfrac{u_{k+1}}{u_k} = \dfrac{u_{n+1}}{u_m}\).

Par linéarité et translation d’indice, \(\sum_{k=m}^{n} u_{k+1} – \sum_{k=m}^{n} u_k = \sum_{j=m+1}^{n+1} u_j – \sum_{k=m}^{n} u_k\). Les termes d’indice \(m+1\) à \(n\) se simplifient. Il reste donc \(u_{n+1} – u_m\). Le cas du produit est identique.

Pour calculer une somme par télescopage, cherchez à écrire le terme général sous la forme \(u_{k+1} – u_k\). Les outils usuels sont la décomposition en éléments simples, par exemple \(\dfrac{1}{k(k+1)} = \dfrac{1}{k} – \dfrac{1}{k+1}\), et les identités du type \(k \cdot k! = (k+1)! – k!\).

\(\sum_{k=1}^{n} \dfrac{1}{k(k+1)} = \sum_{k=1}^{n} (\dfrac{1}{k} – \dfrac{1}{k+1}) = 1 – \dfrac{1}{n+1} = \dfrac{n}{n+1}\).

Pour tout \(n \in \mathbb{N}\) et tout nombre complexe \(q \neq 1\) :

\[\sum_{k=1}^{n} k = \frac{n(n+1)}{2}, \qquad \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}, \qquad \sum_{k=0}^{n} q^k = \frac{1 – q^{n+1}}{1 – q}.\]

Plus généralement, \(a^{n+1} – b^{n+1} = (a – b) \sum_{k=0}^{n} a^k b^{n-k}\).

Pour la somme géométrique, \((1 – q)\sum_{k=0}^{n} q^k = \sum_{k=0}^{n} (q^k – q^{k+1}) = 1 – q^{n+1}\) par télescopage. Pour les carrés, on télescope \((k+1)^3 – k^3 = 3k^2 + 3k + 1\) de \(k = 1\) à \(n\). On obtient \((n+1)^3 – 1 = 3\sum k^2 + \dfrac{3n(n+1)}{2} + n\). Il reste ensuite à isoler \(\sum k^2\) et à factoriser par \(n+1\).

S’il existe une injection de \([\![1, n]\!]\) dans \([\![1, p]\!]\), alors \(n \leq\, p\). En particulier, s’il existe une bijection entre ces deux ensembles, alors \(n = p\).

On raisonne par récurrence sur \(n\). Le cas \(n = 0\) est clair. Supposons le résultat vrai au rang \(n\), et soit \(f\) injective de \([\![1, n+1]\!]\) dans \([\![1, p]\!]\). Alors \(p \geq\, 1\). Soit \(\tau\) la transposition de \([\![1, p]\!]\) qui échange \(f(n+1)\) et \(p\). L’application \(\tau \circ f\) est injective et envoie \(n+1\) sur \(p\). Sa restriction à \([\![1, n]\!]\) est donc une injection dans \([\![1, p-1]\!]\). Par hypothèse de récurrence, \(n \leq\, p – 1\), donc \(n + 1 \leq\, p\).

Un ensemble \(E\) est fini s’il existe \(n \in \mathbb{N}\) et une bijection de \([\![1, n]\!]\) sur \(E\). D’après le lemme, cet entier \(n\) est unique : c’est le cardinal de \(E\), noté \(|E|\), \(\operatorname{Card} E\) ou \(\# E\).

Soit \(E\) et \(F\) deux ensembles finis.

• Toute partie \(A\) de \(E\) est finie et \(|A| \leq\, |E|\), avec égalité si et seulement si \(A = E\).
• Il existe une bijection de \(E\) sur \(F\) si et seulement si \(|E| = |F|\).
• Si \(|E| = |F|\), une application de \(E\) dans \(F\) est injective si et seulement si elle est surjective, si et seulement si elle est bijective.

Soit \(A\), \(B\) deux parties finies d’un ensemble \(E\), et \(F\) un ensemble fini.

• Si \(A \cap B = \varnothing\), alors \(|A \cup B| = |A| + |B|\).
• Dans tous les cas, \(|A \cup B| = |A| + |B| – |A \cap B|\), et \(|E \setminus A| = |E| – |A|\) si \(E\) est fini.
• \(|A \times F| = |A| \times |F|\).
• \(|\mathcal{P}(A)| = 2^{|A|}\).

Si \(a = |A|\) et \(b = |B|\) avec \(A \cap B = \varnothing\), on recolle une bijection \(\varphi : [\![1, a]\!] \to A\) et une bijection \(\psi : [\![1, b]\!] \to B\). L’application qui envoie \(k \leq\, a\) sur \(\varphi(k)\) et \(k > a\) sur \(\psi(k – a)\) est une bijection de \([\![1, a+b]\!]\) sur \(A \cup B\). Ensuite, \(A \cup B\) est la réunion disjointe de \(A\) et de \(B \setminus A\), et \(B\) celle de \(A \cap B\) et de \(B \setminus A\). On en déduit la formule générale. Pour le produit, \(A \times F\) est la réunion disjointe des \(\{x\} \times F\), qui ont chacun \(|F|\) éléments. Enfin, l’application \(X \mapsto \mathbf{1}_X\) est une bijection de \(\mathcal{P}(A)\) sur l’ensemble des applications de \(A\) dans \(\{0, 1\}\), qui en compte \(2^{|A|}\) d’après la partie suivante.

Pour trois parties, la même idée donne la formule du crible : \(|A \cup B \cup C| = |A| + |B| + |C| – |A \cap B| – |A \cap C| – |B \cap C| + |A \cap B \cap C|\).

Soit \(E\) un ensemble à \(n\) éléments et \(p \in \mathbb{N}\). Une \(p\)-liste de \(E\) est un élément de \(E^p\), c’est-à-dire une suite ordonnée \((x_1, \ldots, x_p)\). Un arrangement est une \(p\)-liste d’éléments deux à deux distincts. Une permutation de \(E\) est une bijection de \(E\) sur lui-même.

• Le nombre de \(p\)-listes de \(E\) vaut \(n^p\). Ainsi, il y a \(|F|^{|E|}\) applications de \(E\) dans \(F\).
• Pour \(p \leq\, n\), le nombre d’arrangements de \(p\) éléments de \(E\) vaut \(A_n^p = n(n-1)\cdots(n-p+1) = \dfrac{n!}{(n-p)!}\). Si \(p > n\), il vaut \(0\).
• Le nombre de permutations de \(E\) vaut \(n!\).

Le premier point découle de \(|E^p| = |E|^p\), obtenu par récurrence sur \(p\) grâce au cardinal d’un produit. Pour les arrangements, raisonnons par récurrence sur \(p\). On regroupe les arrangements de longueur \(p+1\) selon leurs \(p\) premiers termes. Chaque arrangement de longueur \(p\) se prolonge de \(n – p\) façons exactement. D’où \(A_n^{p+1} = (n – p) A_n^p\). Enfin, une application de \(E\) dans \(E\) correspond à la liste de ses images. Elle est bijective si et seulement si elle est injective, c’est-à-dire si cette liste est un arrangement de \(n\) éléments.

Un code de carte bancaire comporte \(4\) chiffres. Il y a donc \(10^4 = 10\,000\) codes possibles. Parmi eux, \(A_{10}^4 = 10 \times 9 \times 8 \times 7 = 5\,040\) ont leurs chiffres deux à deux distincts.

Soit \(E\) un ensemble à \(n\) éléments et \(k \in \mathbb{N}\). Une combinaison de \(k\) éléments de \(E\) est une partie de \(E\) à \(k\) éléments. Leur nombre est noté \(\dbinom{n}{k}\), lu « \(k\) parmi \(n\) ».

Pour \(0 \leq\, k \leq\, n\), on a \(\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}\). Pour \(k > n\), \(\dbinom{n}{k} = 0\).

Considérons l’application qui associe à un arrangement \((x_1, \ldots, x_k)\) la partie \(\{x_1, \ldots, x_k\}\). Elle est surjective sur l’ensemble des combinaisons. De plus, chaque partie à \(k\) éléments est l’image d’exactement \(k!\) arrangements, un par ordre possible. Par le principe des bergers, \(A_n^k = k! \dbinom{n}{k}\). On divise alors par \(k!\).

Pour \(1 \leq\, k \leq\, n\) :

• symétrie : \(\dbinom{n}{k} = \dbinom{n}{n-k}\) ;
• formule du capitaine : \(k \dbinom{n}{k} = n \dbinom{n-1}{k-1}\) ;
• somme : \(\sum_{k=0}^{n} \dbinom{n}{k} = 2^n\).

(Formule de Pascal) Pour tous entiers \(n \geq\, 1\) et \(1 \leq\, k \leq\, n\),

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

Fixons un élément \(a\) de \(E\), avec \(|E| = n\). Les parties à \(k\) éléments de \(E\) se répartissent en deux classes disjointes. D’une part, celles qui contiennent \(a\) : elles correspondent, en retirant \(a\), aux parties à \(k-1\) éléments de \(E \setminus \{a\}\). D’autre part, celles qui ne contiennent pas \(a\) : ce sont les parties à \(k\) éléments de \(E \setminus \{a\}\). On additionne les deux cardinaux.

Pour démontrer une identité combinatoire, deux voies sont possibles.

• Par le calcul : on utilise la formule factorielle, la formule de Pascal ou une récurrence.
• Par double comptage : on compte un même ensemble de deux façons, ou l’on construit une bijection entre deux ensembles.

Par exemple, pour \(k \dbinom{n}{k} = n \dbinom{n-1}{k-1}\), on compte les comités de \(k\) personnes munis d’un président. On choisit soit le comité puis le président, soit le président puis les \(k-1\) autres membres.

Pour tous nombres complexes \(a\), \(b\) et tout \(n \in \mathbb{N}\),

\[(a + b)^n = \sum_{k=0}^{n} \binom\,{n}{k} a^k b^{n-k}.\]

Procédons par récurrence sur \(n\). Pour \(n = 0\), les deux membres valent \(1\). Supposons la formule vraie au rang \(n\). Alors \((a+b)^{n+1} = \sum_{k=0}^{n} \binom\,{n}{k} a^{k+1} b^{n-k} + \sum_{k=0}^{n} \binom\,{n}{k} a^k b^{n+1-k}\). Dans la première somme, on pose \(j = k + 1\). Ensuite, on regroupe les termes en \(a^j b^{n+1-j}\) :

\[(a+b)^{n+1} = b^{n+1} + \sum_{j=1}^{n} [\binom\,{n}{j-1} + \binom\,{n}{j}] a^j b^{n+1-j} + a^{n+1}.\]

La formule de Pascal donne alors le rang \(n+1\).

Avec \(a = b = 1\), on retrouve \(\sum_{k=0}^{n} \binom\,{n}{k} = 2^n\). Avec \(a = -1\) et \(b = 1\), on obtient \(\sum_{k=0}^{n} (-1)^k \binom\,{n}{k} = 0\) pour \(n \geq\, 1\). Autrement dit, une partie d’un ensemble non vide a autant de chances d’avoir un cardinal pair qu’impair.

La formule reste vraie dans tout anneau, à condition que \(a\) et \(b\) commutent. Vous la retrouverez donc avec les matrices, sous l’hypothèse \(AB = BA\).