Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup ConcoursTopics traitant de concours [tout]Lister tous les topics de mathématiques

1 2 +

Niveau Maths sup
Partager :

Entier en base deux

Posté par Profil Ramanujan 12-10-18 à 03:17

Bonsoir,

Soit n un entier supérieur ou égal à 2.

On suppose que N=\sum_{k=0}^{n-1} d_k 2^k
Avec \forall k \in [|0,n-2|] : d_k \in \{0,1\}
Et d_{n-1}=1

1/ Montrer que 2^{n-1} \leq N \leq 2^n -1
J'ai résolu cette question.

2/ Montrer que d_0 est le reste de la division euclidienne de N par 2.
J'ai réussi cette question.

3/ Démontrer que la suite (d_0,d_1,...,d_{n-1}) est déterminée de manière unique.
Je bloque sur cette question. Je ne vois pas comment partir.

Posté par
Schtromphmolre : Entier en base deux 12-10-18 à 03:49

Bonsoir,

Suppose que (d(0)..d(n-1)) et (d'(0)..d'(n-1)) sont deux suites possibles pour un même nombre N et montre qu'elles sont égales par récurrence.

Posté par
luzakre : Entier en base deux 12-10-18 à 08:32

Et surtout ne pas imiter "ton" corrigé qui fait un simulacre de démonstration d'unicité par récurrence.
C'est presque correct mais difficile à maîtriser : on tombe facilement dans un piège car il faut " démontrer qu'il y a une unique démonstration ".

Ce que suggère Schtromphmol est correct et tu ferais mieux de suivre cette indication.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 11:19

@Luzak

J'ai parcouru vite fait ça m'a l'air tordu mais je préfère pas regarder la solution entière j'ai envie de réfléchir par moi-même.

Je vais tenter la méthode de Schtromphmol.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 11:21

Sinon j'ai une question :

Faut pas aussi vérifier que si on prend 2 suites elles ont le même nombre de termes ?

En gros si on prend : n' \ne n alors on trouve une contradiction.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 12:00

Parce que la démo de Schtromph on suppose que les 2 suites ont forcément le même nombre de termes et on vérifie juste si elles sont identiques.

Faudrait aussi vérifier que N peut s'écrire sous la forme unique de n termes et pas plus ou pas moins non ?

Posté par
mousse42re : Entier en base deux 12-10-18 à 12:17

Salut Ramanujan :
Suppose que ta premier suite est (0,1,0,1) et la seconde (1,1,0,1,0,0,1) alors la première sera (0,1,0,1,0,0,0).


Sinon un exercice intermédiaire :

Citation :

Division euclidienne dans \mathbb{N}
Soit (a,b)\in \mathbb{N}\times \mathbb{N}^*, montrer qu'il existe un unique couple (q,r)\in\mathbb{N}^2 tel que :

\left\lbrace \begin{array}{ll}a=bq+r\\0\le r<b\end{array}\right.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 12:41

Ah d'accord Mousse mais pourquoi cet exo ?

J'ai utilisé ce théorème pour la question  !

