Preuve que tout nombre peut s'écrire en binaire

Bonjour,

Je cherche à prouver que tout nombre (entier naturel) peut s’écrire en binaire.

J’ai fais un truc je voudrais savoir si c’est juste ou s’il existe plus simple.

Je définis $P : \text{Tout nombre }n\text{ peut s'écrire }\sum_{i=0}^l 2^i a_i \text{ tel que } i,l \in \mathbb{N}\text{ et }\forall a_i, a_i \in {0, 1}$

Je dis que $n$ peut s’écrire $n = 2k + r$ avec $r \in {0, 1}$

Ensuite, je sépare deux cas:

Soit $k = 0$, alors $n = 2*0 + 2^0r$ alors $P$ est vrai.

Soit $k \neq 0$ alors si $P$ est vrai pour $k$ alors :

Donc si $P$ est vrai pour $k$ alors $P$ est vrai pour $n$ et donc par récurrence, $P$ est vrai pour $n$. J’en conclus donc que $P$ est vrai pour tout entier naturel $n$.

Il me ne manque pas une info dans cette preuve ?
Merci !

Salut. A priori la preuve est bonne, juste pas tout à fait formalisée. Ce que tu fait reviens à une preuve par récurrence, et ta manière de distinguer les deux cas $k=0$ et $k\neq 0$ c’est une manière confuse de gérer l’initialisation de la récurrence.

Ce que tu peux poser, pour que ce soit plus clair, c’est la propriété $P_k :$ « $P$ est vrai pour tout $0 \leqslant n < 2^k$ ». Alors ton premier cas peut se réécrire comme prouver que $P_0$ est vrai (on peut écrire 0 et 1 en binaire), et ensuite, ton deuxième cas prouve que $P_k \implies P_{k+1}$, car si $n\leqslant 2^{k+1}$ et $n=2m+r$ avec $r\in \{0,1\}$ (division euclidienne), alors $m\leqslant 2^k$ et la récurrence fonctionne.

Ah je comprend. Ce que tu me proposes est ce qu’on appelle une récurrence forte c’est ça ?
J’ai oublié de préciser dans ma preuve que bien-sûr j’utilisais la division euclidienne.

L’idée que j’avais c’était que l’on peut diviser (division euclidienne), un nombre fini de fois (avant d’arriver à $0$ et de boucler). Et qu’à chaque étape on a $n_i = 2n_{i+1} + r, r \in {0, 1}$. Et que donc si c’était vrai pour $n_l$ (où on arrive à $0$). Alors c’était vrai pour $n_{l-1}$ et donc vrai pour $n_0 = n$.

Il me semble du coup que ce n’était pas une récurrence forte (c’est juste le fait d’utiliser un $\leq$ ou $\geq$ ?)

Merci pour ta réponse en tout cas. Ça m’aide.

Oui c’est l’idée, et ce que tu propose, diviser plusieurs fois jusqu’à arriver à 0, c’est ce que l’on formalise pour en terme de récurrence, mais derrière c’est ça que l’on fait. Pour la remarque sur la récurrence forte, par contre, je suis pas sûr que ça s’applique là… Ici, il n’y a pas vraiment de différence entre récurrence forte et faible avec la propriété que j’ai prise. La récurrence forte, c’est dire qu’il faut $P_0, \dots, P_k$ pour prouver $P_{k+1}$. Ici, $P_k \implies P_0, \dots, P_k$ donc je pense pas que ça soit très pertinent (et de toute façon, ces "types" de récurrence sont surtout des conventions à mon sens).

Ça serait une récurrence forte si ma propriété c’était $P'_k:$ « P vrai pour tout $2_{k-1} \leqslant n < 2^k$, car alors on doit bien supposer $P_0, \dots, P_k$ vrai pour prouver $P_{k+1}$. Mais tout ça ça reste juste des manière de rédiger, ça ne change pas l’idée !

Parfait ! J’ai bien compris le principe de la récurrence force.

Compris. Merci