Récurrence et dénombrement : corrigé des exercices de maths en L1.

Corrigé de l’exercice 1 : Somme des cubes par récurrence

1. On calcule directement : \(S_1 = 1\), \(S_2 = 1 + 8 = 9\), \(S_3 = 9 + 27 = 36\) et \(S_4 = 36 + 64 = 100\). On remarque que ce sont des carrés : \(1^2\), \(3^2\), \(6^2\) et \(10^2\). De plus, \(1\), \(3\), \(6\) et \(10\) sont les sommes \(1 + \cdots + n\). On conjecture que \(S_n = (\frac{n(n+1)}{2})^2\).
2. Pour \(n \geq\, 1\), notons \(\mathcal{P}(n)\) : « \(S_n = \frac{n^2(n+1)^2}{4}\) ».

   Initialisation : \(S_1 = 1\) et \(\frac{1^2 \times 2^2}{4} = 1\). Donc \(\mathcal{P}(1)\) est vraie.

   Hérédité : soit \(n \geq\, 1\) tel que \(\mathcal{P}(n)\) soit vraie. Alors

   \[S_{n+1} = S_n + (n+1)^3 = \frac{(n+1)^2}{4}(n^2 + 4(n+1)) = \frac{(n+1)^2 (n+2)^2}{4}.\]

   En effet, \(n^2 + 4n + 4 = (n+2)^2\). Ainsi \(\mathcal{P}(n+1)\) est vraie. Par le principe de récurrence, \(S_n = (\frac{n(n+1)}{2})^2\) pour tout \(n \geq\, 1\).

3. On sait que \(\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\). Par conséquent, \(\sum_{k=1}^{n} k^3 = (\sum_{k=1}^{n} k)^2\).

Point de méthode : dans l’hérédité, factorisez tôt par \((n+1)^2\). Le calcul devient alors immédiat, alors qu’un développement complet serait long et risqué.

Corrigé de l’exercice 2 : Inégalité de Bernoulli

1. Soit \(x \geq\, -1\) fixé. Pour \(n \in \mathbb{N}\), notons \(\mathcal{P}(n)\) : « \((1+x)^n \geq\, 1 + nx\) ».

   Initialisation : \((1+x)^0 = 1 = 1 + 0 \cdot x\). Donc \(\mathcal{P}(0)\) est vraie.

   Hérédité : soit \(n \in \mathbb{N}\) tel que \(\mathcal{P}(n)\) soit vraie. Comme \(1 + x \geq\, 0\), on peut multiplier l’inégalité par \(1 + x\) sans changer son sens :

   \[(1+x)^{n+1} \geq\, (1 + nx)(1 + x) = 1 + (n+1)x + nx^2 \geq\, 1 + (n+1)x.\]

   En effet, \(nx^2 \geq\, 0\). Donc \(\mathcal{P}(n+1)\) est vraie. Par récurrence, \((1+x)^n \geq\, 1 + nx\) pour tout \(n \in \mathbb{N}\).

2. L’hypothèse sert uniquement à garantir \(1 + x \geq\, 0\) lors de la multiplication. Sans elle, l’inégalité peut tomber en défaut. Par exemple, pour \(x = -4\) et \(n = 3\), on a \((1+x)^3 = (-3)^3 = -27\), tandis que \(1 + 3x = -11\). Ainsi \(-27 < -11\) : l’inégalité est fausse.
3. Soit \(n \geq\, 1\). Avec \(x = \frac{1}{n} \geq\, -1\), on obtient \((1 + \frac{1}{n})^n \geq\, 1 + 1 = 2\). Ensuite, avec \(x = -\frac{1}{2n}\), qui vérifie \(x \geq\, -\frac{1}{2} \geq\, -1\), on obtient \((1 – \frac{1}{2n})^n \geq\, 1 – \frac{1}{2} = \frac{1}{2}\). Les deux inégalités sont démontrées.

Géométriquement, l’inégalité de Bernoulli signifie que la courbe de \(x \mapsto (1+x)^n\) reste au-dessus de sa tangente en \(0\) sur \([-1, +\infty[\). La figure ci-dessous l’illustre pour \(n = 4\).

Corrigé de l’exercice 3 : Une suite récurrente double

1. On calcule \(u_2 = 3 \times 3 – 2 \times 2 = 5\), puis \(u_3 = 3 \times 5 – 2 \times 3 = 9\) et \(u_4 = 3 \times 9 – 2 \times 5 = 17\). Les termes \(2, 3, 5, 9, 17\) valent \(2^n + 1\). On conjecture que \(u_n = 2^n + 1\).
2. Pour \(n \in \mathbb{N}\), notons \(\mathcal{P}(n)\) : « \(u_n = 2^n + 1\) et \(u_{n+1} = 2^{n+1} + 1\) ».

   Initialisation : \(u_0 = 2 = 2^0 + 1\) et \(u_1 = 3 = 2^1 + 1\). Donc \(\mathcal{P}(0)\) est vraie.

   Hérédité : soit \(n \in \mathbb{N}\) tel que \(\mathcal{P}(n)\) soit vraie. Alors

   \[u_{n+2} = 3(2^{n+1} + 1) – 2(2^n + 1) = 6 \cdot 2^n – 2 \cdot 2^n + 1 = 2^{n+2} + 1.\]

   Comme \(u_{n+1} = 2^{n+1} + 1\) fait déjà partie de l’hypothèse, \(\mathcal{P}(n+1)\) est vraie. Par récurrence, \(u_n = 2^n + 1\) pour tout \(n \in \mathbb{N}\).

3. Le terme \(u_{n+2}\) dépend de \(u_{n+1}\) et de \(u_n\). Une hypothèse portant sur un seul rang ne donne donc aucune information sur l’autre terme. C’est pourquoi l’hérédité doit porter sur deux rangs consécutifs.

Corrigé de l’exercice 4 : Récurrence forte et écritures binaires

1. Pour \(n \geq\, 1\), notons \(\mathcal{P}(n)\) : « \(n\) est une somme de puissances de \(2\) deux à deux distinctes ».

   Initialisation : \(1 = 2^0\), donc \(\mathcal{P}(1)\) est vraie.

   Hérédité forte : soit \(n \geq\, 2\) tel que \(\mathcal{P}(m)\) soit vraie pour tout \(m \in [\![1, n-1]\!]\). D’abord, si \(n = 2m\) est pair, alors \(1 \leq\, m \leq\, n – 1\). On écrit \(m = \sum_{i \in I} 2^i\) avec \(I\) fini. Ainsi \(n = \sum_{i \in I} 2^{i+1}\), et les exposants \(i + 1\) restent distincts. Ensuite, si \(n = 2m + 1\) est impair, alors \(m \geq\, 1\) car \(n \geq\, 3\). L’écriture précédente de \(2m\) n’utilise que des exposants au moins égaux à \(1\). On lui ajoute \(2^0\), qui est donc distinct des autres termes. Par récurrence forte, tout entier \(n \geq\, 1\) est une somme de puissances de \(2\) distinctes.

2. Convenons que \(0\) s’écrit comme la somme vide. Notons \(\mathcal{Q}(n)\) : « si \(n = \sum_{i \in I} 2^i = \sum_{j \in J} 2^j\) avec \(I\), \(J\) finis, alors \(I = J\) ». Pour \(n = 0\), toute somme non vide de puissances de \(2\) vaut au moins \(1\), donc \(I = J = \varnothing\).

   Soit \(n \geq\, 1\) tel que \(\mathcal{Q}(m)\) soit vraie pour tout \(m < n\). Supposons \(n = \sum_{i \in I} 2^i = \sum_{j \in J} 2^j\). Les termes d’exposant non nul sont pairs. Par conséquent, \(0 \in I\) si et seulement si \(n\) est impair, si et seulement si \(0 \in J\). Posons alors \(m = \frac{n – r}{2}\), où \(r \in \{0, 1\}\) est le reste de \(n\) modulo \(2\). On obtient

   \[m = \sum_{i \in I,\ i \geq\, 1} 2^{i-1} = \sum_{j \in J,\ j \geq\, 1} 2^{j-1}.\]

   Or \(m < n\). Par hypothèse, les ensembles d’exposants \(\{i – 1\}\) et \(\{j – 1\}\) coïncident. Ainsi \(I = J\). L’écriture est unique : c’est l’écriture binaire de \(n\).

3. On retire à chaque fois la plus grande puissance de \(2\) possible. Ainsi \(100 = 2^6 + 2^5 + 2^2\) et \(255 = 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0\). En effet, \(255 = 2^8 – 1\).

Point de méthode : la récurrence forte s’impose dès que l’hérédité fait appel à un rang qui n’est pas le précédent, ici \(\frac{n}{2}\) ou \(\frac{n-1}{2}\).

Corrigé de l’exercice 5 : Récurrences fautives

1. L’hérédité est censée valoir pour tout \(n \geq\, 1\). Or l’argument suppose que les deux groupes de \(n\) chevaux ont un cheval en commun. C’est vrai si \(n \geq\, 2\), puisque les chevaux numérotés \(2\) à \(n\) appartiennent aux deux groupes. En revanche, pour \(n = 1\), les deux groupes sont \(\{c_2\}\) et \(\{c_1\}\) : ils sont disjoints. L’implication \(\mathcal{P}(1) \Rightarrow \mathcal{P}(2)\) n’est donc pas démontrée, et toute la chaîne s’effondre.
2. Supposons que \(9\) divise \(10^n + 1\). Alors \(10^{n+1} + 1 = 10(10^n + 1) – 9\) est une différence de deux multiples de \(9\). La propriété est donc héréditaire. Cependant, \(10^n – 1 = (10 – 1)\sum_{k=0}^{n-1} 10^k\) est un multiple de \(9\) pour tout \(n \geq\, 1\), et c’est vrai aussi pour \(n = 0\). Ainsi \(10^n + 1 = (10^n – 1) + 2\) a pour reste \(2\) dans la division par \(9\). La propriété n’est vraie pour aucun entier \(n\) : l’initialisation manque toujours.
3. On trouve \(41\), \(43\), \(47\) et \(53\), qui sont premiers. En revanche, pour \(n = 40\), on obtient \(1600 + 40 + 41 = 1681 = 41^2\). Ce nombre n’est pas premier. Autrement dit, vérifier une propriété sur de nombreux cas ne démontre rien : seule une preuve pour tout \(n\) permet de conclure.

Corrigé de l’exercice 6 : Bon ordre et descente infinie

1. Soit \(m\) un minorant de \(A\). L’ensemble \(B = \{a – m,\ a \in A\}\) est contenu dans \(\mathbb{N}\), car \(a \geq\, m\) pour tout \(a \in A\). De plus, il est non vide. Par la propriété du bon ordre, il a un plus petit élément \(b = a_0 – m\), avec \(a_0 \in A\). Pour tout \(a \in A\), on a alors \(a – m \geq\, a_0 – m\), donc \(a \geq\, a_0\). Ainsi \(a_0\) est le plus petit élément de \(A\).
2. Soit \((u_n)\) une suite décroissante d’entiers naturels. L’ensemble \(\{u_n,\ n \in \mathbb{N}\}\) est une partie non vide de \(\mathbb{N}\). Il possède donc un plus petit élément \(u_p\). Pour \(n \geq\, p\), la décroissance donne \(u_n \leq\, u_p\). De plus, la minimalité donne \(u_n \geq\, u_p\). Donc \(u_n = u_p\) pour tout \(n \geq\, p\) : la suite est stationnaire.
3. Supposons que l’ensemble \(X\) des entiers \(x \geq\, 1\) pour lesquels il existe \(y \geq\, 1\) avec \(x^2 = 2y^2\) soit non vide. Par le bon ordre, il a un plus petit élément \(x\), associé à un entier \(y\).

   D’abord, \(x^2\) est pair. Si \(x\) était impair, \(x^2\) le serait aussi. Donc \(x = 2x_1\) avec \(x_1 \geq\, 1\). Ensuite, \(4x_1^2 = 2y^2\), c’est-à-dire \(y^2 = 2x_1^2\). Ainsi \(y \in X\). Or \(y^2 = \frac{x^2}{2} < x^2\), donc \(y < x\). Cela contredit la minimalité de \(x\). Par conséquent, \(X\) est vide.

   Si \(\sqrt{2}\) était rationnel, on écrirait \(\sqrt{2} = \frac{x}{y}\) avec \(x, y \geq\, 1\), et l’on aurait \(x^2 = 2y^2\). Donc \(\sqrt{2}\) est irrationnel.

Corrigé de l’exercice 7 : Changements d’indice et produits

1. Par linéarité, \(A_n = 2\sum_{k=1}^{n} k – \sum_{k=1}^{n} 1 = n(n+1) – n\). Donc \(A_n = n^2\). La somme des \(n\) premiers nombres impairs est un carré.
2. On pose \(j = k – 2\). Quand \(k\) décrit \([\![3, n+2]\!]\), \(j\) décrit \([\![1, n]\!]\). Ainsi \(B_n = \sum_{j=1}^{n} j^2 = \frac{n(n+1)(2n+1)}{6}\).
3. On sépare le facteur constant : \(C_n = \prod_{k=1}^{n} 2 \times \prod_{k=1}^{n} k\). Donc \(C_n = 2^n\, n!\). Ensuite, on sépare les entiers de \([\![1, 2n]\!]\) selon leur parité :

   \[(2n)! = \prod_{k=1}^{n} (2k) \times \prod_{k=1}^{n} (2k-1) = C_n D_n.\]

   Par conséquent, \(D_n = 1 \times 3 \times \cdots \times (2n-1) = \dfrac{(2n)!}{2^n\, n!}\). Par exemple, pour \(n = 3\), on trouve \(\frac{720}{48} = 15 = 1 \times 3 \times 5\).

4. Un produit de puissances de même base est la puissance de la somme des exposants. Ainsi \(E_n = 3^{1 + 2 + \cdots + n} = 3^{n(n+1)/2}\).

Corrigé de l’exercice 8 : Sommes et produits télescopiques

1. On réduit au même dénominateur :

   \[\frac{1}{k(k+1)} – \frac{1}{(k+1)(k+2)} = \frac{(k+2) – k}{k(k+1)(k+2)} = \frac{2}{k(k+1)(k+2)}.\]

   L’égalité annoncée est donc vraie. Posons \(v_k = \frac{1}{k(k+1)}\). Alors le terme général vaut \(\frac{1}{2}(v_k – v_{k+1})\). Par télescopage,

   \[\sum_{k=1}^{n} \frac{1}{k(k+1)(k+2)} = \frac{1}{2}(v_1 – v_{n+1}) = \frac{1}{4} – \frac{1}{2(n+1)(n+2)}.\]

   Cette somme vaut \(\frac{1}{4} – \frac{1}{2(n+1)(n+2)}\) et tend vers \(\frac{1}{4}\).

2. Pour tout \(k \in \mathbb{N}\), \((k+1)! – k! = k!\,(k + 1 – 1) = k \cdot k!\). Par télescopage, \(\sum_{k=0}^{n} k \cdot k! = (n+1)! – 0! = (n+1)! – 1\).
3. On écrit \(\ln(1 + \frac{1}{k}) = \ln(k+1) – \ln k\). Ainsi \(\sum_{k=1}^{n} \ln(1 + \frac{1}{k}) = \ln(n+1) – \ln 1 = \ln(n+1)\).
4. On factorise : \(1 – \frac{1}{k^2} = \frac{(k-1)(k+1)}{k^2} = \frac{k-1}{k} \times \frac{k+1}{k}\). Les deux produits obtenus sont télescopiques :

   \[\prod_{k=2}^{n} \frac{k-1}{k} = \frac{1}{n} \qquad \text{et} \qquad \prod_{k=2}^{n} \frac{k+1}{k} = \frac{n+1}{2}.\]

   Donc \(P_n = \dfrac{n+1}{2n}\), qui tend vers \(\frac{1}{2}\). Par exemple, \(P_2 = \frac{3}{4}\), ce qui correspond bien à \(1 – \frac{1}{4}\).

Corrigé de l’exercice 9 : Sommes doubles

1. Par linéarité, \(\sum_{i,j} (i + j) = \sum_{i,j} i + \sum_{i,j} j\). Dans la première somme, \(i\) ne dépend pas de \(j\), donc \(\sum_{i=1}^{n} \sum_{j=1}^{n} i = n \sum_{i=1}^{n} i = \frac{n^2(n+1)}{2}\). Par symétrie, la seconde somme a la même valeur. Ainsi \(\sum_{1 \leq\, i, j \leq\, n} (i + j) = n^2(n+1)\).
2. Pour \(j\) fixé, l’indice \(i\) décrit \([\![1, j]\!]\). Donc

   \[T_n = \sum_{j=1}^{n} \frac{j(j+1)}{2} = \frac{1}{2}(\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}) = \frac{n(n+1)(2n+4)}{12}.\]

   Finalement, \(T_n = \dfrac{n(n+1)(n+2)}{6}\).

3. Les couples \((i, j)\) se répartissent en trois ensembles disjoints. Si \(i < j\), le minimum vaut \(i\). Si \(i = j\), il vaut \(i\). Si \(i > j\), il vaut \(j\), et l’échange de \(i\) et \(j\) montre que cette dernière somme égale la première. Ensuite, \(\sum_{i < j} i = T_n – \sum_{i=1}^{n} i\). Ainsi

   \[M_n = 2(T_n – \frac{n(n+1)}{2}) + \frac{n(n+1)}{2} = \frac{n(n+1)(n+2)}{3} – \frac{n(n+1)}{2}.\]

   Donc \(M_n = \dfrac{n(n+1)(2n+1)}{6}\). Pour \(n = 2\), on vérifie : \(1 + 1 + 1 + 2 = 5 = \frac{2 \times 3 \times 5}{6}\).

Point de méthode : pour une somme triangulaire, dessinez les couples \((i, j)\) dans un carré. Les bornes de la somme intérieure se lisent alors ligne par ligne ou colonne par colonne.

Corrigé de l’exercice 10 : Somme des carrés par télescopage

1. Par le binôme, \((k+1)^3 – k^3 = 3k^2 + 3k + 1\). On somme de \(k = 1\) à \(n\). Le membre de gauche est télescopique, d’où \((n+1)^3 – 1 = 3S_2 + 3S_1 + n\).
2. On isole \(S_2\) en utilisant \(S_1 = \frac{n(n+1)}{2}\) et en factorisant par \(n+1\) :

   \[3S_2 = (n+1)^3 – (n+1) – \frac{3n(n+1)}{2} = (n+1)(n^2 + 2n – \frac{3n}{2}) = \frac{n(n+1)(2n+1)}{2}.\]

   Donc \(S_2 = \dfrac{n(n+1)(2n+1)}{6}\).

3. De même, \((k+1)^4 – k^4 = 4k^3 + 6k^2 + 4k + 1\). En sommant, on obtient \((n+1)^4 – 1 = 4S_3 + 6S_2 + 4S_1 + n\). Or \(6S_2 = n(n+1)(2n+1)\) et \(4S_1 = 2n(n+1)\). De plus, \((n+1)^4 – 1 – n = (n+1)((n+1)^3 – 1)\). Par conséquent,

   \[4S_3 = (n+1)(n^3 + 3n^2 + 3n – 2n^2 – n – 2n) = (n+1)(n^3 + n^2).\]

   Ainsi \(S_3 = \dfrac{n^2(n+1)^2}{4}\), comme dans l’exercice 1.

Corrigé de l’exercice 11 : Somme arithmético-géométrique

1. On a \(x S_n = \sum_{k=1}^{n} k x^{k+1}\). On pose \(j = k + 1\) : \(x S_n = \sum_{j=2}^{n+1} (j – 1) x^j\). On isole alors le terme \(k = 1\) de \(S_n\) et le terme \(j = n+1\) de \(xS_n\) :

   \[S_n – x S_n = x + \sum_{k=2}^{n} (k – (k-1)) x^k – n x^{n+1} = \sum_{k=1}^{n} x^k – n x^{n+1}.\]

   Donc \((1 – x) S_n = \dfrac{x(1 – x^n)}{1 – x} – n x^{n+1}\), grâce à la somme géométrique.

2. On divise par \(1 – x \neq 0\) et on réduit au même dénominateur. Le numérateur vaut \(x – x^{n+1} – n x^{n+1} + n x^{n+2} = x(1 – (n+1)x^n + n x^{n+1})\). On obtient bien la formule annoncée.
3. Pour \(x = 2\), on a \((1 – x)^2 = 1\). Donc \(\sum_{k=1}^{n} k\, 2^k = 2(1 – (n+1)2^n + n\, 2^{n+1}) = 2 + 2^{n+1}(2n – n – 1)\). Ainsi \(\sum_{k=1}^{n} k\, 2^k = (n-1)\,2^{n+1} + 2\). Pour \(n = 3\), on trouve \(2 + 8 + 24 = 34\) et \(2 \times 16 + 2 = 34\).
4. Pour \(x = \frac{1}{2}\), les termes \(x^n\), \((n+1)x^n\) et \(n x^{n+1}\) tendent vers \(0\). Par opérations sur les limites, \(S_n\) tend vers \(\frac{x}{(1-x)^2} = \frac{1/2}{1/4}\). La limite vaut \(2\).

Corrigé de l’exercice 12 : Cardinal d’une union et crible

1. Notons \(A\) et \(D\) les ensembles d’étudiants suivant l’anglais et l’allemand. Alors \(|A \cup D| = 25 + 18 – 7 = 36\). Le complémentaire dans la promotion a donc \(40 – 36\) éléments. Ainsi \(4\) étudiants ne suivent aucune des deux options.
2. On applique la formule à \(A \cup B\) et \(C\) : \(|A \cup B \cup C| = |A \cup B| + |C| – |(A \cup B) \cap C|\). Or \((A \cup B) \cap C = (A \cap C) \cup (B \cap C)\) par distributivité. De plus, l’intersection de ces deux parties est \(A \cap B \cap C\). En appliquant encore la formule, on obtient

   \[|A \cup B \cup C| = |A| + |B| + |C| – |A \cap B| – |A \cap C| – |B \cap C| + |A \cap B \cap C|.\]

   C’est la formule du crible pour trois parties.

3. Si \(6\) divise \(m\), alors \(2\) et \(3\) divisent \(m\). Réciproquement, supposons que \(2\) et \(3\) divisent \(m\). Alors \(3m\) est multiple de \(6\) car \(2 \mid m\), et \(2m\) est multiple de \(6\) car \(3 \mid m\). Donc \(m = 3m – 2m\) est multiple de \(6\). Ainsi \(A_2 \cap A_3 = A_6\), et de même \(A_2 \cap A_5 = A_{10}\), \(A_3 \cap A_5 = A_{15}\), \(A_2 \cap A_3 \cap A_5 = A_{30}\).

   Ensuite, \(q \mapsto dq\) est une bijection de \([\![1, q_0]\!]\) sur \(A_d\), où \(q_0\) est le plus grand entier tel que \(d q_0 \leq\, 1000\). Donc \(|A_d| = \lfloor \frac{1000}{d} \rfloor\).

4. On obtient \(|A_2| = 500\), \(|A_3| = 333\), \(|A_5| = 200\), \(|A_6| = 166\), \(|A_{10}| = 100\), \(|A_{15}| = 66\) et \(|A_{30}| = 33\). Par la formule du crible,

   \[|A_2 \cup A_3 \cup A_5| = 500 + 333 + 200 – 166 – 100 – 66 + 33 = 734.\]

   Il y a \(734\) entiers divisibles par \(2\), \(3\) ou \(5\), et donc \(1000 – 734 = 266\) qui ne le sont par aucun. La figure ci-dessous donne l’effectif de chaque zone. Par exemple, la zone « multiples de \(2\) seulement » contient \(500 – 166 – 100 + 33 = 267\) entiers.

Corrigé de l’exercice 13 : Applications, injections et parties

1. Numérotons \(E = \{x_1, \ldots, x_n\}\). L’application \(f \mapsto (f(x_1), \ldots, f(x_n))\) est une bijection de l’ensemble des applications de \(E\) dans \(F\) sur \(F^n\). Il y a donc \(|F^n| = p^n\) applications. De plus, \(f\) est injective si et seulement si cette liste est formée d’éléments distincts. Il y a donc \(p^n\) applications et \(A_p^n = \frac{p!}{(p-n)!}\) injections.
2. Notons \(\Phi(X) = \mathbf{1}_X\) et, pour \(f : E \to \{0, 1\}\), \(\Psi(f) = f^{-1}(\{1\})\). D’une part, \(\Psi(\mathbf{1}_X) = \{x : \mathbf{1}_X(x) = 1\} = X\). D’autre part, \(\mathbf{1}_{\Psi(f)}\) vaut \(1\) exactement là où \(f\) vaut \(1\), donc égale \(f\). Ainsi \(\Phi\) est bijective, de réciproque \(\Psi\). Par la question 1, \(|\mathcal{P}(E)| = 2^n\).
3. Une relation binaire est une partie de \(E \times E\), qui compte \(n^2\) éléments. Il y a donc \(2^{n^2}\) relations binaires sur \(E\).
4. À un couple \((A, B)\) avec \(A \subset B\), on associe \(f\) valant \(2\) sur \(A\), \(1\) sur \(B \setminus A\) et \(0\) hors de \(B\). Réciproquement, à \(f : E \to \{0, 1, 2\}\), on associe \(A = f^{-1}(\{2\})\) et \(B = f^{-1}(\{1, 2\})\), qui vérifient \(A \subset B\). Ces deux constructions sont réciproques l’une de l’autre. Il y a donc \(3^n\) tels couples.

Corrigé de l’exercice 14 : Codes et anagrammes

1. Un code est une \(4\)-liste de \([\![0, 9]\!]\) : il y en a \(10^4 = 10\,000\). Les codes à chiffres distincts sont des arrangements : \(10 \times 9 \times 8 \times 7 = 5\,040\). Par passage au complémentaire, \(10\,000 – 5\,040 = 4\,960\) codes comportent un chiffre répété.
2. On compte les arrangements de \(5\) lettres parmi \(26\) : \(26 \times 25 \times 24 \times 23 \times 22 = 7\,893\,600\) mots.
3. Les lettres de MATHS sont distinctes : une anagramme est une permutation de ces lettres. Il y en a \(5! = 120\). Pour ANANAS, on choisit d’abord les \(3\) positions des A parmi \(6\), soit \(\binom\,{6}{3} = 20\) choix. Ensuite, on choisit les \(2\) positions des N parmi les \(3\) restantes, soit \(3\) choix. Enfin, le S occupe la dernière place. Il y a \(20 \times 3 = 60\) anagrammes de ANANAS.
4. Les deux places voisines occupées par Alice et Bruno forment l’une des \(5\) paires de places adjacentes. Ensuite, Alice et Bruno s’y placent de \(2\) façons. Enfin, les quatre autres personnes occupent les places restantes de \(4! = 24\) façons. Il y a \(5 \times 2 \times 24 = 240\) dispositions.

Point de méthode : demandez-vous toujours si l’ordre compte. S’il compte, on dénombre des listes ou des arrangements ; sinon, des combinaisons.

Corrigé de l’exercice 15 : Mains de cinq cartes

1. Une main est une combinaison de \(5\) cartes parmi \(32\). Il y a \(\binom\,{32}{5} = \frac{32 \times 31 \times 30 \times 29 \times 28}{120} = 201\,376\) mains.
2. On choisit \(2\) as parmi \(4\), puis \(3\) cartes parmi les \(28\) autres. On obtient \(\binom\,{4}{2}\binom\,{28}{3} = 6 \times 3\,276 = 19\,656\) mains.
3. On passe au complémentaire. Les mains sans cœur sont les parties à \(5\) éléments des \(24\) autres cartes : il y en a \(\binom\,{24}{5} = 42\,504\). Donc \(201\,376 – 42\,504 = 158\,872\) mains contiennent au moins un cœur.
4. On choisit la couleur (\(4\) choix), puis \(5\) cartes parmi les \(8\) de cette couleur. Il y a \(4 \times \binom\,{8}{5} = 4 \times 56 = 224\) telles mains.
5. On choisit la hauteur du brelan (\(8\) choix) et ses trois couleurs (\(\binom\,{4}{3} = 4\) choix). Ensuite, on choisit la hauteur de la paire parmi les \(7\) restantes, puis ses deux couleurs (\(\binom\,{4}{2} = 6\) choix). Il y a \(8 \times 4 \times 7 \times 6 = 1\,344\) fulls.

Corrigé de l’exercice 16 : Chemins dans un quadrillage

1. Un chemin de \(O\) à \(B\) comporte exactement \(5\) pas D et \(3\) pas H, puisque l’abscisse augmente de \(5\) et l’ordonnée de \(3\). On lui associe la suite de ses pas. Réciproquement, tout mot de \(8\) lettres avec \(5\) D et \(3\) H décrit un chemin unique de \(O\) à \(B\). Un tel mot est déterminé par la position de ses \(3\) lettres H. Il y a donc \(\binom\,{8}{3} = 56\) chemins.
2. Un chemin passant par \(C\) se découpe de façon unique en un chemin de \(O\) à \(C\) suivi d’un chemin de \(C\) à \(B\). Le premier comporte \(2\) D et \(1\) H, soit \(\binom\,{3}{1} = 3\) possibilités. Le second comporte \(3\) D et \(2\) H, soit \(\binom\,{5}{2} = 10\) possibilités. Il y a \(3 \times 10 = 30\) chemins passant par \(C\) et \(56 – 30 = 26\) qui l’évitent. Sur la figure ci-dessous, chaque nœud porte le nombre de chemins qui y mènent depuis \(O\).

3. Comme à la question 1, \(c(m, n) = \binom\,{m+n}{n}\). Pour \(m, n \geq\, 1\), le dernier pas d’un chemin vers \((m, n)\) vient soit de \((m-1, n)\) par un pas D, soit de \((m, n-1)\) par un pas H. Ces deux cas sont disjoints. Donc \(c(m, n) = c(m-1, n) + c(m, n-1)\). En notant \(N = m + n\) et \(k = n\), cela s’écrit

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

   On retrouve la formule de Pascal. La figure ci-dessus en donne une lecture directe : chaque nombre est la somme de ses voisins de gauche et du dessous.

Corrigé de l’exercice 17 : Binôme de Newton et coefficients

1. La ligne \(4\) du triangle de Pascal est \(1, 4, 6, 4, 1\). Avec \(a = 2x\) et \(b = -1\), on obtient \(\sum_{k=0}^{4} \binom\,{4}{k} (2x)^k (-1)^{4-k}\). Donc \((2x – 1)^4 = 16x^4 – 32x^3 + 24x^2 – 8x + 1\).
2. Le terme en \(x^3\) correspond à \(k = 3\) : \(\binom\,{7}{3} (2x)^3 (-1)^4 = 35 \times 8\, x^3\). Le coefficient vaut \(280\).
3. Par la formule du binôme avec \(a = 2\) et \(b = 1\), \(\sum_{k=0}^{n} \binom\,{n}{k} 2^k = 3^n\). Avec \(a = -1\) et \(b = 3\), \(\sum_{k=0}^{n} (-1)^k \binom\,{n}{k} 3^{n-k} = 2^n\).
4. On écrit \(1{,}01^{10} = (1 + 0{,}01)^{10} = \sum_{k=0}^{10} \binom\,{10}{k} 0{,}01^k\). Tous les termes sont positifs. On minore donc par les trois premiers : \(1 + 10 \times 0{,}01 + 45 \times 0{,}0001 = 1{,}1045\). Ainsi \(1{,}01^{10} \geq\, 1{,}1045\).

Corrigé de l’exercice 18 : Identités par double comptage

1. L’application \(X \mapsto E \setminus X\) est une involution de \(\mathcal{P}(E)\), donc une bijection. Elle envoie les parties à \(k\) éléments sur les parties à \(n – k\) éléments, et réciproquement. Ainsi \(\binom\,{n}{k} = \binom\,{n}{n-k}\).
2. Comptons les couples \((X, a)\) où \(X\) est une partie à \(k\) éléments et \(a \in X\). D’abord, on choisit \(X\) puis \(a\) : \(k\binom\,{n}{k}\) possibilités. Ensuite, on choisit \(a\) parmi \(n\) éléments, puis les \(k – 1\) autres membres parmi \(n – 1\) : \(n\binom\,{n-1}{k-1}\) possibilités. Donc \(k\binom\,{n}{k} = n\binom\,{n-1}{k-1}\). En sommant et en posant \(j = k – 1\),

   \[\sum_{k=0}^{n} k\binom\,{n}{k} = n \sum_{j=0}^{n-1} \binom\,{n-1}{j} = n\, 2^{n-1}.\]

   Ainsi \(\sum_{k=0}^{n} k\binom\,{n}{k} = n\,2^{n-1}\).

3. L’application \(\sigma : X \mapsto X \,\Delta\, \{a\}\) ajoute \(a\) à \(X\) s’il n’y est pas, et le retire sinon. Elle modifie donc le cardinal de \(\pm 1\), ce qui change sa parité. De plus, \(\sigma \circ \sigma = \mathrm{id}\), donc \(\sigma\) est bijective. Elle réalise ainsi une bijection des parties paires sur les parties impaires. Ces deux ensembles ont le même cardinal, et leur réunion disjointe est \(\mathcal{P}(E)\). Il y a donc \(2^{n-1}\) parties de cardinal pair.
4. Une paire \(\{i, j\}\) avec \(i < j\) a pour plus grand élément \(j\). Pour \(j\) fixé, l’autre élément \(i\) se choisit dans \([\![1, j-1]\!]\), soit \(j – 1\) possibilités. Les paires se répartissent selon la valeur de \(j\). Par conséquent, \(\sum_{j=1}^{n} (j – 1) = \binom\,{n}{2}\), ce qui redonne \(\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}\).