Supposons que (d_ 0,d_1,...d_{n-1}) et (d'_ 0,d'_1,...d'_{n-1}) sont 2 suites possibles.

Récurrence :

Initialisation :
Au rang n=2 on a :
Soit  (d_ 0,d_1) et  (d'_ 0,d'_1)

Or : N=d_0 + 2d_1 = d'_0 + 2d'_1

Mais on sait que : d_{n-1}=1 donc d_1=1

D'où : d_0 + 2 = d'_0 + 2d'_1

Là je bloque

Posté par
mousse42re : Entier en base deux 12-10-18 à 12:49



N=d_0+d_12+d_22^2\cdots d_{n-1}2^{n-1}

Donc N=d_0+2(d_1+d_22+\cdots d_{n-1}2^{n-2})

On a bien une forme en N=2q+d_0 avec q=(d_1+d_22+\cdots d_{n-1}2^{n-2})

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 12:51

mousse42 @ 12-10-2018 à 12:49



N=d_0+d_12+d_22^2\cdots d_{n-1}2^{n-1}

Donc N=d_0+2(d_1+d_22+\cdots d_{n-1}2^{n-2})

On a bien une forme en N=2q+d_0 avec q=(d_1+d_22+\cdots d_{n-1}2^{n-2})


Ca je l'ai déjà démontré à la question 2. Plutôt facile.

Posté par
Poncarguesre : Entier en base deux 12-10-18 à 12:52

La question 2 règles immédiatement la question, d_0 est le reste de la division par 2, et par réccurence d_{p+1} est le reste de la division de (n-(d_0+...+d_p 2^p))2^{-(p+1)} par 2

Posté par
mousse42re : Entier en base deux 12-10-18 à 12:53

oui mais tu as l'unicité de d_0 et par itération successive tu montres l'unicité des d_i

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 12:58

Bon je crois avoir trouvé pour l'initialisation :

N=d_0 + 2 = d'_0 + 2d'_1

On a : N=2q+r où (q,r) sont uniques et ici on a : q=1 et r=d_0

Par unicité : d'_1 = 1=d_1 et d'_0=d_0

Je vais essayer l'hérédité.

Posté par
mousse42re : Entier en base deux 12-10-18 à 13:17

Laisse tomber le raisonnement par récurrence pour l'instant.

Il faut que tu comprennes le mécanisme.

Montre maintenant que d_1 est unique puis ensuite d_2 .

Quand tu auras terminé, tu rédigeras une belle récurrence

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 13:24

Hérédité :

J'ai pas trop compris comment N peut passer d'une somme qui termine à n-1 en une somme qui termine à n

Supposons que au rang n-1 on a : (d_0,...,d_{n-1})=(d'_0,...,d'_{n-1})

Or \sum_{k=0}^{n} d_k 2^k =\sum_{k=0}^{n-1} d_k 2^k + d_n 2^n

\sum_{k=0}^{n} d'_k 2^k =\sum_{k=0}^{n-1} d'_k 2^k + d'_n 2^n

Là je suis bloqué

Posté par
luzakre : Entier en base deux 12-10-18 à 13:27

Toujours à compliquer des choses simples !
1. Pour commencer, le nombre de chiffres est forcément le même : pourquoi crois-tu qu'on fait établir l'encadrement  

Citation :
Montrer que 2^{n-1} \leq N \leq 2^n -1

2. Si tu as démontré que d_0 est le reste de la division de N par 2, tu as forcément d_0=d'_0 (les divisions euclidiennes définissent un reste unique  et un quotient unique).
En supposant 0\leqslant k\leqslant p<n\implies d_k=d'_k, tu notes  

N'=\dfrac{N-\sum_{0\leqslant k\leqslant p}d_k2^k}{2^p}

et tu vois que N' admet les développements d_{p+1},\dots,d_n,\;\;d'_{p+1},\dots,d'_n et c'est fini!

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 13:35

luzak @ 12-10-2018 à 13:27

Toujours à compliquer des choses simples !
1. Pour commencer, le nombre de chiffres est forcément le même : pourquoi crois-tu qu'on fait établir l'encadrement  
Citation :
Montrer que 2^{n-1} \leq N \leq 2^n -1

2. Si tu as démontré que d_0 est le reste de la division de N par 2, tu as forcément d_0=d'_0 (les divisions euclidiennes définissent un reste unique  et un quotient unique).
En supposant 0\leqslant k\leqslant p<n\implies d_k=d'_k, tu notes  

N'=\dfrac{N-\sum_{0\leqslant k\leqslant p}d_k2^k}{2^p}

et tu vois que N' admet les développements d_{p+1},\dots,d_n,\;\;d'_{p+1},\dots,d'_n et c'est fini!


Je vois pas le rapport entre l'inégalité démontrée et le fait qu'on ait le même nombre de chiffres.

Pour la récurrence j'ai absolument rien compris.  J'ai l'impression que c'est vous qui compliquez.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 13:39

mousse42 @ 12-10-2018 à 13:17

Laisse tomber le raisonnement par récurrence pour l'instant.

Il faut que tu comprennes le mécanisme.

Montre maintenant que d_1 est unique puis ensuite d_2 .

Quand tu auras terminé, tu rédigeras une belle récurrence


En décomposant la somme ?

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 13:42

Honnêtement Luzak vous écrivez des choses trop compliquées pour moi, des p,k je sais pas d'où ils sortent, un N' je sais pas d'où il sort, à chaque fois vous me perdez.
J'ai déjà du mal donc...

Vos raisonnements sont sûrement nikel mais j'ai pas le niveau pour les comprendre.

J'ai besoin de choses simples.

Posté par
mousse42re : Entier en base deux 12-10-18 à 13:46



N=d_0+d_12+d_22^2\cdots d_{n-1}2^{n-1}

Donc N=\underbrace{d_0}_{r}+2(\underbrace{d_1+d_22+\cdots d_{n-1}2^{n-2}}_{q})

Donc le coupe (q,r) est unique.

Et tu recommences avec q

q=d_1+2[d_2+\cdots d_{n-1}2^{n-3}]

Posté par
verdurinre : Entier en base deux 12-10-18 à 13:46

Bonjour,
la suite \bigl(2^k\bigr)_{k\in\N} est strictement croissante.

Mais je ne vois pas pourquoi faire une démonstration par récurrence alors que les d_i sont obtenus par un algorithme déterministe.

mousse42 t'a proposé de l'écrire dans le sens « petit-boutien »

Si tu préfères tu peux l'écrire dans le sens « gros-boutien » :
\forall N\in\N\ \exists!\,n\in\N\quad 2^n\leqslant N<2^{n+1}
On a ainsi la valeur de n et on recommence avec N-2^n

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 13:49

@Verdurin

Je comprends pas le rapport entre la suite (2^k) est croissante et le nombre de chiffres de N est unique.

Posté par
mousse42re : Entier en base deux 12-10-18 à 13:57

merci Verdurin, je ne connaissais pas ce terme.

Posté par
verdurinre : Entier en base deux 12-10-18 à 13:57

Si \bigl(U_n\bigr)_{n\in\N} est une suite d'entiers strictement croissante alors quelque soit l'entier N il existe un unique entier n tel que UnN<Un+1.

Posté par
luzakre : Entier en base deux 12-10-18 à 14:06

Citation :

Je vois pas le rapport entre l'inégalité démontrée et le fait qu'on ait le même nombre de chiffres.

Combien de n penses-tu pouvoir définir à partir de cet encadrement ?
Ne vois-tu pas que n-1 est simplement la partie entière de \log_2(N) ?

Citation :

Honnêtement Luzak vous écrivez des choses trop compliquées pour moi, des p,k je sais pas d'où ils sortent, un N' je sais pas d'où il sort, à chaque fois vous me perdez.

Comment fais-tu une hérédité de récurrence sinon  supposer que la propriété est vraie pour un entier p et essayer d'établir qu'elle est vraie aussi pour
Citation :
p+1
?
Et tu oses ajouter l'adverbe "honnêtement" ?

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 14:07

mousse42 @ 12-10-2018 à 13:46



N=d_0+d_12+d_22^2\cdots d_{n-1}2^{n-1}

Donc N=\underbrace{d_0}_{r}+2(\underbrace{d_1+d_22+\cdots d_{n-1}2^{n-2}}_{q})

Donc le coupe (q,r) est unique.

Et tu recommences avec q

q=d_1+2[d_2+\cdots d_{n-1}2^{n-3}]


Bien vu Mousse

Je pars sur votre méthode.

J'ai donc : (d_0,q) unique où : q=\sum_{1}^{n-1} d_k 2^{k-1}

Mais : q=d_1 + 2 \sum_{k=2}^{n-1} d_k 2^{k-2}

J'ai (d_1,q') unique et q' = \sum_{k=2}^{n-1} d_k 2^{k-2} unique.

Maintenant faut que je fasse une récurrence ou juste des itérations ?

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 14:14

luzak @ 12-10-2018 à 14:06

Citation :

Je vois pas le rapport entre l'inégalité démontrée et le fait qu'on ait le même nombre de chiffres.

Combien de n penses-tu pouvoir définir à partir de cet encadrement ?
Ne vois-tu pas que n-1 est simplement la partie entière de \log_2(N) ?

[quote]

Je ne comprends pas les questions.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 14:14

Luzak je n'ai pas compris vos questions concernant l'inégalité.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 14:17

verdurin @ 12-10-2018 à 13:57

Si \bigl(U_n\bigr)_{n\in\N} est une suite d'entiers strictement croissante alors quelque soit l'entier N il existe un unique entier n tel que UnN<Un+1.


Pas compris.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 14:29

2^{n-1} \leq N \leq 2^n -1

Il faut montrer que n est unique.

Or : 2^n = e^{n ln(2)}

Soit : e^{(n-1) ln(2)} \leq N \leq e^{n ln(2)} - 1

Après je vois pas.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 14:45

Cette démonstration est-elle valable ?

N=d_0+2 \sum_{1}^{n-1} d_k 2^{k-1} où q_0=\sum_{1}^{n-1} d_k 2^{k-1} donc d_0 est unique.

Or : q_0=\sum_{1}^{n-1} d_k 2^{k-1} = d_1 + 2\sum_{2}^{n-1} d_k 2^{k-2} où : q_1 =\sum_{2}^{n-1} d_k 2^{k-2} donc d_1 est unique

