# OLA, TD8 : Prédicats inductifs

## Exercice 1:

1.

2. Principe d'induction:
Si on a $\forall$ x, y : ami(x, y) ⇒ P(x,y)
et si on a $\forall x, y, z$ ami (x, z) et P(z, y) ⇒ P(x, y)
Alors on peut conclure par le principe d'induction:
$\forall$ x, y, lié(x, y) ⇒ P(x, y)

3.
a) ∀ x y z, ami (x, z) ⇒ lié (z, y) ⇒ lié (x, y)
Il s'agit de la règle 2, donc c'est simplement une conséquence de la définition.
b) ∀ x y z, lié (x, z) ⇒ ami (z, y) ⇒ lié (x, y)
On montre par induction sur lié(x, z)
P(x, z) := ∀ y, ami (z, y) ⇒ lié (x, y)

Cas 1: on montre que
∀ x, z, ami(x, z) ⇒ ∀ y, ami (z, y) ⇒ lié (x, y)
Soient x et z dans X
On suppose ami(x, z), alors soit y tel que ami(z, y).
On déduit par la règle 1 que lié(z, y)
Donc par la règle 2, lié(x,y)

Cas 2: On montre que
∀ x, z, t ami(x, t) et P(t, z) ⇒
∀ y, ami (z, y) ⇒ lié (x, y)

Donc soit x z et t tels que ami (x,t) et P(t, z)
Soit y tel que ami (z,y), on veut montrer que lié(x,y).
On rappelle que P(t,z) signifie
∀ y, ami (z, y) ⇒ lié (t, y)
On a justement l'hypothèse ami(z,y) donc on peut déduire lié (t,y)
On a aussi l'hypothèse ami(x,t) donc on peut déduire par la règle 2
que on a lié(x,y)

4.

On veut montrer ∀ x y, lié (x, y) ⇒ lié (y, x)
lié(y, x) = P(x, y)

Cas 1 : on veut montrer que
ami(x,y) ⇒ P(x,y)
On suppose ami(x,y)
ami est une relation symétrique donc on a aussi ami(y,x)
Donc par la règle 1, on a lié(y,x)

Cas 2: on veut montrer que
ami(x, z) et P(z, y) ⇒ lié (y, x)
On suppose ami (x, z) et lié (z, y).
On a P(z, y) donc on a lié (y, z)
On a ami (x, z) donc on a ami (z, x)
On utilise la propriété de la question 3b pour déduire que lié(y,x)

Ainsi on a bien montré par induction que ∀ x y, lié (x, y) ⇒ lié (y, x)

## Exercice 2:

1.
2. Principe d'induction
Cas de base : P(0, 1, 0)
Cas inductif : ∀ x,y,n P(x,y,n) ⇒ P(x+y, y+2, n+1)

Conclusion : ∀ x y n, R(x, y, n) ⇒ P(x, y, n)

3. On veut montrer R(x, y, n) ⇒ x = n² ∧ y = 2n + 1
On note cette propriété P(x, y, n)

Cas de base:
x=0, y =1, n=0
On a bien 0 = 0² et 1 = 2*0 + 1

Cas inductif:
On suppose que P(x, y, n) est vrai, donc x = n² ∧ y = 2n + 1
On veut montrer que P(x + y, y+2, n+1) est vrai
On calcule x + y = n² + 2n + 1 = (n+1)²
On calcule (y + 2) = (2n + 1 + 2 ) =2*(n+1) +1
Donc P(x,y,n) ⇒ P(x+y, y+2, n+1)
On conclut que ∀ x y n, R(x, y, n) ⇒ x = n² ∧ y = 2n + 1

4. $x_{n}$ est une suite d'entiers strictement croissante qui démarre à zéro donc il existe un unique n qui vérifie la propriété
D'après la question 3, on a
n² ≤ a < (n+1)²

# Exercice 3: