Reformulation. Il s'agit de montrer que tout entier $n \ge 8$ s'écrit $n = 3a + 5b$ avec $a, b \in \mathbb{N}$.

Pourquoi trois cas de base. L'hérédité naturelle consiste à dire : si $n - 3$ est payable, alors $n$ l'est, en ajoutant une pièce de 3. Mais cette hérédité ne couvre que les $n \ge 11$, puisqu'elle exige $n - 3 \ge 8$. Il faut donc amorcer trois valeurs consécutives, de façon que tout entier plus grand retombe sur l'une d'elles :

$8 = 3 + 5, \qquad 9 = 3 + 3 + 3, \qquad 10 = 5 + 5.$

Hérédité. Soit $n \ge 11$ et supposons la propriété vraie pour $n - 3$. Comme $8 \le n - 3 < n$, l'hypothèse de récurrence s'applique : $n - 3 = 3a + 5b$. Alors

$n = 3a + 5b + 3 = 3(a + 1) + 5b,$

qui est bien une combinaison de pièces de 3 et 5. Par récurrence généralisée sur $n$, la propriété est vraie pour tout $n \ge 8$. $\blacksquare$

La leçon sur le pas d'induction. L'erreur classique est de n'amorcer qu'un seul cas de base ($8 = 3 + 5$) et de conclure pour tout $n \ge 8$ : le raisonnement ne couvre alors que $8, 11, 14, \dots$ et laisse $9, 10, 12, \dots$ sans preuve. La règle générale : si l'hérédité fait appel à $n - k$, il faut $k$ cas de base consécutifs. Ici $k = 3$, donc trois cas de base.

Vérification numérique. $8 = 3+5$, $9 = 3+3+3$, $10 = 5+5$, $11 = 3+3+5$, $12 = 3+3+3+3$, $13 = 3+5+5$, $14 = 3+3+3+5$. Les valeurs $1$ à $7$ (sauf $3$ et $5$) ne sont effectivement pas payables : le seuil de 8 est optimal.

1. $P(2)$ est vraie : deux points distincts du plan déterminent toujours une droite, donc ils sont alignés. Le cas de base est donc correct.

2. Le pas d'induction est faux en tant qu'énoncé général. Comptons les points communs à $d_1$ et $d_2$. La droite $d_1$ passe par $p_1, \dots, p_n$, la droite $d_2$ par $p_2, \dots, p_{n+1}$. Les points communs aux deux ensembles sont $p_2, \dots, p_n$, c'est-à-dire $n - 1$ points, et non $n$ comme l'affirme l'énoncé.

Cette correction d'un point change tout. Deux droites distinctes ont au plus un point commun. Donc pour conclure $d_1 = d_2$, il faut que $n - 1 \ge 2$, c'est-à-dire $n \ge 3$. L'implication $P(n) \Rightarrow P(n+1)$ n'est donc démontrée que pour $n \ge 3$ ; elle est sans fondement pour $n = 2$.

3. Non, on ne peut pas conclure. L'induction exige que le cas de base soit assez « bas » pour que l'hérédité s'y accroche. Ici l'hérédité démarre à $n = 3$ : il faudrait donc disposer de $P(3)$ comme cas de base. Or $P(3)$ est fausse : trois points non alignés du plan le contredisent (par exemple $(0,0)$, $(1,0)$, $(0,1)$). L'induction ne peut pas démarrer, et la conclusion $\forall n\, P(n)$ tombe.

La leçon. Une induction ne vaut que par la jonction du cas de base et de l'hérédité : il ne suffit pas que chacune des deux étapes soit vraie séparément, il faut qu'elles s'enchaînent sans trou. Le symptôme à surveiller est exactement celui-ci : une hérédité prouvée sous une condition sur $n$ ($n \ge 3$) et un cas de base plus petit ($n = 2$). C'est le même défaut que dans le sophisme « tous les chevaux ont la même couleur ».