q_1=d_2 + 2\sum_{3}^{n-1} d_k 2^{k-3} où q_2 =\sum_{3}^{n-1} d_k 2^{k-3} donc d_2 est unique.

Par itération d_{n-1} est unique.

Je vois pas comment poser une récurrence ici.

Posté par
Poncarguesre : Entier en base deux 12-10-18 à 15:00

Ben oui c'est correct.
Une itération ou une récurrence ca revient au meme.
Tu supposes que tu as prouvé d_0,...d_k unique, et tu prouve d_{k+1} unique, c'est ton "itération".

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 15:13

@Poncargues

J'ai pas réussi à rédiger la récurrence à partir de mon raisonnement. Je vois pas comment procéder ici.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 15:28

Verdurin

Il est clair que : 2^n - 1 < 2^{n+1}
Donc : 2^n \leq N <  2^{n+1}

Ça sort d'où cette propriété montrant que n est unique ? J'ai jamais étudié ça.
\forall N\in\N\ \exists!\,n\in\N\quad 2^n\leqslant N<2^{n+1}

Posté par
Camélia Correcteurre : Entier en base deux 12-10-18 à 15:31

Bonjour

Ca sort de la définition d'une suite qui tend vers +\infty.

Il me semble que tu n'as jamais hésité à écrire des nombres décimaux, donc tu as du voir une démonstration de ladite écriture. Ici, c'est pareil!

Posté par
carpediemre : Entier en base deux 12-10-18 à 15:33

salut

je ne comprends pas pourquoi faire compliqué quand on peut faire simple !!

n = \sum_0^m a_k2^k = \sum_0^m b_k2^k

n = a_0 + 2p = b_0 + 2q donc par différence a_0 - b_0 \equiv 0  [2]

et par définition de la division euclidienne a_0 = b_0

PS : écrire mathématiquement ce que signifie rouge

je recommence alors avec le nombre n_1 = n - a_0 = a_1 + 2p_1 = b_1 + 2q_1

...

en particulier on voit que faire cette démonstration c'est simplement (et équivalent à) prouver l'unicité de la division euclidienne ...

je préfère prouver cette unicité ... et ne pas m'em... avec une récurrence inutile ...

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 15:43

Camélia @ 12-10-2018 à 15:31

Bonjour

Ca sort de la définition d'une suite qui tend vers +\infty.

Il me semble que tu n'as jamais hésité à écrire des nombres décimaux, donc tu as du voir une démonstration de ladite écriture. Ici, c'est pareil!


Non jamais vu ça je comprends pas d'où ça sort.

Posté par
Camélia Correcteurre : Entier en base deux 12-10-18 à 15:44

Ecris que \lim_{n\to +\infty}2^n=+\infty

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 15:44

Je connais pas votre théorème et pas compris ce qu'a dit Luzak avec le Log donc faudrait que je démontre en utilisant l'égalité que n = n'

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 15:45

Camélia @ 12-10-2018 à 15:44

Ecris que \lim_{n\to +\infty}2^n=+\infty


Quel est le rapport avec l'unicité de n ?

Posté par
Camélia Correcteurre : Entier en base deux 12-10-18 à 15:46

Si en plus tu refuses de faire ce que nous disons… tu n'as qu'à te débrouiller.
Il y a dans ce topic au moins 5 démonstrations de l'existence du développement dyadique!

Posté par
mousse42re : Entier en base deux 12-10-18 à 16:31

\forall N\in\N\ \exists!\,n\in\N\quad 2^n\leqslant N<2^{n+1}

On suppose l'existence d'un n tel que 2^n\leqslant N<2^{n+1}

Et on regarde si il existe un p tel que p\ne n et
2^p\leqslant N<2^{p+1}

si p<n on a donc  N <2^{p+1}\le 2^n
or N\ge 2^n, contradiction.

si p>n

2^{n+1}\le2 ^{p}\le N or n<2^{n+1} contradiction.

Sous l'hypothèse de l'existence, on a montré l'unicité.

J'espère que c'est juste  

Posté par
mousse42re : Entier en base deux 12-10-18 à 16:41

existence :
2^n\leqslant N<2^{n+1}\iff n\ln 2\le \ln N<(n+1)\ln 2 \iff n\le \dfrac{\ln N}{\ln 2}<n+1

Donc n=\left\lfloor  \dfrac{\ln N}{\ln 2}\right\rfloor