Corrigé de l’exercice 19 : Formule de Vandermonde

1. Une délégation de \(p\) personnes est une partie à \(p\) éléments de l’assemblée : il y en a \(\binom\,{a+b}{p}\). Classons-les selon le nombre \(k\) de femmes qu’elles contiennent. Pour \(k\) fixé, on choisit \(k\) femmes parmi \(a\), puis \(p – k\) hommes parmi \(b\). Les termes avec \(k > a\) ou \(p – k > b\) sont nuls, ce qui est cohérent. Ainsi \(\sum_{k=0}^{p} \binom\,{a}{k}\binom\,{b}{p-k} = \binom\,{a+b}{p}\).
2. On a \((1+x)^a (1+x)^b = (1+x)^{a+b}\). D’un côté, le coefficient de \(x^p\) à droite vaut \(\binom\,{a+b}{p}\) par le binôme. De l’autre, le produit de \(\sum_k \binom\,{a}{k} x^k\) par \(\sum_j \binom\,{b}{j} x^j\) a pour coefficient de \(x^p\) la somme des produits avec \(k + j = p\). Deux polynômes égaux ont les mêmes coefficients, d’où la même formule.
3. On prend \(a = b = p = n\) et l’on utilise la symétrie \(\binom\,{n}{n-k} = \binom\,{n}{k}\). On obtient \(\sum_{k=0}^{n} \binom\,{n}{k}^2 = \binom\,{2n}{n}\).
4. Par la formule du capitaine, \(k\binom\,{n}{k} = n\binom\,{n-1}{k-1}\) pour \(k \geq\, 1\), et le terme \(k = 0\) est nul. Ensuite, on écrit \(\binom\,{n}{k} = \binom\,{n}{n-k}\) et l’on pose \(j = k – 1\) :

   \[\sum_{k=0}^{n} k\binom\,{n}{k}^2 = n\sum_{j=0}^{n-1} \binom\,{n-1}{j}\binom\,{n}{n-1-j} = n\binom\,{2n-1}{n-1}.\]

   La dernière égalité est la formule de Vandermonde avec \(a = n – 1\), \(b = n\) et \(p = n – 1\). Donc \(\sum_{k=0}^{n} k\binom\,{n}{k}^2 = n\binom\,{2n-1}{n-1}\). Pour \(n = 2\), on trouve \(1 \times 4 + 2 \times 1 = 6\) et \(2 \times \binom\,{3}{1} = 6\).

