Salut,
Je ne vous demande pas de répondre à ma place mais peut-être pourriez-vous m'aider à mieux comprendre parce-que je ne sais pas par ou commencer.

On s'intéresse a l’ensemble C des clôtures solides. Elles sont construites avec
des poteaux, représentés par le symbole ‘|’, et des traverses, représentées par le
symbole ‘×’. Par exemple, les clôtures “|×|×|” et “|×|||×||” sont solides, alors
que les clôtures “| × |×” et “| × ×|” ne le sont pas. On définit récursivement
l’ensemble C de la fa¸con suivante.
1. La chaîne “| × |” appartient `a C.
2. Si c ∈ C, alors les chaines “c|” et “c × |” sont dans C.
La longueur d’une clôture est le nombre de traverses que la clôtures possède.

a) Donnez une définition récursive de la fonction L(c) qui calcule la longueur
d’une clôture c.

b) Donnez une définition récursive de la fonction P(c) qui calcule le nombre de
poteaux d’une clôture c.

c) Montrez, par induction, qu’une clôture solide a toujours un nombre de poteaux
strictement supérieur à sa longueur. Aide : faites l’induction sur le nombre
de fois ou la règle 2 a été appliquée.

tu as un cours sur les fonctions récursives ?

on t'as déjà répondu...

a) L(c) = L(c-1) si le dernier caractère est un poteau et L(c-1) + 1 si le dernier caractère est une traverse
b) P(c) c'est pareil il faut juste intervertir
c) Une clotûre solide s'écrit "|||..." + |x| + "n*règle(2)"
on décompose donc la clotûre en ces trois parties:

1) "|||...": longueur 0 et le nombre de poteaux >=0
2) |x|: longueur 1 et nombre de poteaux = 2
-> à ce stade on a pour la sous-clôture "||||...." + |x| la propriété "nombre de poteaux > longueur"
3) n*règle2: à chaque fois qu'on applique la règle2, on ajoute un nombre de poteaux supérieur ou égal à la longueur ajoutée (0 pour "|" et 1 pour "x|") donc au final on peut l'appliquer un milliard de fois on aura toujours nombre de poteaux > longueur

voilà pour l'idée

Pour la c), il faut plutôt raisonner par induction structurelle sur la façon dont a été construite la clôture :
- cas de base |x| : deux poteaux et longueur 1, la propriété est vérifiée.
- cas d'une clôture de la forme c| : par hypothèse d'induction, c a plus de poteaux que sa longueur, donc c| aussi.
- cas d'une clôture de la forme cx| : idem

ouais j'avoue c'est plus formel que de le faire à l'envers