LICENCE Structures Discrètes – T.D.

Induction

Exercice 1 Montrer que, pour n ≥ 2,

A1 ∪ A2 ∪ · · · ∪ An = A1 ∩ A2 ∩ · · · ∩ An
A1 ∩ A2 ∩ · · · ∩ An = A1 ∪ A2 ∪ · · · ∪ An

(Lois de Morgan généralisées) ♦

Exercice 2 La suite harmonique est définie par Hn = 1 + 1/2 + · · · + 1/n pour n ≥ 1. Montrer
que H2n ≥ 1 + n/2 pour tout n ≥ 0. ♦
Exercice 3 On prouve la proposition “Toutes les roses ont le même parfum.” par récurrence sur
le nombre n de roses. Si n = 1, c’est évident. Soit un ensemble c1 , c2 , · · · , cn+1 de n + 1 roses. Par
hypothèse de récurrence c1 , · · · , cn est un ensemble de n roses qui ont donc le même parfum. De
même, c2 , c3 , · · · , cn+1 est un ensemble de n roses qui ont donc le même parfum. Puisque ces deux
ensembles ont en commun c2 , · · · , cn , les n + 1 roses ont le même parfum. Où est l’erreur ? ♦
Exercice 4 On considère le polynôme à coefficient réels P (x) = 31 x3 + ax2 + bx.
1) Trouver a et b pour que ∀x ∈ IR, P (x + 1) − P (x) = x2 . On suppose dans la suite que cette
propriété est vérifiée.
2) Montrer que ∀n ∈ IN, P (n) est un entier.
n
X
3) ∀n ≥ 0, on pose Sn = k 2 . Montrer que
k=0
n(n + 1)(2n + 1)
∀n ≥ 0, Sn = P (n + 1) = . ♦
6
Exercice 5 Soit Hn = 1 + 1/2 + · · · + 1/n pour n ≥ 2. Montrer que Hn n’est pas entier pour
n ≥ 2. ♦
Exercice 6 On rappelle que les nombres de Fibonacci sont définis par Fn = Fn−1 + Fn−2 pour
n > 1 et F0 = 0, F1 = 1. Montrer que pour tout n > 0 :
1) F1 + F3 + · · · + F2n−1 = F2n .
2) Fn+1 Fn−1 − Fn2 = (−1)n .
3) F12 + F22 + · · · + Fn2 = Fn Fn+1
4) F3n est pair. √
5) ϕn−2 ≤ Fn ≤ ϕn−1 , où ϕ = 1+2 5 est racine du polynôme x2 − x − 1. ♦
n
Exercice 7 Donner une définition inductive de f (n) = a2 .
n+1
 n
2
Indication. On pourra remarquer que a2 = a2 . ♦

Exercice 8 1) Montrer que ∀n ∈ IN, (n + 1)2 − (n + 2)2 − (n + 3)2 + (n + 4)2 = 4.

2) En déduire que tout entier m peut s’écrire comme somme et différence des carrés 12 , 22 , . . . , n2
pour un certain n, c’est-à-dire

∀m ∈ IN, ∃n ∈ IN, ∃ε1 , . . . , εn ∈ {−1, 1}, m = ε1 12 + ε2 22 + · · · + εn n2

(Indication: montrer d’abord le résultat pour m ∈ {0, 1, 2, 3}). ♦

Exercice 9 On considère le sous-ensemble D de IN × IN défini inductivement par :

T.S.V.P.
(i) (n, 0) ∈ D
(ii) si (n, n′ ) ∈ D, alors (n, n + n′ ) ∈ D
1) Donner quelques éléments de D.
2) Montrer par récurrence sur k que si n′ = kn alors (n, n′ ) ∈ D.
3) Montrer que si (n, n′ ) ∈ D, alors pour k ∈ IN, on a n′ = kn. ♦
Exercice 10 On dit qu’un ensemble ordonné est un treillis si tout sous-ensemble fini d’éléments
de E admet une borne supérieure et une borne inférieure.
Montrer qu’un ensemble ordonné (E, ≤) est un treillis si et seulement si tout sous-ensemble à
deux éléments de E admet une borne supérieure et une borne inférieure.
Indication: montrer par récurrence sur n que si tout sous-ensemble à deux éléments de E
admet une borne supérieure et une borne inférieure, alors tout sous-ensemble fini à n éléments de
E admet une borne supérieure et une borne inférieure. ♦
Exercice 11 Donner une définition inductive de la hauteur h(t), du nombre de nœuds n(t), du
nombre d’arêtes ar(t) et du nombre de feuilles f (t) d’un arbre binaire. ♦
Exercice 12 Soit t un arbre, h(t) sa hauteur, n(t) le nombre de ses nœuds, f (t) le nombre
de ses feuilles. On suppose que t est un arbre binaire (0, 1 ou 2 fils par nœud). Montrer que
n(t) ≤ 2h(t) − 1, et que f (t) ≤ 2h(t)−1 . ♦
Exercice 13 Soit t un arbre binaire strict (c’est-à-dire que t est non vide, chaque nœud de t a
exactement 0 ou 2 fils et il n’y a aucun noeud avec un seul fils non vide). Soit n(t) le nombre de
ses nœuds, f (t) le nombre de ses feuilles et a(t) le nombre de ses arêtes.
1) Donner une définition de l’ensemble ABS des arbres stricts.
2) Montrer que si t est un arbre binaire strict non vide n(t) = a(t) + 1.
3) Montrer que si t est un arbre binaire strict non vide n(t) = 2f (t) − 1. ♦
Exercice 14 Un arbre n-aire complet est un arbre où :
• chaque nœud interne a exactement n fils,
• toutes les feuilles sont à la même profondeur.
L’arbre vide est un arbre n-aire de profondeur 0.
1) Donner une définition inductive des arbres n-aires complets et étiquetés sur l’alphabet A =
{a} (toutes les nœuds sont étiquetés a).
2) Donner une définition inductive des arbres n-aires complets et étiquetés sur un alphabet A
non réduit à un unique élément.
3) Donner une définition inductive du nombre de nœuds et du nombre d’arêtes d’un arbre n-aire
complet de profondeur k. ♦
Exercice 15 Définir le parcours préfixe d’un arbre binaire. ♦
Exercice 16 (Fonction d’Ackerman) Soit f : IN × IN → IN définie par :
f (0, n) = n + 1,
f (m, 0) = f (m − 1, 1),
f (m, n) = f (m − 1, f (m, n − 1)).
1) Montrer que f (m, n) est définie pour tout couple (m, n) ∈ IN × IN.
2) Soit g: IN × IN → IN définie par :
g(0, n) = n + 1,
g(m, 0) = g(m − 1, 1),
g(m, n) = g(m − 1, g(m, n + 1)).

2
 Pour quels couples (m, n) ∈ IN × IN la fonction g(m, n) est-elle définie ?
3) Calculer f (1, n), f (2, n) et f (3, n). ♦
Exercice 17 Les listes de lettres L de l’alphabet A sont définies inductivement par :
(B) ε ∈ L,
(I) ∀l ∈ L, ∀a ∈ A, (al) ∈ L.
Définissons g(x, y) sur L × L par : ∀a ∈ A, ∀l ∈ L, ∀y ∈ L,

g(ε, y) = y ,
g((al), y) = g(l, (ay)) .

1) Soit Q(x) le prédicat ‘∀y, g(x, y) est défini’. Prouver par induction sur x que Q(x) est vrai
sur L.
2) Calculer g((a1 ), y), pour a1 ∈ A, y ∈ L.
3) Prouver par induction sur n (pour n ≥ 1) que



g (an (an−1 (. . . (a1 ) . . .))), y = g ε, (a1 (. . . (an−1 (an y)) . . .)) .

4) Soit rev(x) = g(x, ε). Déduire de la question 3 que, pour a1 , . . . , an ∈ A,

rev (an (an−1 (. . . (a1 ) . . .))) = (a1 (. . . (an−1 (an )) . . .)). ♦

Les notations qui suivent sont communes aux exercices 18 à 25. Un ensemble E muni
d’une opération ∗ associative est un semi-groupe. Si de plus E possède un élément neutre
e pour ∗ on dit que (E, ∗, e) est un monoı̈de. Etant donné un ensemble A, le monoı̈de
libre sur A, noté A∗ , est l’ensemble des suites finies d’éléments de A (dont la suite vide,
notée ε). Dans ce cas, l’opération qui fait de A∗ un monoı̈de est la concaténation, notée .
(“point”), qui admet la suite vide ε, pour élément neutre.
Exercice 18 On considère le monoı̈de libre A∗ sur un alphabet fini A. On note up le mot u . . . u,
où p exemplaires de u ont été concaténés. On dit que mot u est un facteur gauche d’un mot v,
s’il existe un mot w tel que v = uw, (de même, u est facteur droit de v si on peut écrire v = wu).
Soit α et β deux mots.
1) Montrer qu’une condition nécessaire et suffisante pour que l’un d’entre eux soit facteur gauche
de l’autre est qu’il existe deux mots u et v tels que αu = βv.
2) On suppose que αβ = βα. Montrer que cela équivaut à : ∃γ ∈ A∗ , ∃(p, q) ∈ N × N, α =
γ , β = γq.
p
♦

On appelle langage (sur l’alphabet A) un sous-ensemble de A∗ . Si L1 et L2 sont deux

langages de A∗ , on définit leur concaténation par :

L1 .L2 = {u.v | u ∈ L1 , v ∈ L2 }

La concaténation de langages est une opération associative admettant {ε} comme élément
neutre. On peut alors définir les puissances d’un langage L par : L0 = {ε} et Ln+1 =
Ln .L = L.Ln . Enfin, l’étoile d’un langage L est le sous-monoı̈de de A∗ engendré par L
c’est à dire : [
L∗ = Ln
n∈IN

3
Exercice 19 Les notations sont les mêmes que dans l’Exercice 18. On définit inductivement les
langages rationnels (on dit aussi réguliers) par :
(i) Un langage fini est rationnel,
(ii) Si L1 et L2 sont rationnels alors L1 ∪ L2 est rationnel,
(iii) Si L1 et L2 sont rationnels alors
S L1 .L2 = {uv, u ∈ L1 , v ∈ L2 } est rationnel,
(iv) Si L est rationnel alors L∗ = n≥0 Ln est rationnel (L0 = {ǫ}).
On appelle miroir du mot u = a1 · · · an , le mot ũ = an · · · a1 . Si L est un langage, on définit
L̃ = {ũ, u ∈ L}. Montrer que si L est un langage rationnel, alors L̃ est également rationnel. ♦
Exercice 20 [Lemme d’Arden] Soient L et M deux langages de A∗ tels que ε 6∈ L, montrer que
l’équation X = L.X ∪ M admet pour unique solution le langage L∗ .M . ♦
Exercice 21
1) Définir la relation “est un préfixe de” sur A∗ . S’agit-il d’une relation d’ordre ? si oui, s’agit-il
d’un ordre total ou d’un ordre partiel ?
2) En supposant que A est muni d’un ordre total A , définir l’ordre lexicographique sur A∗ .
S’agit-il d’un ordre total ou d’un ordre partiel ?
3) Soit A = {a, b} tel que a A b. Montrer que l’ordre lexicographique défini à la question
précédente n’est pas un ordre bien fondé. ♦
Exercice 22 Soient (A, ≤1 ) et (B, ≤2 ) deux ordres bien fondés. Les ordres suivants sont-ils bien
fondés ?
1. sur A × B, l’ordre produit ( (a, b) ≤ (a′ , b′ ) ⇐⇒ (a ≤1 a′ ) ∧ (b ≤2 b′ ) ).
2. sur A × B, l’ordre lexicographique. ♦
Exercice 23 Les ordres suivants sont-ils bien fondés ?
1. sur A2 , l’ordre lexicographique (A alphabet totalement ordonné).
2. sur IN m ≤ n ssi m divise n.
3. sur l’ensemble des diviseurs d’un entier donné, la relation du 2.
4. sur A∗ , l’ordre préfixe.
5. sur A∗ , l’ordre u ≤ v ssi u est un sous-mot de v.
6. sur A∗ , l’ordre lexicographique (A alphabet totalement ordonné).
7. sur A∗ / ≡, l’ordre des longueurs u ≤ v ssi |u| ≤ |v| (où ≡ est défini par u ≡ v si et seulement
si |u| = |v|). ♦
Exercice 24 L’ordre préfixe sur A∗ peut être défini de deux manières différentes :
(1) ∀m1 , m2 ∈ A∗ m1 1pref m2 si et seulement si ∃m3 ∈ A∗ m1 m3 = m2
(2) Définition inductive :
(B) ∀m ∈ A∗ ε 2pref m
(I) Si m1 , m2 ∈ A∗ sont tels que m1 2pref m2 , alors pour tout a ∈ A, am1 2pref am2
Montrer que ces deux définitions sont équivalentes. ♦
∗
Exercice 25 Soit A le monoı̈de libre engendré par l’alphabet A.
Le miroir d’un mot u = a1 a2 · · · an est le mot ũ = an · · · a2 a1 . Donner une définition inductive
du miroir. ♦
S
Exercice 26
Soit F0

= {a}, F1 = {s}, F = F0 F1 . L’ensemble T des termes construits sur F
est T = {a, s a , s s a , . . .}.
Posons V = IN. Soit h: F0 −→ V , et hs : V −→ V ; il existe une et une seule fonction h∗ de T
dans V telle que:
(B’) Si t ∈ F0 , h∗ (t) =
h(t),
(I’) Si t = f t1 , . . . , tn , h∗ (t) = hf (h∗ (t1 ), . . . , h∗ (tn )).

4
 Calculer h∗ dans les cas suivants :
1) h1 (a) = 0, h1 s (n) = n + 1.
2) h2 (a) = 1, h2 s (n) = 2n.
3) h3 (a) = 1, h3 s (n) = n + 2. ♦
Exercice 27 Soit X un ensemble de symboles de variable et F un ensemble de symboles de
fonction, on définit inductivement l’ensemble T (F, X) des termes sur F et X de la façon suivante :
(B) Si x ∈ X alors x ∈ T (F, X); si f ∈ F0 , alors f ∈ T (F, X);
(I) Si t1 , . . . , tn ∈ T (F, X), n ≥ 1 et f ∈ Fn , alors f (t1 , . . . tn ) ∈ T (F, X). (Fn est l’ensemble
des symboles de fonction d’arité n.
1) Une application ϕ de T (F, X) dans T (F, X) est un morphisme si elle vérifie ϕ(f0 ) = f0 pour
f0 ∈ F0 et ϕ(f (t1 , . . . , tn )) = f (ϕ(t1 ), . . . , ϕ(tn )) pour f ∈ Fn , n > 0. Soit une application h
de X dans T (F, X), montrer qu’il existe un morphisme unique h∗ de T (F, X) dans T (F, X) qui
prolonge h (c’est à dire, tel que ∀x ∈ X, h∗ (x) = h(x)).
2) Une substitution est une opération sur les termes permettant de remplacer certaines variables
d’un terme par un terme. Plus formellement, l’ensemble Θ des substitutions est l’ensemble des
fonctions de X dans T (F, X) :
Θ = {θ : X → T (F, X)}
On notera sid la substitution identité, c’est-à-dire la substitution telle que pour toute variable
x ∈ X, sid (x) = x. Une substitution θ se prolonge de façon unique en une fonction θ ∗ de T (F, X)
dans T (F, X) définie par :