Ce qu'il faut prouver. La propriété $P(a,b)$ : « l'appel PGCD(a,b) termine et renvoie $\gcd(a,b)$ », pour tous entiers $a, b \ge 0$ non tous deux nuls.

Les deux faits arithmétiques. On utilise les deux identités classiques, valables pour $a \ge b \ge 0$ :

$\gcd(a, 0) = a, \qquad \gcd(a, b) = \gcd(a - b, b).$

La seconde exprime que l'ensemble des diviseurs communs de $a$ et $b$ est exactement celui de $a-b$ et $b$ : tout $d$ divisant $a$ et $b$ divise $a - b$ ; réciproquement tout $d$ divisant $a-b$ et $b$ divise $(a-b)+b = a$. Les deux entiers ont donc le même PGCD.

Terminaison. Le point délicat est la première ligne : l'appel PGCD(b, a) conserve la somme $a + b$. Une induction simple sur $a+b$ ne suffit donc pas, puisque la mesure ne décroît pas sur ce cas. On prend une mesure plus fine, le couple

$\mu(a, b) = \big(a + b,\; [\,b \gt a\,]\big) \in \mathbb{N} \times \{0,1\},$

ordonné lexicographiquement (on compare d'abord les sommes, puis l'indicateur). Vérifions que chaque appel récursif diminue strictement $\mu$ :

• Cas $b \gt a$ : l'appel passe à $(b, a)$. La somme est inchangée, mais l'indicateur passe de $1$ à $0$ (car $a \lt b$). Donc $\mu$ décroît strictement, et l'appel suivant ne peut pas reprendre cette branche.
• Cas $b \le a$ et $b \neq 0$ : l'appel passe à $(a-b, b)$, de somme $a$, strictement inférieure à $a + b$ puisque $b \gt 0$. Donc $\mu$ décroît strictement.

Comme $\mathbb{N} \times \{0,1\}$ muni de l'ordre lexicographique est bien fondé (il n'existe pas de suite infinie strictement décroissante), il n'y a pas de chaîne d'appels infinie : l'algorithme termine. Le cours utilise exactement ce vocabulaire : un ordre bien fondé est un ordre sans suite infinie strictement décroissante, et c'est lui qui autorise l'induction généralisée.

Correction (validation partielle). On raisonne par induction généralisée sur $\mu(a,b)$.

• Cas $b = 0$ : l'algorithme renvoie $a$. Or $\gcd(a, 0) = a$ : la sortie est correcte.
• Cas $b \gt a$ : l'algorithme renvoie PGCD(b, a). Par hypothèse d'induction appliquée à $(b,a)$, dont la mesure est strictement plus petite, cet appel renvoie $\gcd(b, a)$. Or le PGCD est symétrique, $\gcd(b,a) = \gcd(a,b)$ : la sortie est correcte.
• Cas $b \le a$ et $b \neq 0$ : l'algorithme renvoie PGCD(a-b, b). Par hypothèse d'induction, cet appel renvoie $\gcd(a-b, b)$, qui vaut $\gcd(a,b)$ par l'identité établie plus haut : la sortie est correcte.

Les trois cas épuisent les situations possibles (si $b \neq 0$ et $b \le a$, le troisième cas s'applique). L'algorithme termine et renvoie le PGCD : il est correct. $\blacksquare$

Vérification. PGCD(12, 18) : $b \gt a$ donc appel de PGCD(18, 12) ; puis PGCD(6, 12) par soustraction, puis PGCD(12, 6) par échange, puis PGCD(6, 6), puis PGCD(0, 6) ; $b = 0$ donc renvoie $6 = \gcd(12,18)$. Correct.

Ce qu'il faut retenir. Le cas de base n'est pas ici « $a = b = 0$ » mais « $b = 0$ », et la terminaison se prouve par une mesure bien fondée — pas seulement par « la somme diminue ». C'est le prix à payer pour le premier test qui échange les arguments.

1. Définitions inductives. La structure de l'ensemble impose la forme des définitions : une clause pour la base ($\emptyset$), une clause pour l'étape inductive (le nœud $(\cdot, g, d)$).

$h(\emptyset) = 0, \qquad h\big((\cdot,g,d)\big) = 1 + \max\big(h(g), h(d)\big)$

$n(\emptyset) = 0, \qquad n\big((\cdot,g,d)\big) = 1 + n(g) + n(d)$

$f(\emptyset) = 0, \qquad f\big((\cdot,g,d)\big) = \begin{cases} 1 & \text{si } g = d = \emptyset \ \text{(le nœud est une feuille)} \\ f(g) + f(d) & \text{sinon}\end{cases}$

La hauteur du nœud racine ajoute 1 au maximum des hauteurs des sous-arbres ; le nombre de nœuds ajoute 1 aux effectifs des deux sous-arbres ; le nombre de feuilles se transmet par les sous-arbres non vides, une feuille étant un nœud dont les deux sous-arbres sont vides.

2. Bornes. On raisonne par induction structurelle, c'est-à-dire par le principe d'induction sur l'ensemble défini inductivement : la propriété est vérifiée sur la base, puis on montre que si elle est vraie de $g$ et de $d$, elle est vraie de $(\cdot,g,d)$.

Borne sur les nœuds. Pour $x = \emptyset$ : $n(\emptyset) = 0$ et $2^{h(\emptyset)} - 1 = 2^0 - 1 = 0$, donc l'égalité tient. Pour $x = (\cdot,g,d)$ : par hypothèse d'induction, $n(g) \le 2^{h(g)} - 1$ et $n(d) \le 2^{h(d)} - 1$, d'où

$n(x) = 1 + n(g) + n(d) \le 1 + \big(2^{h(g)} - 1\big) + \big(2^{h(d)} - 1\big) = 2^{h(g)} + 2^{h(d)} - 1.$

Or $h(g) \le h(x) - 1$ et $h(d) \le h(x) - 1$ par définition de $h(x) = 1 + \max(h(g),h(d))$, donc $2^{h(g)} \le 2^{h(x)-1}$ et $2^{h(d)} \le 2^{h(x)-1}$. Il vient

$n(x) \le 2 \cdot 2^{h(x)-1} - 1 = 2^{h(x)} - 1. \qquad \blacksquare$

Borne sur les feuilles. Pour $x = \emptyset$ : $f(\emptyset) = 0$ et la borne s'écrit $0 \le 2^{-1}$, ce qui n'a pas de sens : on énonce donc la propriété pour $x \neq \emptyset$, ce qui impose $h(x) \ge 1$. Pour une feuille $x = (\cdot,\emptyset,\emptyset)$ : $f(x) = 1$ et $2^{h(x)-1} = 2^0 = 1$ : l'égalité tient. Pour $x = (\cdot,g,d)$ non feuille, les deux sous-arbres sont non vides, donc $h(g) \ge 1$ et $h(d) \ge 1$, et l'hypothèse d'induction s'applique :

$f(x) = f(g) + f(d) \le 2^{h(g)-1} + 2^{h(d)-1} \le 2 \cdot 2^{h(x)-2} = 2^{h(x)-1}. \qquad \blacksquare$

3. $AB$ est inductif. $AB$ est défini inductivement par une base ($\emptyset$) et un ensemble fini d'opérations ($g, d \mapsto (\cdot,g,d)$, d'arité 2). Le cours énonce qu'un ensemble défini inductivement est inductif, c'est-à-dire qu'il est muni d'un bon ordre permettant d'y appliquer le principe d'induction structurelle. C'est précisément ce principe qui vient d'être utilisé en 2.

Vérification. Pour l'arbre parfait de hauteur 3 (racine, 2 enfants, 4 petits-enfants), $n = 7 = 2^3 - 1$ : la borne sur les nœuds est atteinte. Ses feuilles sont au nombre de $4 = 2^{3-1}$ : la borne sur les feuilles est atteinte aussi. Les deux inégalités sont donc optimales, et l'arbre parfait est l'unique cas d'égalité.

Lien avec la complexité. La borne $n \le 2^h - 1$ se réécrit $h \ge \log_2(n+1)$ : la hauteur d'un arbre à $n$ nœuds ne peut pas descendre sous $\log_2(n+1)$. C'est cette inégalité qui rend crédible la promesse d'une recherche en $O(\log n)$ dans un arbre binaire de recherche équilibré — et qui explique que cette promesse tombe si l'arbre dégénère en liste, cas où $h = n$.

Chaque boucle parcourt exactement $n$ valeurs. Les trois boucles étant imbriquées, leurs nombres d'itérations se multiplient : le corps de la boucle la plus interne est exécuté

$n \times n \times n = n^{3}$

fois. À la sortie, compteur vaut donc $n^3$.

Le réflexe de comptage. Boucles successives (l'une après l'autre) : les coûts s'additionnent. Boucles imbriquées : les coûts se multiplient. C'est la règle qui transforme un programme en formule, et elle est la base de toute analyse de complexité avant même d'introduire la notation grand-O.

Vérification. Pour $n = 2$, les triplets $(i,j,k)$ parcourus sont $2^3 = 8$ : $(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)$. Pour $n = 3$, $27$. Le décompte est bien cubique.

Ordre de grandeur. En comptant une opération par tour, ce programme coûte $n^3$ opérations. Doubler $n$ multiplie le travail par $8$ : c'est la signature d'un algorithme cubique, à éviter dès que $n$ dépasse quelques milliers.

Traduire un chemin en mot. Un itinéraire monotone de $S$ vers $D$ est entièrement décrit par la suite de ses déplacements élémentaires : un pas vers la droite (notons-le $D$) ou un pas vers le haut (notons-le $H$). Parcourir la grille de $p$ mailles en largeur et $q$ mailles en hauteur exige exactement

$p \text{ pas vers la droite et } q \text{ pas vers le haut},$

soit $n = p + q$ pas au total. Réciproquement, tout mot de $n$ lettres sur l'alphabet $\{D, H\}$ comportant $p$ occurrences de $D$ et $q$ occurrences de $H$ décrit un et un seul itinéraire monotone. Il y a donc bijection entre les itinéraires et ces mots.

Compter les mots. Choisir un tel mot, c'est choisir les $p$ positions occupées par les $D$ parmi les $n = p+q$ positions disponibles : les $H$ occupent automatiquement les autres. Le nombre cherché est donc le coefficient binomial

$\binom{p+q}{p} = \binom{p+q}{q} = \frac{(p+q)!}{p!\,q!}.$

Vérification. Pour $p = q = 1$ (une maille en largeur, une en hauteur), la formule donne $\binom{2}{1} = 2$, et l'on voit bien les deux chemins : $DH$ et $HD$. Pour $p = 2, q = 1$ : $\binom{3}{2} = 3$, soit $DDH$, $DHD$, $HDD$. Le résultat est cohérent.

Pourquoi c'est un résultat de combinatoire, pas d'énumération. Le nombre de chemins croît de façon exponentielle avec $p + q$ : pour $p = q = 12$ il vaut déjà $\binom{24}{12} = 2\,704\,156$, et il dépasse le milliard dès $p = q = 18$. L'énumération exhaustive coûterait précisément ce nombre d'opérations. Compter au lieu d'énumérer est exactement le geste que le cours met en avant : « avant d'énumérer, il est prudent de dénombrer ».

1. Graphes maximaux. $G_1$ est un sommet isolé (aucune arête, $a(1) = 0$). $G_2$ est un segment : une arête reliant $s_1$ et $s_2$ ($a(2) = 1$). $G_3$ est un triangle : les trois arêtes $\{s_1,s_2\}$, $\{s_1,s_3\}$, $\{s_2,s_3\}$ ($a(3) = 3$). Ce sont les graphes complets sur $1$, $2$ et $3$ sommets.

2. Nombre maximal d'arêtes. Une arête non orientée est une paire de sommets distincts, donc une partie à 2 éléments de $S_n$. Le nombre maximal d'arêtes est le nombre de ces paires :

$a(n) = \binom{n}{2} = \frac{n(n-1)}{2}.$

Justification : il y a $n$ choix pour le premier sommet et $n-1$ pour le second, soit $n(n-1)$ couples ordonnés ; chaque arête non orientée $\{s_i,s_j\}$ est comptée deux fois, une fois comme $(s_i,s_j)$ et une fois comme $(s_j,s_i)$. D'où $n(n-1)/2$. Aucun graphe simple ne peut faire mieux, puisqu'il ne peut contenir que des paires distinctes de $S_n$.

3. Nombre de graphes. Un graphe non orienté sur $S_n$ est déterminé par la donnée de son ensemble d'arêtes, c'est-à-dire par le choix d'une partie de l'ensemble des $a(n)$ paires possibles. Il y a donc autant de graphes que de parties de cet ensemble, soit

$g(n) = 2^{a(n)} = 2^{\,n(n-1)/2}.$

4. Application numérique. $a(3) = 3 \times 2 / 2 = 3$ et $g(3) = 2^3 = 8$. Les huit graphes sur $S_3$ correspondent aux huit parties de l'ensemble des trois arêtes possibles : le graphe vide, les trois graphes à une arête, les trois graphes à deux arêtes, et le triangle.

Ce que ce résultat enseigne. Le nombre de graphes sur $n$ sommets est $2^{n(n-1)/2}$ : pour $n = 10$ cela fait déjà $2^{45} \approx 3{,}5 \times 10^{13}$, et pour $n = 30$, environ $2^{435} \approx 10^{131}$. Aucun algorithme ne peut énumérer tous les graphes au-delà de quelques dizaines de sommets : c'est exactement le mur exponentiel que décrit le cours de dénombrement, et la raison pour laquelle on cherche des propriétés à prouver plutôt que des cas à parcourir.

Notons $x_1, x_2, x_3, x_4$ les quatre chiffres de la combinaison. L'énoncé se traduit en un système de contraintes arithmétiques :

$x_1 + x_2 + x_3 + x_4 = 10, \qquad x_i \ge 1 \ \text{(premier cas)}, \qquad x_i \ge 0 \ \text{(second cas)}.$

Le cours fournit exactement l'outil adapté : le nombre de solutions entières de $x_1 + \dots + x_n = p$ avec $x_i \ge 0$ est le nombre de combinaisons avec répétition de $p$ éléments pris parmi $n$, soit

$K_n^{p} = \binom{n + p - 1}{n - 1}.$

Cas 1 — aucun chiffre nul. On se ramène au cas positif ou nul par le changement de variable $y_i = x_i - 1$, qui est légitime car $x_i \ge 1 \iff y_i \ge 0$. En substituant dans l'équation,

$(y_1 + 1) + (y_2 + 1) + (y_3 + 1) + (y_4 + 1) = 10 \quad\Longrightarrow\quad y_1 + y_2 + y_3 + y_4 = 6.$

Il reste 4 variables pour un total de 6, donc

$\binom{6 + 4 - 1}{4 - 1} = \binom{9}{3} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84.$

Cas 2 — les chiffres peuvent être nuls. On applique la formule directement, avec $n = 4$ et $p = 10$ :

$\binom{10 + 4 - 1}{4 - 1} = \binom{13}{3} = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = 286.$

Réponse. Mme Joublietout doit essayer 84 combinaisons dans le premier cas et 286 dans le second. $\blacksquare$

Le point à ne pas manquer. Le changement de variable porte sur chaque variable : retirer 1 à chacune retire 4 au total, et c'est le second membre qui doit absorber ce retrait ($10 \to 6$). Oublier de retirer 4 donne le même $\binom{13}{3} = 286$ dans les deux cas — un signe infaillible que l'erreur a été commise, puisque les deux questions n'ont aucune raison d'avoir la même réponse.

Vérification. Dans le cas 1, les quadruplets ordonnés d'entiers $\ge 1$ de somme 10 se répartissent en familles : $(1,1,1,7)$ et ses $4$ permutations, $(1,1,2,6)$ et ses $12$ permutations, etc. Le total de 84 est de l'ordre de grandeur attendu, et il est bien inférieur au total $286$ du cas 2, comme il se doit puisqu'on y impose une contrainte de plus.

Pourquoi on parle de récurrence complète. Le terme $u_n$ dépend de tous les termes précédents, pas d'un nombre fixé d'entre eux : le cours appelle cela une relation de récurrence complète. La technique associée est la réduction d'ordre par différence : on écrit la relation au rang $n+1$ et on retranche celle du rang $n$, ce qui élimine la somme.

Étape 1 — écrire la relation au rang suivant.

$u_{n+1} = 3 \sum_{k=0}^{n} u_k + 1.$

Étape 2 — isoler la somme. En séparant le dernier terme de la somme :

$u_{n+1} = 3 \sum_{k=0}^{n-1} u_k + 3u_n + 1.$

Or la relation au rang $n$ donne $3\sum_{k=0}^{n-1} u_k = u_n - 1$. En substituant :

$u_{n+1} = (u_n - 1) + 3u_n + 1 = 4u_n.$

Étape 3 — résoudre la récurrence d'ordre 1 obtenue. Pour tout $n \ge 1$, $u_{n+1} = 4u_n$, donc la suite est géométrique de raison 4 à partir de $u_1$ :

$u_n = 4^{\,n-1} u_1.$

Il reste à calculer $u_1$ par la relation d'origine : $u_1 = 3u_0 + 1 = 3 \times 1 + 1 = 4$. D'où

$u_n = 4^{\,n-1} \times 4 = 4^{\,n} \quad \text{pour tout } n \ge 1,$

et cette formule vaut aussi pour $n = 0$ puisque $4^0 = 1 = u_0$. Donc

$\boxed{u_n = 4^{\,n} \ \text{pour tout } n \in \mathbb{N}.}$

Vérification. $u_0 = 1 = 4^0$. $u_1 = 3u_0 + 1 = 4 = 4^1$. $u_2 = 3(u_0 + u_1) + 1 = 3 \times 5 + 1 = 16 = 4^2$. $u_3 = 3(1 + 4 + 16) + 1 = 3 \times 21 + 1 = 64 = 4^3$. La formule est confirmée sur quatre rangs.

La méthode en une phrase. Pour une récurrence complète, on écrit la relation au rang $n+1$, on y reconnaît l'expression du rang $n$ et on soustrait : la somme disparaît et il ne reste qu'une récurrence d'ordre 1, que l'on sait résoudre.

1. Suite arithmétique déguisée ($a(n) = 1$, $b(n) = 2n$). On déroule la récurrence en sommant les équations, technique du cours :

En additionnant membre à membre, les termes intermédiaires s'annulent et il reste

$u_n = u_0 + 2\sum_{k=1}^{n} k = 1 + 2 \cdot \frac{n(n+1)}{2} = 1 + n(n+1).$

Donc $u_n = n^2 + n + 1$. Vérification : $u_1 = 1 + 2 = 3$, et la formule donne $1 + 2 = 3$ ; $u_2 = 3 + 4 = 7$, et la formule donne $4 + 2 + 1 = 7$. Correct.

2. Suite géométrique translatée ($a$, $b$ constants). On divise par la puissance qui rend la relation homogène. Posons $v_n = u_n + 1$ : alors

$v_n = u_n + 1 = 2u_{n-1} + 2 = 2(u_{n-1} + 1) = 2v_{n-1},$

et $v_0 = u_0 + 1 = 2$. Donc $(v_n)$ est géométrique de raison 2 : $v_n = 2 \cdot 2^n = 2^{n+1}$, d'où

$u_n = 2^{\,n+1} - 1.$

Vérification : $u_1 = 2u_0 + 1 = 3$ et $2^2 - 1 = 3$ ; $u_2 = 2 \times 3 + 1 = 7$ et $2^3 - 1 = 7$. C'est aussi le coût des tours de Hanoï, que le cours résout exactement de cette façon : $T(0) = 0$, $T(n) = 2T(n-1) + 1$ donne $T(n) = 2^n - 1$.

3. Récurrence homogène d'ordre 2 à coefficients constants. On applique la technique de l'équation caractéristique. On cherche des solutions de la forme $u_n = \alpha^n$ : en substituant dans $u_n = 4u_{n-1} - 3u_{n-2}$,

$\alpha^n = 4\alpha^{n-1} - 3\alpha^{n-2} \quad\Longrightarrow\quad \alpha^2 = 4\alpha - 3 \quad\Longrightarrow\quad \alpha^2 - 4\alpha + 3 = 0.$

Le discriminant vaut $\Delta = 16 - 12 = 4$, d'où deux racines réelles distinctes

$\alpha_1 = \frac{4 - 2}{2} = 1, \qquad \alpha_2 = \frac{4 + 2}{2} = 3.$

Le cours donne alors la solution générale $u_n = c_1 \alpha_1^n + c_2 \alpha_2^n$, soit $u_n = c_1 + c_2 \cdot 3^n$. Les conditions initiales fixent $c_1$ et $c_2$ :

$\begin{cases} u_0 = c_1 + c_2 = 0 \\ u_1 = c_1 + 3c_2 = 1 \end{cases}$

Par différence : $2c_2 = 1$, donc $c_2 = \tfrac12$ et $c_1 = -\tfrac12$. D'où

$\boxed{u_n = \frac{3^{\,n} - 1}{2}}.$

Vérification : $u_0 = 0$, $u_1 = (3-1)/2 = 1$, $u_2 = 4u_1 - 3u_0 = 4$ et $(9-1)/2 = 4$, $u_3 = 4 \times 4 - 3 \times 1 = 13$ et $(27-1)/2 = 13$. Correct.

Les trois cas à reconnaître. Le cours classe les récurrences linéaires d'ordre 1 selon $a(n)$ et $b(n)$ : $a(n) = 1$ avec $b$ constant donne une suite arithmétique (cas 1, avec $b$ dépendant de $n$) ; $a(n)$ constant donne une suite géométrique, éventuellement translatée (cas 2). Pour l'ordre 2 homogène à coefficients constants, l'équation caractéristique remplace tout : deux racines réelles distinctes donnent $c_1\alpha_1^n + c_2\alpha_2^n$, une racine double donne $\alpha^n(c_1 + c_2 n)$.

Méthode de sommation. On écrit la relation aux rangs successifs et on additionne, exactement comme pour une récurrence d'ordre 1 avec $a(n) = 1$ :

En additionnant membre à membre, les termes $c(n-1), \dots, c(3)$ s'annulent deux à deux et il reste

$c(n) = c(2) + \sum_{k=4}^{n+1} k.$

Évaluation de la somme. La somme des entiers de 4 à $n+1$ vaut

$\sum_{k=4}^{n+1} k = \frac{(n+1)(n+2)}{2} - (1 + 2 + 3) = \frac{(n+1)(n+2)}{2} - 6 = \frac{n^2 + 3n + 2 - 12}{2} = \frac{n^2 + 3n - 10}{2}.$

D'où

$c(n) = 3 + \frac{n^2 + 3n - 10}{2} = \frac{n^2 + 3n - 4}{2}.$

Vérification. $c(2) = (4 + 6 - 4)/2 = 3$ : la condition initiale est respectée. $c(3) = c(2) + 4 = 7$ et la formule donne $(9 + 9 - 4)/2 = 7$. $c(4) = 7 + 5 = 12$ et $(16 + 12 - 4)/2 = 12$. $c(5) = 12 + 6 = 18$ et $(25 + 15 - 4)/2 = 18$. La formule est confirmée.

Interprétation. $c(n) = \frac{n^2 + 3n - 4}{2}$ est un polynôme de degré 2 : le tri rapide est quadratique dans le pire cas, ce que l'on écrit $c(n) = \Theta(n^2)$. Le cas se produit lorsque le pivot est systématiquement le plus petit ou le plus grand élément, si bien que la partition ne retire qu'un seul élément à chaque tour : la profondeur de récursion devient $n$ au lieu de $\log_2 n$. C'est pourquoi les implémentations sérieuses choisissent le pivot au hasard ou en médiane de trois.

Vérification sur le listing du TD. Le pseudo-code de la feuille appelle trirapide(d, pivot-1) puis trirapide(pivot+1, d). La seconde borne devrait être f (la borne droite de la partition) : telle qu'elle est écrite, la récursion de droite repart sur l'intervalle initial. Le listing comporte donc une coquille ; la borne correcte est trirapide(pivot+1, f).

1. Calcul de $T(4)$. Énumérons les tas commençant par 4, en classant selon le deuxième élément.

• Tas réduit à $(4)$ : 1 possibilité.
• Deuxième élément 3 : la suite des éléments suivants est un tas commençant par 3, soit $(3)$ tout court, ou $3$ suivi d'un tas commençant par 1 ou 2. Cela donne $(4,3)$, $(4,3,2)$, $(4,3,2,1)$, $(4,3,1)$ : 4 possibilités, soit $T(3)$.
• Deuxième élément 2 : $(4,2)$ et $(4,2,1)$ : 2 possibilités, soit $T(2)$.
• Deuxième élément 1 : $(4,1)$ : 1 possibilité, soit $T(1)$.

Au total $T(4) = 1 + 4 + 2 + 1 = 8$.

2. Relation de récurrence. Généralisons l'observation précédente. Un tas commençant par $n$ est :

• soit la séquence réduite $(n)$ : 1 possibilité ;
• soit $n$ suivi d'un tas commençant par un élément $x$ avec $1 \le x \le n-1$ : $T(x)$ possibilités pour chaque $x$.

D'où, pour $n \ge 1$,

$T(n) = 1 + \sum_{x=1}^{n-1} T(x) = \sum_{x=0}^{n-1} T(x),$

la dernière égalité utilisant $T(0) = 1$, que le premier cas $(n)$ réalise précisément. Vérification : $T(1) = T(0) = 1$ (seul le tas $(1)$) ; $T(2) = T(0) + T(1) = 2$ (les tas $(2)$ et $(2,1)$) ; $T(3) = 1 + 1 + 2 = 4$, conforme à l'énoncé.

3. Résolution. La relation $T(n) = \sum_{x=0}^{n-1} T(x)$ est une récurrence complète, du même type que l'exercice 9. On l'écrit au rang $n+1$ et on soustrait :

$T(n+1) = \sum_{x=0}^{n} T(x) = \sum_{x=0}^{n-1} T(x) + T(n) = T(n) + T(n) = 2\,T(n).$

La suite est donc géométrique de raison 2 à partir de $T(0) = 1$ :

$T(n) = 2^{\,n-1} \ \text{pour } n \ge 1, \qquad T(0) = 1.$

Vérification : $T(1) = 1 = 2^0$, $T(2) = 2 = 2^1$, $T(3) = 4 = 2^2$, $T(4) = 8 = 2^3$. Conforme.

Ce que le résultat dit. Les tas de sable à premier élément $n$ sont en bijection avec les parties de $\{1, \dots, n-1\}$ : un tas est déterminé par le choix de l'ensemble des positions occupées, ce qui explique le $2^{n-1}$ et fait écho au comptage des parties d'un ensemble à $n-1$ éléments. Le comptage combinatoire et la récurrence disent ici la même chose.