# OLA, TD 6 : Récurrence

## Exercice 1 : Définitions récursives d’opérations arithmétiques

### 1 Equations récursives pour n!
$0! = 1$
$(n+1)! = (n+1) * n!$

### 2 Equations récursives pour la fonction puissance

$k^{0} = 1$
$k^{n+1} = k * k^{n}$

### 3 Equations récursives pour la fonction k-exposants

(Erreur d'énoncé, on a n-1 exposants et pas n)
$^{0}k = 1$
$^{n+1}k = k^{^{n}k}$

## Exercice 2 : Récurrence sur les entiers

Initialisation : Pour $n = 1$, on a un quadrillage avec des cotés de longueur $2^{1}$ ce qui nous donne 4 cases au total, $4-1 = 3$ donc la propriété est vraie pour $n=1$ car on place exactement un triomino.

Récurrence:
On suppose que la propriété est vraie pour un certain entier $n$.
Un carré de côté $2^{n+1}$ contient exactement 4 carrés de côté $n$.
Si on retire une case à ce grand carré, on a retiré une case à l'un des 4 petits carrés dont il est composé.
On place un triomino au centre de sorte qu'il soit à l'intersection des trois autres carrés. Le problème se ramène alors à paver 4 carrés de côté $2^{n}$ auxquels on a retiré une case. On applique donc l'hypothèse de récurrence pour finir le pavage.


## Exercice 3 : Récurrence à récurer

L'erreur se situe dans le fait que le raisonnement de Toto ne marche que pour une initialisation avec $n>1$.
En effet, quand il retire le dernier crayon de la boîte, la boîte contient
les crayons $1, 2..., n$
Il dit qu'alors les crayons ont la même couleur par hypothèse de récurrence.
Et ensuite il fait de même pour les crayons $2, ..., n+1$
S'il y a des crayons entre le crayon 1 et le crayon $n+1$ alors on peut comparer la couleur du crayon 1 et du crayon $n+1$ : ils auront tous les deux la couleur du crayon du milieu.
Mais quand $n=1$, donc $n+1=2$, on ne peut pas comparer la couleur du crayon 1 avec celle du crayon 2 car il n'y a plus de crayon du milieu, donc le raisonnement ne marche plus.

Toto a juste montré que si toutes les boîtes contenant deux crayons de couleurs avaient les crayons de la même couleur, alors les boîtes ayant $n \ge 2$ crayons de couleurs auraient leurs crayons de la même couleur.

## Exercice 4 : Retournement de liste

Note: nil est la liste vide

let rec rev l = match l with
| [] -> []
| x::l -> concat (rev l) [x]

1. Cas nil :

donc ```length(rev[])= length([])=0```

Cas cons:

On suppose que pour une certaine liste l, ```long(rev l) =  long(l)```
On doit montrer qu'on a alors, pour tout x, ```long(rev (x::l) =  long(x::l)```

long(rev(x::l))= long(concat(rev(l),x::[])) (définition de rev)
=long(rev(l))+long([x] (propriété du cours)
=long l + long [x] (hypothèse de récurrence)
=long(x::l) (définition de longueur)

Donc d'après le principe d'induction la propriété est vraie.



Jacobo:
Hérédité: supposons que longueur(rev(l)) = longueur(l)

Montrons que longueur(rev(x::l))= longueur(x::l):

long(rev(x::l))= long(concat(rev(l),x::[]))
                =long(rev(l))+long(x::[])
                =long(l)+long(x::[]) (par hypo rec)
                =long(concat x::[], l) (par commutativité de la somme)
                =longueur(x::l)
Conclusion: Par recurrence la propriete est vraie. 
                
Alexis:
Init:
l1=[], l2 = rev(l1) = [] donc longueur(l1) =  longueur(l2) = 0, on a donc la propriété longueur(rev(l)) = longueur(l) qui est vraie

Hérédité :
On suppose la propriété vraie pour une certaine liste l de longeur n, on a donc long(l)=n.
long(rev(l)) = long(rev(h::t))
             = long(contact rev(t)  [h])
             = long(rev(t) + long([h]))
             = n-1 + 1
             = n







Berkennou : 
cas de base : vérifions pour l=[]
 L = [] on a longeur(l) = 0 te rev(l) renvoie [] donc longeur(rev(l)) donnera 0
 
Héridité : 
supposons que p(l)(l) est vraie et démontrons pour p(x::l) (x::l).
on a de la propriété de la fonction longueur
longeur(x::l) = longeur (l)+1
on a rev(x::l)=concat(rev(l),x::[])
ou rev(l) = longueur (l) selon l'hypothése de récurrence 
à laquelle on rajoute 1 (l'elt qu'on a rajouter(x)) vu que c'est une concaténation avec la fonction concat
donc on aura : 
longueur(rev(x::l))= longueur(l)+1 = longeur(x::l)

Par rec rev preserve la longueur.x    


2. 

let rec concat l1 l2 = match l1 with
| [] -> l2
| e::l -> e :: concat l l2

Comme ```concat``` est définie sur ```l1```, on fait la récurrence sur ```l1```.

Cas de base: ```l1=[]```

= rev(l2)++[]
= rev(l2)++rev([])

Cas d'hérédité : on suppose la propriété vraie pour ```l1``` et on veut la montrer pour ```x :: l1```

= rev (l1 ++ l2) ++ [x]
= (rev l2 ++ rev l1) ++ [x] (HR)
= rev l2 ++ (rev l1 ++ [x]) (propriété de concat)
= rev l2 ++ rev (x :: l1) (définition de rev)

3.

Cas de base:

Hérédité, on suppose que ```rev (rev l)= l ```

=rev(rev l ++ [x]) (définition de rev)
=rev [x] ++ rev(rev l) (question 2)
= [x] ++ l (HR)
= x :: l