∀x ∈ X θ ∗ (x) = θ(x) et ∀f0 ∈ F0 θ ∗ (f0 ) = f0

∀f ∈ Fn ∀t1 , t2 , · · · , tn ∈ T (X, F ) θ ∗ (f (t1 , t2 , · · · , tn )) = f (θ ∗ (t1 ), θ ∗ (t2 ), · · · , θ ∗ (tn ))

Appliquer une substitution à un terme c’est donc instancier certaines de ses variables par des
termes et donc faire augmenter sa taille. Montrer que :

∀θ ∈ Θ ∀t ∈ T (X, F ) τ (θ ∗ (t)) ≥ τ (t)

où la taille d’un terme est donnée par l’application τ : T (X, F ) → IN définie par :

0 si t = x,


1 si t = f0 ∈ F0 ,
τ (t) = P n
1+
 τ (ti ) si t = f (t1 , · · · , tn ).
i=1

3) On peut définir un préordre (i.e. une relation réflexive et transitive) sur T (X, F ) comme
suit : t1  t2 si et seulement si il existe une substitution θ telle que θ ∗ (t1 ) = t2 . Montrer que
cette relation définit bien un préordre (ce préordre est appelé préordre de filtrage).
4) Pourquoi le préordre de filtrage ne définit-il pas une relation d’ordre (i.e. une relation
réflexive, antisymétrique et transitive) ?
5) Dans cette question nous allons voir qu’il est possible de définir une relation d’ordre à partir
d’un préordre.
Soit E un ensemble muni d’un préordre .

5
a) Montrer que la relation ≈ définie par x ≈ y ssi soit x = y soit x  y et y  x est une relation
d’équivalence (i.e., une relation réflexive, symétrique et transitive).
b) On note [x]/≈ = {y | y ≈ x} la classe d’équivalence de x et E/≈ l’ensemble des classes
d’équivalence de E pour ≈ (ensemble quotient). Montrer que la relation  définie sur E/≈ par
[x]/≈ [y]/≈ ssi x  y est une relation d’ordre (cet ordre est appelé ordre quotient du préordre ).
6) D’après la question précédente, on peut définir une relation d’équivalence sur les termes
comme suit :
t1 ≡ t2 ssi t1 = t2 ou (t1  t2 et t2  t1 )
En fait, la relation ≡ identifie les termes équivalents à un renommage près des variables. A partir
de cette relation d’équivalence entre termes, il est alors possible de construire une relation d’ordre
 sur l’ensemble quotient T (X, F )/≡ définie par :

[t1 ]/≡ [t2 ]/≡ ssi t1  t2

On remarquera que tous les termes d’une même classe d’équivalence ont la même taille.
(i) Soit Λ(t) le nombre de variables distinctes apparaissant dans le terme t. Montrer que t ≺ t′
et τ (t) = τ (t′ ) =⇒ Λ(t′ ) < Λ(t).
(ii) Montrer que  est un ordre bien fondé sur T (X, F )/≡ . ♦
Exercice 28 1. On suppose qu’une propriété P définie sur IN vérifie :
(i) P (1) est vraie
(ii) si P (n) est vraie alors P (2n) est vraie (pour n ≥ 1)
(iii) si P (n) est vraie alors P (n − 1) est vraie (pour n ≥ 2).
Montrer par récurrence sur n que P (n) est vraie pour tout n ≥ 1.
2. On veut montrer que la moyenne arithmétique est supérieure à la moyenne géométrique.
Soient a1 , . . . , an n nombres réels positifs, avec n ≥ 1 ; on pose A = (a1 + · · · + an )/n et G =
(a1 · · · an )1/n , montrer que A ≥ G. ♦