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

Exercice 1 : Somme des cubes par récurrence

Pour tout entier \(n \geq\, 1\), on pose \(S_n = \sum_{k=1}^{n} k^3\).

1. Calculez \(S_1\), \(S_2\), \(S_3\) et \(S_4\). Que remarquez-vous ?
2. Démontrez par récurrence que \(S_n = (\dfrac{n(n+1)}{2})^2\) pour tout \(n \geq\, 1\).
3. Déduisez-en que \(\sum_{k=1}^{n} k^3 = (\sum_{k=1}^{n} k)^2\).

Exercice 2 : Inégalité de Bernoulli

Soit \(x\) un réel tel que \(x \geq\, -1\).

1. Démontrez par récurrence que \((1 + x)^n \geq\, 1 + nx\) pour tout \(n \in \mathbb{N}\).
2. À quel endroit l’hypothèse \(x \geq\, -1\) intervient-elle ? Montrez que l’inégalité est fausse pour \(x = -4\) et \(n = 3\).
3. Déduisez-en que \((1 + \dfrac{1}{n})^n \geq\, 2\) et \((1 – \dfrac{1}{2n})^n \geq\, \dfrac{1}{2}\) pour tout \(n \geq\, 1\).

Exercice 3 : Une suite récurrente double

On définit la suite \((u_n)\) par \(u_0 = 2\), \(u_1 = 3\) et \(u_{n+2} = 3u_{n+1} – 2u_n\) pour tout \(n \in \mathbb{N}\).

1. Calculez \(u_2\), \(u_3\) et \(u_4\), puis conjecturez une expression de \(u_n\).
2. Démontrez par récurrence double que \(u_n = 2^n + 1\) pour tout \(n \in \mathbb{N}\).
3. Expliquez pourquoi une récurrence simple, avec la seule hypothèse sur \(u_n\), ne permet pas de conclure.

Exercice 4 : Récurrence forte et écritures binaires

1. Démontrez par récurrence forte que tout entier \(n \geq\, 1\) est une somme de puissances de \(2\) deux à deux distinctes. On distinguera les cas \(n\) pair et \(n\) impair.
2. Démontrez, toujours par récurrence forte, que cette écriture est unique à l’ordre près des termes.
3. Écrivez \(100\) et \(255\) sous cette forme.

Exercice 5 : Récurrences fautives

1. On « démontre » que, dans tout ensemble fini non vide de chevaux, tous les chevaux ont la même couleur. L’initialisation pour un cheval est évidente. Pour l’hérédité, on considère \(n+1\) chevaux. On retire le premier : les \(n\) restants ont la même couleur. On retire le dernier : les \(n\) autres ont aussi la même couleur. Comme les deux groupes ont des chevaux en commun, les \(n+1\) chevaux ont la même couleur. Localisez précisément l’erreur.
2. Montrez que la propriété \(\mathcal{P}(n)\) : « \(9\) divise \(10^n + 1\) » est héréditaire. Est-elle vraie pour un entier \(n\) ?
3. Vérifiez que \(n^2 + n + 41\) est premier pour \(n \in \{0, 1, 2, 3\}\). Calculez sa valeur pour \(n = 40\). Quelle leçon en tirez-vous ?

Exercice 6 : Bon ordre et descente infinie

1. Soit \(A\) une partie non vide et minorée de \(\mathbb{Z}\). En considérant \(\{a – m,\ a \in A\}\) pour un minorant \(m\), montrez que \(A\) possède un plus petit élément.
2. Montrez qu’une suite d’entiers naturels décroissante (au sens large) est stationnaire, c’est-à-dire constante à partir d’un certain rang.
3. On suppose qu’il existe des entiers \(x, y \geq\, 1\) tels que \(x^2 = 2y^2\). On choisit un tel couple avec \(x\) minimal. Montrez que \(x\) est pair, écrivez \(x = 2x_1\), puis obtenez une contradiction. Que peut-on en conclure pour \(\sqrt{2}\) ?

Exercice 7 : Changements d’indice et produits

Soit \(n \geq\, 1\). Calculez les expressions suivantes en justifiant chaque changement d’indice.

1. \(A_n = \sum_{k=1}^{n} (2k – 1)\).
2. \(B_n = \sum_{k=3}^{n+2} (k – 2)^2\).
3. \(C_n = \prod_{k=1}^{n} (2k)\), puis \(D_n = \prod_{k=1}^{n} (2k – 1)\) à l’aide de factorielles.
4. \(E_n = \prod_{k=1}^{n} 3^k\).

Exercice 8 : Sommes et produits télescopiques

Soit \(n \geq\, 2\).

1. Vérifiez que \(\dfrac{1}{k(k+1)(k+2)} = \dfrac{1}{2}(\dfrac{1}{k(k+1)} – \dfrac{1}{(k+1)(k+2)})\), puis calculez \(\sum_{k=1}^{n} \dfrac{1}{k(k+1)(k+2)}\) et sa limite.
2. Calculez \(\sum_{k=0}^{n} k \cdot k!\).
3. Calculez \(\sum_{k=1}^{n} \ln(1 + \dfrac{1}{k})\).
4. Calculez \(P_n = \prod_{k=2}^{n} (1 – \dfrac{1}{k^2})\) et sa limite quand \(n \to +\infty\).

Exercice 9 : Sommes doubles

Soit \(n \geq\, 1\). On rappelle que \(\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\).

1. Calculez \(\sum_{1 \leq\, i, j \leq\, n} (i + j)\).
2. Calculez \(T_n = \sum_{1 \leq\, i \leq\, j \leq\, n} i\) en sommant d’abord sur \(i\).
3. Déduisez-en \(M_n = \sum_{1 \leq\, i, j \leq\, n} \min(i, j)\) en séparant les couples selon que \(i < j\), \(i = j\) ou \(i > j\).

Exercice 10 : Somme des carrés par télescopage

Pour \(n \geq\, 1\), on note \(S_1 = \sum_{k=1}^{n} k\), \(S_2 = \sum_{k=1}^{n} k^2\) et \(S_3 = \sum_{k=1}^{n} k^3\).

1. Développez \((k+1)^3 – k^3\), puis sommez pour \(k\) allant de \(1\) à \(n\).
2. Déduisez-en l’expression de \(S_2\) sans utiliser de récurrence.
3. En utilisant de même \((k+1)^4 – k^4\), retrouvez l’expression de \(S_3\).

Exercice 11 : Somme arithmético-géométrique

Soit \(x\) un réel différent de \(1\) et, pour \(n \geq\, 1\), \(S_n = \sum_{k=1}^{n} k x^k\).

1. Calculez \(S_n – x S_n\) à l’aide d’un changement d’indice.
2. Déduisez-en que \(S_n = \dfrac{x(1 – (n+1)x^n + n x^{n+1})}{(1-x)^2}\).
3. Calculez \(\sum_{k=1}^{n} k\, 2^k\) et vérifiez le résultat pour \(n = 3\).
4. On admet que \(n x^n \to 0\) quand \(|x| < 1\). Déterminez la limite de \(\sum_{k=1}^{n} \dfrac{k}{2^k}\).

Exercice 12 : Cardinal d’une union et crible

1. Dans une promotion de \(40\) étudiants, \(25\) suivent l’option anglais, \(18\) l’option allemand et \(7\) les deux. Combien ne suivent aucune de ces deux options ?
2. Soit \(A\), \(B\), \(C\) trois parties finies d’un ensemble. En appliquant deux fois la formule pour deux parties, démontrez la formule du crible pour \(|A \cup B \cup C|\).
3. Soit \(E = [\![1, 1000]\!]\) et, pour \(d \geq\, 1\), \(A_d\) l’ensemble des multiples de \(d\) dans \(E\). La figure ci-dessous représente \(A_2\), \(A_3\) et \(A_5\). Justifiez que \(A_2 \cap A_3 = A_6\) et que \(|A_d|\) est la partie entière de \(\frac{1000}{d}\).
4. Combien d’entiers de \(E\) sont divisibles par \(2\), par \(3\) ou par \(5\) ? Combien ne le sont par aucun des trois ?

Exercice 13 : Applications, injections et parties

Soit \(E\) un ensemble à \(n\) éléments et \(F\) un ensemble à \(p\) éléments.