Point de méthode : pour une somme de produits de coefficients binomiaux, cherchez à reconnaître un coefficient d’un produit de polynômes ou un comptage par catégories.

Corrigé de l’exercice 20 : Formule de la crosse de hockey

1. Fixons \(p\). Pour \(n \geq\, p\), notons \(\mathcal{P}(n)\) : « \(\sum_{k=p}^{n} \binom\,{k}{p} = \binom\,{n+1}{p+1}\) ».

   Initialisation : pour \(n = p\), les deux membres valent \(\binom\,{p}{p} = 1 = \binom\,{p+1}{p+1}\).

   Hérédité : soit \(n \geq\, p\) tel que \(\mathcal{P}(n)\) soit vraie. Alors \(\sum_{k=p}^{n+1} \binom\,{k}{p} = \binom\,{n+1}{p+1} + \binom\,{n+1}{p}\). Par la formule de Pascal, ce nombre vaut \(\binom\,{n+2}{p+1}\). Par récurrence, la formule est vraie pour tout \(n \geq\, p\).

2. Soit \(X\) une partie à \(p + 1\) éléments de \([\![1, n+1]\!]\), et \(m\) son plus grand élément. Alors \(m \in [\![p+1, n+1]\!]\). De plus, \(X \setminus \{m\}\) est une partie à \(p\) éléments de \([\![1, m-1]\!]\), et tout choix d’une telle partie convient. Pour \(m\) fixé, il y a donc \(\binom\,{m-1}{p}\) parties. En posant \(k = m – 1\), on obtient \(\binom\,{n+1}{p+1} = \sum_{k=p}^{n} \binom\,{k}{p}\). C’est la même formule, obtenue par bijection.
3. On vérifie : \(2\binom\,{k}{2} + \binom\,{k}{1} = k(k-1) + k = k^2\). En sommant de \(k = 1\) à \(n\), avec \(\binom\,{1}{2} = 0\), et en appliquant la formule pour \(p = 2\) puis \(p = 1\) :

   \[\sum_{k=1}^{n} k^2 = 2\binom\,{n+1}{3} + \binom\,{n+1}{2} = \frac{(n+1)n(n-1)}{3} + \frac{n(n+1)}{2}.\]

   On factorise par \(\frac{n(n+1)}{6}\) : il reste \(2(n-1) + 3 = 2n + 1\). On retrouve \(\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\).

Le nom de la formule vient du triangle de Pascal. En effet, les termes sommés forment une colonne oblique, et le résultat se lit juste en dessous, comme la palette d’une crosse.

Corrigé de l’exercice 21 : Surjections

1. La seule application de \([\![1, n]\!]\) dans \(\{1\}\) est constante et surjective : \(s(n, 1) = 1\). Entre deux ensembles de même cardinal, une application est surjective si et seulement si elle est bijective : \(s(n, n) = n!\). Enfin, l’image d’une application définie sur \([\![1, n]\!]\) a au plus \(n\) éléments. Donc \(s(n, p) = 0\) si \(p > n\).
2. Il y a \(2^n\) applications de \([\![1, n]\!]\) dans \(\{1, 2\}\). Une telle application n’est pas surjective si et seulement si elle est constante. Il y a exactement deux applications constantes. Donc \(s(n, 2) = 2^n – 2\).
3. Soit \(f\) une surjection de \([\![1, n+1]\!]\) sur \([\![1, n]\!]\). Les \(n\) ensembles \(f^{-1}(\{y\})\) sont non vides, disjoints, et leurs cardinaux ont pour somme \(n + 1\). Ainsi, un seul d’entre eux possède deux éléments et tous les autres en ont un. Une telle surjection est déterminée par deux choix. D’abord, la paire des deux antécédents communs : \(\binom\,{n+1}{2}\) choix. Ensuite, la bijection entre les \(n\) classes obtenues et \([\![1, n]\!]\) : \(n!\) choix. Donc \(s(n+1, n) = \frac{(n+1)n}{2} \times n! = \frac{n\,(n+1)!}{2}\).
4. Soit \(f\) une surjection de \([\![1, n]\!]\) sur \([\![1, p]\!]\) et \(y = f(n)\). Il y a \(p\) choix pour \(y\). Deux cas se présentent alors.

   D’une part, \(y\) peut avoir un autre antécédent. Dans ce cas, la restriction de \(f\) à \([\![1, n-1]\!]\) est une surjection sur \([\![1, p]\!]\), et réciproquement : cela donne \(s(n-1, p)\) possibilités.

   D’autre part, \(n\) peut être le seul antécédent de \(y\). Dans ce cas, la restriction est une surjection sur \([\![1, p]\!] \setminus \{y\}\), ensemble à \(p – 1\) éléments : cela donne \(s(n-1, p-1)\) possibilités.

   Donc \(s(n, p) = p\big(s(n-1, p) + s(n-1, p-1)\big)\). Par suite, \(s(4, 2) = 2(s(3, 2) + s(3, 1)) = 2(6 + 1) = 14\), ce qui confirme \(2^4 – 2\). De même, \(s(4, 3) = 3(s(3, 3) + s(3, 2)) = 3(6 + 6) = 36\), en accord avec la question 3 pour \(n = 3\).

5. Classons les applications \(f\) de \([\![1, n]\!]\) dans \([\![1, p]\!]\) selon leur image \(Y = f([\![1, n]\!])\). Cette image est non vide, de cardinal \(k \in [\![1, p]\!]\). Pour \(Y\) fixé, les applications d’image \(Y\) sont les surjections sur \(Y\). Par composition avec une bijection de \(Y\) sur \([\![1, k]\!]\), il y en a \(s(n, k)\). Comme il y a \(\binom\,{p}{k}\) parties \(Y\) de cardinal \(k\), on obtient \(p^n = \sum_{k=1}^{p} \binom\,{p}{k} s(n, k)\). Pour \(n = 3\) et \(p = 2\) : \(2 \times 1 + 1 \times 6 = 8 = 2^3\).

Corrigé de l’exercice 22 : Problème : pavages et nombres de Fibonacci

1. La bande de longueur \(1\) n’admet que C. Celle de longueur \(2\) admet CC et D. Celle de longueur \(3\) admet CCC, CD et DC. Enfin, la figure de l’énoncé montre cinq pavages de longueur \(4\). Donc \(t_1 = 1\), \(t_2 = 2\), \(t_3 = 3\) et \(t_4 = 5\).
2. Soit \(n \geq\, 2\). La dernière pièce d’un pavage est soit un carré, soit un domino. Dans le premier cas, le reste est un pavage de longueur \(n – 1\). Dans le second, le reste est un pavage de longueur \(n – 2\). Ces deux cas sont disjoints, et tout pavage des longueurs \(n-1\) ou \(n-2\) se complète ainsi. Donc \(t_n = t_{n-1} + t_{n-2}\), puis \(t_5 = 8\) et \(t_6 = 13\). La suite \((t_n)\) est la suite de Fibonacci décalée : \(t_n = F_{n+1}\).
3. Un pavage à \(k\) dominos comporte \(n – 2k\) carrés, soit \(n – k\) pièces. Il est déterminé par les positions des \(k\) dominos parmi ces \(n – k\) pièces. Il y en a donc \(\binom\,{n-k}{k}\), pour \(0 \leq\, k \leq\, \lfloor n/2 \rfloor\). Ainsi \(t_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom\,{n-k}{k}\). Pour \(n = 6\) : \(\binom\,{6}{0} + \binom\,{5}{1} + \binom\,{4}{2} + \binom\,{3}{3} = 1 + 5 + 6 + 1 = 13\).
4. Pour \(n \geq\, 1\), notons \(\mathcal{P}(n)\) : « \((\frac{3}{2})^{n-1} \leq\, t_n \leq\, (\frac{7}{4})^n \) ».

   Initialisation : \(1 \leq\, t_1 = 1 \leq\, \frac{7}{4}\) et \(\frac{3}{2} \leq\, t_2 = 2 \leq\, \frac{49}{16}\). Donc \(\mathcal{P}(1)\) et \(\mathcal{P}(2)\) sont vraies.

   Hérédité : soit \(n \geq\, 1\) tel que \(\mathcal{P}(n)\) et \(\mathcal{P}(n+1)\) soient vraies. Pour la majoration, \(\frac{7}{4} + 1 = \frac{44}{16} \leq\, \frac{49}{16}\). Ainsi

   \[t_{n+2} = t_{n+1} + t_n \leq\, (\frac{7}{4})^n (\frac{7}{4} + 1) \leq\, (\frac{7}{4})^{n+2}.\]

   Pour la minoration, \(\frac{3}{2} + 1 = \frac{10}{4} \geq\, \frac{9}{4}\). Ainsi \(t_{n+2} \geq\, (\frac{3}{2})^{n-1}(\frac{3}{2} + 1) \geq\, (\frac{3}{2})^{n+1}\). Donc \(\mathcal{P}(n+2)\) est vraie. Par récurrence double, l’encadrement vaut pour tout \(n \geq\, 1\). La figure ci-dessous, en échelle logarithmique, montre \(t_n\) entre ses deux bornes.

5. Pour \(k \geq\, 0\), la relation de la question 2 au rang \(k + 2\) donne \(t_k = t_{k+2} – t_{k+1}\). Par télescopage, \(\sum_{k=0}^{n} t_k = t_{n+2} – t_1\). Donc \(\sum_{k=0}^{n} t_k = t_{n+2} – 1\). Par exemple, \(1 + 1 + 2 + 3 = 7 = t_5 – 1\).
6. Numérotons les cases de \(1\) à \(m + n\). Pour un pavage donné, deux cas s’excluent. D’abord, aucune pièce ne chevauche les cases \(m\) et \(m+1\). Le pavage se coupe alors en un pavage de longueur \(m\) et un pavage de longueur \(n\) : \(t_m t_n\) possibilités. Ensuite, un domino occupe les cases \(m\) et \(m+1\). Il reste alors un pavage des cases \(1\) à \(m – 1\) et un pavage des cases \(m + 2\) à \(m + n\) : \(t_{m-1} t_{n-1}\) possibilités. Ainsi \(t_{m+n} = t_m t_n + t_{m-1} t_{n-1}\). Pour \(m = n = 2\), on trouve \(2 \times 2 + 1 \times 1 = 5 = t_4\).

Point de méthode : un même objet combinatoire fournit ici une relation de récurrence, une formule avec des coefficients binomiaux et une identité d’addition. Classer les objets selon un critère bien choisi est la clé de chaque question.

Revenir aux énoncés des exercices

Pour aller plus loin en L1

• Le cours : récurrence et dénombrement, cours de maths en L1
• Les énoncés : exercices de maths en L1 sur récurrence et dénombrement
• À maîtriser avant : Logique, raisonnement et ensembles, Applications et relations binaires
• Chapitre précédent : Applications et relations binaires
• Chapitre suivant : Nombres complexes et trigonométrie
• Tester vos connaissances : QCM de maths en L1 par chapitre
• Le sommaire : tous les chapitres de maths de L1 et la licence de maths de L1 à L3