Voici le corrigé du contrôle de maths de L1 sur le thème : récurrence, sommes et coefficients binomiaux.
Ce corrigé montre la rédaction attendue en licence pour chaque récurrence : la propriété est nommée, l’initialisation vérifiée, puis l’hérédité démontrée avec l’hypothèse clairement utilisée. Les sommes sont calculées par télescopage, par symétrie des coefficients binomiaux et grâce à la formule du capitaine.
Dans le problème, un même nombre est obtenu deux fois : par un calcul avec le binôme de Newton, puis par une bijection vers des applications. Chaque exercice se termine par un barème détaillé qui sépare la méthode du résultat. Refaites les calculs de votre côté avant de lire la solution.
L’énoncé se trouve sur la page contrôle de maths l1 : récurrence, sommes et coefficients binomiaux.
| Exercice | Points |
| Exercice 1 : Question de cours : formule de Pascal et binôme de Newton | 4 points |
| Exercice 2 : Trois récurrences | 5 points |
| Exercice 3 : Calculs de sommes | 5 points |
| Exercice 4 : Problème : dénombrer des couples de parties | 6 points |
| Total | 20 points |
Exercice 1 : Question de cours : formule de Pascal et binôme de Newton (4 points)
-
Soit \(1 \leq\, k \leq\, n\). On met les deux fractions au même dénominateur \(k!\,(n-k+1)!\) :
\[\binom\,{n}{k-1} + \binom\,{n}{k} = \dfrac{n!}{(k-1)!\,(n-k+1)!} + \dfrac{n!}{k!\,(n-k)!} = \dfrac{n!\,k + n!\,(n-k+1)}{k!\,(n-k+1)!}.\]
Le numérateur vaut \(n!\,(n+1) = (n+1)!\). Donc \(\binom\,{n}{k-1} + \binom\,{n}{k} = \dfrac{(n+1)!}{k!\,(n+1-k)!} = \binom\,{n+1}{k}\).
-
Pour \(n \in \mathbb{N}\), notons \(\mathcal{P}(n)\) : « \((a+b)^n = \sum_{k=0}^{n} \binom\,{n}{k} a^k b^{n-k}\) ».
Initialisation : pour \(n = 0\), les deux membres valent \(1\), donc \(\mathcal{P}(0)\) est vraie.
Hérédité : soit \(n \in \mathbb{N}\) tel que \(\mathcal{P}(n)\) soit vraie. Alors
\[(a+b)^{n+1} = (a+b)\sum_{k=0}^{n} \binom\,{n}{k} a^k b^{n-k} = \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\) : elle devient \(\sum_{j=1}^{n+1} \binom\,{n}{j-1} a^j b^{n+1-j}\). On isole ensuite le terme \(j = n+1\) de la première somme et le terme \(k = 0\) de la seconde :
\[(a+b)^{n+1} = a^{n+1} + \sum_{k=1}^{n} (\binom\,{n}{k-1} + \binom\,{n}{k}) a^k b^{n+1-k} + b^{n+1}.\]
D’après la formule de Pascal, la parenthèse vaut \(\binom\,{n+1}{k}\). Or \(\binom\,{n+1}{0} = \binom\,{n+1}{n+1} = 1\), donc \((a+b)^{n+1} = \sum_{k=0}^{n+1} \binom\,{n+1}{k} a^k b^{n+1-k}\) : \(\mathcal{P}(n+1)\) est vraie.
Par récurrence, la formule du binôme est vraie pour tout \(n \in \mathbb{N}\). On a utilisé la commutativité du produit des complexes.
Barème : a) 1 point pour le calcul, 0,5 point pour la conclusion ; b) 0,5 point pour l’énoncé de la propriété et l’initialisation, 1 point pour le développement et le changement d’indice, 0,5 point pour l’usage de Pascal, 0,5 point pour la conclusion.
Exercice 2 : Trois récurrences (5 points)
-
Notons \(\mathcal{P}(n)\) l’égalité demandée. Pour \(n = 1\), on a \(1 = \dfrac{1 \times 2 \times 3}{6}\) : \(\mathcal{P}(1)\) est vraie.
Soit \(n \geq\, 1\) tel que \(\mathcal{P}(n)\) soit vraie. Alors
\[\sum_{k=1}^{n+1} k^2 = \dfrac{n(n+1)(2n+1)}{6} + (n+1)^2 = \dfrac{(n+1)(2n^2 + 7n + 6)}{6} = \dfrac{(n+1)(n+2)(2n+3)}{6}.\]
C’est exactement \(\mathcal{P}(n+1)\). Par récurrence, la formule est vraie pour tout \(n \in \mathbb{N}^*\).
-
Pour \(n \in \mathbb{N}\), notons \(\mathcal{Q}(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{Q}(0)\) est vraie.
Hérédité : supposons \(\mathcal{Q}(n)\). Alors \(u_{n+2} = 3(2^{n+1} + 1) – 2(2^n + 1) = 3 \times 2^{n+1} – 2^{n+1} + 1 = 2^{n+2} + 1\). Avec \(u_{n+1} = 2^{n+1} + 1\), on obtient \(\mathcal{Q}(n+1)\).
Par récurrence, \(u_n = 2^n + 1\) pour tout \(n \in \mathbb{N}\).
-
Pour \(n \geq\, 2\), notons \(\mathcal{R}(n)\) : « tout entier \(m\) tel que \(2 \leq\, m \leq\, n\) admet un diviseur premier ».
Initialisation : \(2\) est premier et se divise lui-même, donc \(\mathcal{R}(2)\) est vraie.
Hérédité : soit \(n \geq\, 2\) tel que \(\mathcal{R}(n)\) soit vraie. Il suffit d’étudier l’entier \(n+1\). S’il est premier, il est son propre diviseur premier. Sinon, il s’écrit \(n+1 = ab\) avec \(2 \leq\, a \leq\, n\). Par hypothèse de récurrence, \(a\) admet un diviseur premier \(p\), et comme \(a\) divise \(n+1\), \(p\) divise \(n+1\). Ainsi \(\mathcal{R}(n+1)\) est vraie.
Par récurrence forte, tout entier \(n \geq\, 2\) admet un diviseur premier.
Erreur fréquente : en b), n’initialiser qu’au rang \(0\). Une récurrence double exige les deux premiers termes.
Barème : a) 0,5 point pour l’initialisation, 1 point pour l’hérédité ; b) 0,5 point pour la propriété double et l’initialisation, 1 point pour le calcul de l’hérédité ; c) 0,5 point pour la propriété de récurrence forte, 0,5 point pour l’initialisation et le cas premier, 1 point pour le cas composé.
Exercice 3 : Calculs de sommes (5 points)
-
On a \(\dfrac{1}{k} – \dfrac{1}{k+1} = \dfrac{(k+1) – k}{k(k+1)} = \dfrac{1}{k(k+1)}\), donc \(\alpha = 1\) et \(\beta = -1\). La somme est alors télescopique :
\[\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}.\]
La somme vaut \(\dfrac{n}{n+1}\).
-
Le changement d’indice \(j = n-k\) parcourt aussi \(\{0, \ldots, n\}\). Par symétrie, \(\binom\,{n}{n-j} = \binom\,{n}{j}\), donc
\[S_n = \sum_{j=0}^{n} (n-j)\binom\,{n}{j} = n\sum_{j=0}^{n} \binom\,{n}{j} – S_n = n2^n – S_n,\]
car \(\sum_{j=0}^{n} \binom\,{n}{j} = (1+1)^n = 2^n\) d’après la formule du binôme. Ainsi \(2S_n = n2^n\). Donc \(S_n = n2^{n-1}\).
-
Pour \(1 \leq\, k \leq\, n\) : \(k\binom\,{n}{k} = \dfrac{k\,n!}{k!\,(n-k)!} = \dfrac{n \times (n-1)!}{(k-1)!\,(n-k)!} = n\binom\,{n-1}{k-1}\).
Le terme \(k = 0\) étant nul, on obtient, en posant \(j = k-1\) :
\[\sum_{k=0}^{n} k^2\binom\,{n}{k} = n\sum_{k=1}^{n} k\binom\,{n-1}{k-1} = n\sum_{j=0}^{n-1} (j+1)\binom\,{n-1}{j} = n(S_{n-1} + 2^{n-1}).\]
Comme \(n-1 \geq\, 1\), la question b) donne \(S_{n-1} = (n-1)2^{n-2}\). Donc la somme vaut \(n((n-1)2^{n-2} + 2 \times 2^{n-2})\). Ainsi \(\sum_{k=0}^{n} k^2\binom\,{n}{k} = n(n+1)2^{n-2}\). Vérification pour \(n = 2\) : \(0 + 2 + 4 = 6 = 2 \times 3 \times 1\).
-
Posons \(w_k = (k-1)k(k+1)\). Alors \(w_{k+1} – w_k = k(k+1)(k+2) – (k-1)k(k+1) = 3k(k+1)\). En sommant de \(k = 1\) à \(n\), les termes se télescopent :
\[3\sum_{k=1}^{n} k(k+1) = w_{n+1} – w_1 = n(n+1)(n+2) – 0.\]
Donc \(\sum_{k=1}^{n} k(k+1) = \dfrac{n(n+1)(n+2)}{3}\). Pour \(n = 2\), on retrouve \(2 + 6 = 8\).
Barème : a) 0,5 point pour la décomposition, 0,5 point pour le télescopage ; b) 1 point pour le changement d’indice et la symétrie, 0,5 point pour le résultat ; c) 0,5 point pour l’identité, 1 point pour le calcul de la somme ; d) 0,5 point pour le télescopage, 0,5 point pour le résultat.
Exercice 4 : Problème : dénombrer des couples de parties (6 points)
-
Une \(p\)-liste est un élément de \(E^p\) : il y a \(n\) choix pour chaque coordonnée, donc \(n^p\) listes. Pour une liste d’éléments distincts, il y a \(n\) choix pour le premier, \(n-1\) pour le second, et ainsi de suite jusqu’à \(n-p+1\) pour le dernier. On obtient \(n(n-1)\cdots(n-p+1) = \dfrac{n!}{(n-p)!}\) arrangements.
-
Fixons \(k \in \{0, \ldots, n\}\). Il y a \(\binom\,{n}{k}\) parties \(B\) de cardinal \(k\), et pour chacune, \(A\) est une partie quelconque de \(B\) : il y en a \(2^k\). En sommant sur \(k\), \(N = \sum_{k=0}^{n} \binom\,{n}{k} 2^k\).
Par la formule du binôme avec \(a = 2\) et \(b = 1\) : \(N = (2+1)^n\). Donc \(N = 3^n\).
-
À un couple \((A,B)\) avec \(A \subset B\), associons l’application \(\chi : E \to \{0,1,2\}\) définie par \(\chi(x) = 2\) si \(x \in A\), \(\chi(x) = 1\) si \(x \in B \setminus A\), et \(\chi(x) = 0\) si \(x \notin B\).
Cette correspondance est bijective : à une application \(\chi\), on associe réciproquement \(A = \chi^{-1}(\{2\})\) et \(B = \chi^{-1}(\{1,2\})\), qui vérifient \(A \subset B\). Or il y a \(3^n\) applications de \(E\) dans un ensemble à trois éléments. On retrouve \(N = 3^n\).
-
La condition \(A \cap B = \emptyset\) équivaut à \(A \subset \overline{B}\). L’application \((A,B) \mapsto (A, \overline{B})\) est donc une bijection des couples disjoints vers les couples \((A,C)\) tels que \(A \subset C\). Elle est d’ailleurs sa propre réciproque. Il y a donc \(3^n\) couples de parties disjointes.
-
On applique la formule à \(A\) et \(B \cup C\), puis à \(B\) et \(C\), en utilisant la distributivité \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\). Comme \((A \cap B) \cap (A \cap C) = A \cap B \cap C\), on obtient
\[\operatorname{card}(A \cup B \cup C) = \operatorname{card} A + \operatorname{card} B + \operatorname{card} C – \operatorname{card}(A \cap B) – \operatorname{card}(A \cap C) – \operatorname{card}(B \cap C) + \operatorname{card}(A \cap B \cap C).\]
Notons \(D_d\) l’ensemble des multiples de \(d\) entre \(1\) et \(300\) ; il contient \(\dfrac{300}{d}\) éléments lorsque \(d\) divise \(300\). Un entier est divisible par \(2\) et \(3\) si et seulement s’il l’est par \(6\), car \(2\) et \(3\) sont premiers entre eux ; de même pour les autres intersections. Ainsi :
\[\operatorname{card}(D_2 \cup D_3 \cup D_5) = 150 + 100 + 60 – 50 – 30 – 20 + 10 = 220.\]
Entre \(1\) et \(300\), il y a \(220\) entiers divisibles par \(2\), par \(3\) ou par \(5\).
Barème : a) 0,5 point par dénombrement ; b) 1 point pour la somme justifiée, 0,5 point pour le binôme ; c) 0,5 point pour la construction, 0,5 point pour la bijectivité ; d) 0,5 point pour l’équivalence, 0,5 point pour la bijection et le résultat ; e) 0,75 point pour la formule démontrée, 0,75 point pour le calcul.
Revenir à l’énoncé du contrôle
Après le corrigé du contrôle : récurrence, sommes et coefficients binomiaux
Pour consolider ce que le corrigé vous a appris, relisez le cours « Récurrence et dénombrement » en L1 puis entraînez-vous avec les exercices corrigés récurrence et dénombrement.
Retrouvez tous les contrôles de maths de L1 classés par chapitre, ou choisissez un autre niveau sur la page contrôles de maths du CP au post-bac.