On vérifie avec une application numérique

N=1111, on a donc n=10

2^{10}\le 1111<2^{11}  donne 1024\le 1111<2048

Posté par
carpediemre : Entier en base deux 12-10-18 à 17:32

franchement !!

\forall N\in\N\ \exists!\,n\in\N\quad 2^n\leqslant N<2^{n+1}

par définition de la définition euclidienne apprise en primaire pour tout entier N et pour tout entier n il existe un unique entier q et un unique entier r vérifiant 0 \le r < 2^n tel que N = 2^nq + r

les intervalles [0, 0] et [2^k, 2^{k + 1[ forment une partition de \N (k dans \N) donc N appartient à un unique de ces intervalles et n est unique

et pur ce n on a donc 2^n \le N < 2^n + 2^n = 2^{n + 1}

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 18:33

Mousse super ! Vous êtes le seul que j'arrive à comprendre, vos 2 méthodes pour montrer l'unicité de n j'ai tout compris

Pourriez vous m'aider à faire la récurrence :

carpediem @ 12-10-2018 à 17:32

franchement !!

\forall N\in\N\ \exists!\,n\in\N\quad 2^n\leqslant N<2^{n+1}

par définition de la définition euclidienne apprise en primaire pour tout entier N et pour tout entier n il existe un unique entier q et un unique entier r vérifiant 0 \le r < 2^n tel que N = 2^nq + r

les intervalles [0, 0] et [2^k, 2^{k + 1[ forment une partition de \N (k dans \N) donc N appartient à un unique de ces intervalles et n est unique

et pur ce n on a donc 2^n \le N < 2^n + 2^n = 2^{n + 1}


Rien compris

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 18:35

mousse42 @ 12-10-2018 à 16:41

existence :
2^n\leqslant N<2^{n+1}\iff n\ln 2\le \ln N<(n+1)\ln 2 \iff n\le \dfrac{\ln N}{\ln 2}<n+1

Donc n=\left\lfloor  \dfrac{\ln N}{\ln 2}\right\rfloor

On vérifie avec une application numérique

N=1111, on a donc n=10

2^{10}\le 1111<2^{11}  donne 1024\le 1111<2048


Super Mousse j'ai tout compris et votre autre méthode aussi nikel
Je sais pas pourquoi y a que vous que j'arrive à comprendre, peut être parce que vous êtes étudiant comme moi

Pourriez vous m'aider pour la récurrence :

J'en étais à :

N=d_0+2 \sum_{1}^{n-1} d_k 2^{k-1} où q_0=\sum_{1}^{n-1} d_k 2^{k-1} donc d_0 est unique.

Or : q_0=\sum_{1}^{n-1} d_k 2^{k-1} = d_1 + 2\sum_{2}^{n-1} d_k 2^{k-2} où : q_1 =\sum_{2}^{n-1} d_k 2^{k-2} donc d_1 est unique

q_1=d_2 + 2\sum_{3}^{n-1} d_k 2^{k-3} où q_2 =\sum_{3}^{n-1} d_k 2^{k-3} donc d_2 est unique.

Par itération d_{n-1} est unique.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 18:36

@Carpediem

Honnêtement je comprends rien à votre raisonnement.

Posté par
carpediemre : Entier en base deux 12-10-18 à 18:48

alors c'est bien triste ...

puisque c'est ce que j'ai appris en primaire quand j'ai appris la division euclidienne !!! (avec un entier un peu plus compliqué je le concède puisqu'on travaille avec 2^n)

Posté par
luzakre : Entier en base deux 12-10-18 à 18:48

Bref, mauvaise volonté à tous les étages !
Et tu as écrit "honnêtement c'est trop compliqué", sans faire le moindre effort !

Quelle différence entre ce qu'a écrit mousse42 à 16:41 et ce que j'ai dit à 13:27 ?
n (ou n-1 : énoncé original) est une partie entière d'où unicité.

@carpediem :
il refuse ton approche parce qu'il a un corrigé qui fait une récurrence.
Sauf que son corrigé fait une démonstration d'unicité par récurrence ce qui est souvent contestable.

Posté par Profil Ramanujanre : Entier en base deux 12-10-18 à 18:50

Vous sortez tous d'une ENS ou quoi ? Généralement ces gens là n'arrivent pas à se mettre au niveau des autres moins doués.

Vous expliquez pas les transitions entre les lignes. Je comprends pas le passage de la ligne 1 à la ligne 2 et celui de la ligne 2 à la ligne 3.

1 2 +


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !