Écriture binaire d’un nombre réel

Publié le 03/03/17

(cet exercice est issu de l’oral X-Cachan Psi 2015)
On pose {x \in[0,1[} et {x_{1} = \lfloor 2x\rfloor}.
Pour tout {n\in\mathbb{N}^{*}}, soit {x_{n+1}= \lfloor 2^{n+1}(x - S_{n})\rfloor}, où {S_{n} = \displaystyle\sum_{k=1}^{n}\dfrac{x_{k}}{2^{k}}}.

  1. Vérifier qu’on a {S_{n}\le x \lt S_{n} +\dfrac{1}{2^{n}}} pour tout {n\in\mathbb{N}^{*}}.
  2. Montrer que les conditions suivantes sont équivalentes:
    \cdot\ x=j\,2^{-m} avec j entier, {0\le j\lt 2^{m}}
    {\cdot\ x_{k}=0} pour tout {k > m}.

  3. Soit {f\colon\{0,1\}^{\mathbb{N}^{*}}\rightarrow[0,1],\;(x_{k})_{k\ge1}\mapsto \displaystyle\sum_{k=1}^{+\infty}\dfrac{x_{k}}{2^{k}}}.
    Montrer que f est bien définie, surjective mais pas injective.

  1. On a {x-S_{1}=x-\dfrac{x_{1}}{2}=\dfrac{1}{2}\bigl(2x-\lfloor2x\rfloor\bigr)\in\Big[0,\dfrac{1}{2}\Bigr[}.

    Ainsi {S_{1}\le x \lt S_{1}+\dfrac{1}{2}}: l’encadrement demandé est vrai si {n=1}.

    On le suppose vrai au rang {n\ge1}.

    Alors {2^{n+1}(x-S_{n+1})=2^{n+1}(x-S_{n})-x_{n+1}\in[0,1[}.

    Ainsi {x-S_{n+1}\in\Bigl[0,\dfrac{1}{2^{n+1}}\Bigr[}, ce qui achève la récurrence.

    Remarque: {S_{n} \le x \lt S_{n} +\dfrac{1}{2^{n}}} donne {0\le 2^{n+1}(x-S_{n})\lt 2} donc {x_{n+1}\in\{0,1\}}.

    Ainsi: {\forall\, k\in\mathbb{N}^{*},\;x_{k}\in\{0,1\}} (vrai si {k=1} par définition de {x} et de {x_{1}}).

    Les {x_{k}} sont bien sûr les chiffres de la représentation binaire de {x}.

    Par construction: {2^{n}S_{n}\in\mathbb{N}}, avec {2^{n}S_{n}\le 2^{n}x\lt 2^{n}S_{n}+1} donc {2^{n}S_{n}=\lfloor2^{n}x\rfloor}.

    Ainsi {S_{n}=2^{-n}\lfloor2^{n}x\rfloor} est la valeur approchée de {x} par défaut à {2^{-n}} près.

  2. On suppose {x_{k}=0} pour tout {k>m}.

    Alors, pour tout {n>m}, on a {S_{n}=S_{m}}, donc {S_{m} \le x \lt S_{m} +\dfrac{1}{2^{n}}}.

    Avec {n\rightarrow+\infty} on a {x=S_{m}=\displaystyle\sum_{k=1}^{m}\dfrac{x_{k}}{2^{k}}=\dfrac{j}{2^{m}}}, où {j=\displaystyle\sum_{k=1}^{m}2^{m-k}x_{k}}.

    Il en résulte {j\in\mathbb{N}} et {j\le \displaystyle\sum_{k=1}^{m}2^{m-k}=2^{m}-1\lt 2^{m}}.

    Réciproquement, on suppose que {x=\dfrac{j}{2^{m}}} avec {0\le j\lt 2^{m}}.

    Alors {S_{k}\le \dfrac{j}{2^{m}}\lt S_{k}+\dfrac{1}{2^{k}}} donc {2^{k}S_{k}\le j\,2^{k-m}\lt 2^{k}S_{k}+1} pour tout {k\ge m}.

    Mais {2^{k}S_{k}} et {j\,2^{k-m}} sont entiers, donc {S_{k}=\dfrac{j}{2^{m}}=x} pour tout {k\ge m}.

    Il en découle {x_{k+1}= \lfloor 2^{k+1}(x - S_{k})\rfloor=0} pour {k\ge m}, ce qu’il fallait prouver.

  3. Si {\sigma=(x_{k})_{k\ge1}\in\{0,1\}^{\mathbb{N}^{*}}}, alors {0\le \dfrac{x_{k}}{2^{k}}\le \dfrac{1}{2^{k}}}.

    Cela assure la convergence de la série, et {0\le f(\sigma)\le \displaystyle\sum_{k=1}^{+\infty}\dfrac{1}{2^{k}}=1}.

    Soit {x\in[0,1[}. Avec les notations de (1) on a: {\forall\, n\in\mathbb{N}^{*},\;x-\dfrac{1}{2^{n}}\lt S_{n}\le x}.

    Ainsi {x=\displaystyle\lim_{n\rightarrow+\infty}S_{n}=\displaystyle\sum_{k=1}^{+\infty}\dfrac{x_{k}}{2^{k}}=f((x_{k})_{k\ge1})}.

    Par ailleurs {1=\displaystyle\sum_{k=1}^{+\infty}\dfrac{1}{2^{k}}=f((x_{k}=1)_{k\ge 1})}.

    L’application {f} est donc une surjection de {\{0,1\}^{\mathbb{N}^{*}}} dans {[0,1]}.

    Montrons qu’elle n’est pas injective.

    Posons par exemple {\begin{cases} x_{1}=0\\ x_{k}=1\text{\ si \ }k\ge1\end{cases}} et {\begin{cases} y_{1}=1\\ y_{k}=\text{\ si \ }k\ge1\end{cases}}

    Ces deux suites ont la même image: {f(x)=\displaystyle\sum_{k=1}^{+\infty}\dfrac{x_{k}}{2^{k}}=\displaystyle\sum_{k=2}^{+\infty}\dfrac{1}{2^{k}}=\dfrac{1}{2}\text{\ et \ }f(y)=\displaystyle\sum_{k=1}^{+\infty}\dfrac{y_{k}}{2^{k}}=\dfrac{y_{1}}{2}=\dfrac{1}{2}}