1. Justifiez qu’il y a \(p^n\) applications de \(E\) dans \(F\), puis \(\dfrac{p!}{(p-n)!}\) injections si \(n \leq\, p\).
2. Montrez que l’application \(X \mapsto \mathbf{1}_X\) est une bijection de \(\mathcal{P}(E)\) sur l’ensemble des applications de \(E\) dans \(\{0, 1\}\). Retrouvez \(|\mathcal{P}(E)|\).
3. Combien existe-t-il de relations binaires sur \(E\), c’est-à-dire de parties de \(E \times E\) ?
4. Construisez une bijection entre l’ensemble des couples \((A, B)\) de parties de \(E\) tels que \(A \subset B\) et l’ensemble des applications de \(E\) dans \(\{0, 1, 2\}\). Combien y a-t-il de tels couples ?

Exercice 14 : Codes et anagrammes

1. Combien existe-t-il de codes à \(4\) chiffres ? Combien ont leurs chiffres deux à deux distincts ? Combien comportent au moins un chiffre répété ?
2. Combien de mots de \(5\) lettres distinctes peut-on former avec l’alphabet de \(26\) lettres ?
3. Combien le mot MATHS a-t-il d’anagrammes ? Et le mot ANANAS ? Pour ce dernier, choisissez d’abord les positions des lettres A.
4. Six personnes, dont Alice et Bruno, s’assoient sur un banc de six places. Combien de dispositions placent Alice et Bruno côte à côte ?

Exercice 15 : Mains de cinq cartes

Un jeu de \(32\) cartes comporte \(4\) couleurs (pique, cœur, carreau, trèfle) et \(8\) hauteurs (7, 8, 9, 10, valet, dame, roi, as). Une main est une partie de \(5\) cartes.

1. Combien existe-t-il de mains ?
2. Combien de mains contiennent exactement deux as ?
3. Combien de mains contiennent au moins un cœur ?
4. Combien de mains sont formées de cinq cartes de la même couleur ?
5. Un full est formé de trois cartes d’une même hauteur et de deux cartes d’une autre hauteur. Combien y a-t-il de fulls ?

Exercice 16 : Chemins dans un quadrillage

Dans le quadrillage ci-dessous, on va du point \(O(0, 0)\) au point \(B(5, 3)\) par des pas unitaires vers la droite (D) ou vers le haut (H).

1. Montrez que les chemins de \(O\) à \(B\) sont en bijection avec les mots de \(8\) lettres comportant \(5\) lettres D et \(3\) lettres H. Déduisez-en leur nombre.
2. Combien de ces chemins passent par le point \(C(2, 1)\) ? Combien l’évitent ?
3. Plus généralement, on note \(c(m, n)\) le nombre de chemins de \(O\) à \((m, n)\). Donnez \(c(m, n)\). En classant les chemins selon leur dernier pas, retrouvez la formule de Pascal.

Exercice 17 : Binôme de Newton et coefficients

1. À l’aide du triangle de Pascal, développez \((2x – 1)^4\).
2. Déterminez le coefficient de \(x^3\) dans le développement de \((2x – 1)^7\).
3. Calculez \(\sum_{k=0}^{n} \binom\,{n}{k} 2^k\) et \(\sum_{k=0}^{n} (-1)^k \binom\,{n}{k} 3^{n-k}\).
4. Sans calculatrice, montrez que \(1{,}01^{10} \geq\, 1{,}1045\).

Exercice 18 : Identités par double comptage

Soit \(E\) un ensemble à \(n \geq\, 1\) éléments. On démontrera chaque identité par une bijection ou par un double comptage, sans utiliser la formule factorielle.

1. Montrez que \(\binom\,{n}{k} = \binom\,{n}{n-k}\) pour \(0 \leq\, k \leq\, n\).
2. En comptant les comités de \(k\) personnes munis d’un président, montrez que \(k \binom\,{n}{k} = n \binom\,{n-1}{k-1}\) pour \(1 \leq\, k \leq\, n\). Déduisez-en \(\sum_{k=0}^{n} k \binom\,{n}{k}\).
3. Fixons \(a \in E\). Montrez que \(X \mapsto X \,\Delta\, \{a\}\) échange les parties de cardinal pair et celles de cardinal impair. Combien \(E\) possède-t-il de parties de cardinal pair ?
4. En classant les paires \(\{i, j\}\) de \([\![1, n]\!]\) selon leur plus grand élément, montrez que \(\sum_{j=1}^{n} (j – 1) = \binom\,{n}{2}\).

Exercice 19 : Formule de Vandermonde

Soit \(a\), \(b\), \(p\) des entiers naturels.

1. Une assemblée compte \(a\) femmes et \(b\) hommes. En comptant de deux façons les délégations de \(p\) personnes, démontrez que \(\sum_{k=0}^{p} \binom\,{a}{k} \binom\,{b}{p-k} = \binom\,{a+b}{p}\).
2. Retrouvez ce résultat en identifiant le coefficient de \(x^p\) dans \((1+x)^a (1+x)^b\).
3. Déduisez-en que \(\sum_{k=0}^{n} \binom\,{n}{k}^2 = \binom\,{2n}{n}\).
4. À l’aide de la formule du capitaine, montrez que \(\sum_{k=0}^{n} k \binom\,{n}{k}^2 = n \binom\,{2n-1}{n-1}\) pour \(n \geq\, 1\). Vérifiez pour \(n = 2\).

Exercice 20 : Formule de la crosse de hockey

Soit \(p \leq\, n\) deux entiers naturels. On veut montrer que \(\sum_{k=p}^{n} \binom\,{k}{p} = \binom\,{n+1}{p+1}\).

1. Démontrez cette formule par récurrence sur \(n \geq\, p\), à l’aide de la formule de Pascal.
2. Démontrez-la de nouveau en classant les parties à \(p + 1\) éléments de \([\![1, n+1]\!]\) selon leur plus grand élément.
3. En écrivant \(k^2 = 2\binom\,{k}{2} + \binom\,{k}{1}\), retrouvez la valeur de \(\sum_{k=1}^{n} k^2\).

Exercice 21 : Surjections

Pour \(n, p \geq\, 1\), on note \(s(n, p)\) le nombre de surjections de \([\![1, n]\!]\) sur \([\![1, p]\!]\).

1. Calculez \(s(n, 1)\), \(s(n, n)\) et \(s(n, p)\) pour \(p > n\).
2. Montrez que \(s(n, 2) = 2^n – 2\).
3. Montrez que \(s(n+1, n) = \dfrac{n\,(n+1)!}{2}\).
4. Pour \(n \geq\, 2\) et \(p \geq\, 2\), démontrez que \(s(n, p) = p\big(s(n-1, p) + s(n-1, p-1)\big)\). Calculez \(s(4, 2)\) et \(s(4, 3)\).
5. En classant les applications de \([\![1, n]\!]\) dans \([\![1, p]\!]\) selon leur image, montrez que \(p^n = \sum_{k=1}^{p} \binom\,{p}{k} s(n, k)\). Vérifiez pour \(n = 3\) et \(p = 2\).

Exercice 22 : Problème : pavages et nombres de Fibonacci

On pave une bande de longueur \(n\) et de hauteur \(1\) avec des carrés \(1 \times 1\) (notés C) et des dominos \(2 \times 1\) posés à plat (notés D). On note \(t_n\) le nombre de pavages, avec \(t_0 = 1\). La figure ci-dessous montre les pavages de la bande de longueur \(4\).

1. Donnez \(t_1\), \(t_2\), \(t_3\) et \(t_4\).
2. En classant les pavages selon la dernière pièce, montrez que \(t_n = t_{n-1} + t_{n-2}\) pour \(n \geq\, 2\). Calculez \(t_5\) et \(t_6\).
3. En classant les pavages selon leur nombre \(k\) de dominos, montrez que \(t_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom\,{n-k}{k}\). Vérifiez pour \(n = 6\).
4. Démontrez par récurrence double que \((\frac{3}{2})^{n-1} \leq\, t_n \leq\, (\frac{7}{4})^n\) pour tout \(n \geq\, 1\).
5. Montrez que \(\sum_{k=0}^{n} t_k = t_{n+2} – 1\) par télescopage.
6. Pour \(m, n \geq\, 1\), montrez que \(t_{m+n} = t_m t_n + t_{m-1} t_{n-1}\) en regardant si une pièce chevauche les cases \(m\) et \(m+1\).

Le corrigé des exercices

Chaque exercice est corrigé en détail, question par question, sur la page suivante.

Pour aller plus loin en L1

• Le cours : récurrence et dénombrement, cours de maths en L1
• À 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