\documentclass[12pt,a4paper,twoside]{article}

\usepackage[latin1]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{aafrench}
\input{c:/tex/aaa/oi/exs/exs} %inclue ifthen
%\usepackage{alltt}                          %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlg}    %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpic}  %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpicf} %DECOMMENTER CETTE LIGNE
%\newcommand{\FigMlPic}[3]{\mbox{}\\FIGURE\\} %COMMENTER CETTE LIGNE

\begin{document}
 \setlength{\parindent}{7mm}
 \setlength{\abovedisplayskip}{0.5mm}
 \setlength{\belowdisplayskip}{0.5mm}\begin{parenthese}
 \thispagestyle{empty}
  \sujet{Décomposition en nombres de Fibonacci (ENS)}
  \texte
   $F$ est la suite de Fibonacci définie par
   $F_0=0$, $F_1=1$ et $F_{n+2}=F_{n+1}+F_n$ pour tout $n\in\N$.
  \unequestion
   Montrer que tout entier $n\geq0$ peut s'écrire de façon unique
   sous la forme
   ${\displaystyle n=\sum_{i=1}^{r}F_{e_i}}$,
   où $e_i-e_{i+1}>1$ et $e_i\geq2$.
\paragraph*{Corrigé}\setcounter{questions}{0}\mbox{}
   \texte
    Montrons d'abord par récurrence sur $r$ que, pour toute
    décomposition ${\displaystyle n=\sum_{i=1}^{r}F_{e_i}}$,
    on a $n<F_{e_1+1}$. Si $r=1$, c'est clair; et si on suppose
    le résultat pour $r-1$, alors
    ${\displaystyle n<F_{e_1}+F_{e_2+1}\leq F_{e_1}+F_{e_1-1}=F_{e_1+1}}$.
    \par
    On démontre par récurrence sur $p$ que tout entier
    $<$ à $F_p$ admet une unique décomposition
    de la forme indiquée. Pour $p\leq4$ c'est facile.
    Si le résultat est vérifié pour $p$, soit
    $n\in[F_p,F_{p+1}[$: $n=F_p+m$ où $0\leq m<F_{p+1}-F_p=F_{p-1}$.
    D'après l'hypothèse de récurrence,
    $m$ admet une unique décomposition
    ${\displaystyle m=\sum_{i=1}^{r}F_{e_i}}$. Les $e_i$ sont alors
    nécessairement $<p-1$ donc
    ${\displaystyle n=F_p+\sum_{i=1}^{r}F_{e_i}}$ est une décomposition
    de $n$. Pour vérifier l'unicité,
    soit ${\displaystyle n=\sum_{i=1}^{s}F_{e_i'}}$ une décomposition
    de $n$. Nécessairement, $e_1'=p$ (car sinon $e_1'<p$ 
    et donc $n<F_{e_1'+1}\leq F_p$) et
    ${\displaystyle \sum_{i=2}^{s}F_{e_i'}}$ est donc la
    décomposition de $m$.
\end{parenthese}\end{document}
