Exercice 4 - Introduction aux itérateurs

Etant donné une fonction $f$, on note $f^n$ la composition de $f$ par elle-même $n$ fois. Par exemple : $f^3 = f \circ f \circ f$, si $f : x \mapsto x + 1$, alors $f^3(x) = f(f(f(x))) = x + 3$. Par convention, on a $f^0 = id$, avec $id : x \mapsto x$.

1. Si $f : x \mapsto x + 1$, démontrez par récurrence que $f^n : x \mapsto x + n$
2. Si $f : x \mapsto 2x$, démontrez par récurrence que $f^n : x \mapsto 2^nx$
3. Si $f : x \mapsto x^2$, démontrez par récurrence que $f^n : x \mapsto x^(2^n)$
4. Ecrire une fonction récursive $applyF$ non terminale prenant en paramètre une fonction $f$, un nombre $n$ et un argument $x$, et retournant $f^n(x)$. Ce type de fonction sera appelé un itérateur.
5. Ecrire une version récursive terminale de $applyF$.
6. Soit $f : (a, b) \mapsto (a + b, b)$, montrez par récurrence que $f^n : (0, b) \mapsto (bn, b)$
7. Ecrire une fonction $f$ prenant en paramètre le couple $(a, b)$ et retournant $(a + b, b)$.
8. Ecrire la fonction $multiplie$ en utilisant $f$ et $applyF$.