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 ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Partager :

Numération - question sur la récurrence

Posté par
rcompany 19-02-19 à 02:52

Exercice:

\text{Soit }n\in \mathbb{N}^*, \text{ montrer qu'il existe p}\in \mathbb{N}\;et\;n_0,n_1,...,n_p\;\in \{1;2\}\text{ uniques tels que }n=\sum_{k=0}^p n_k 2^k

Je reformule la proposition pour faciliter la notation:

\forall n\in\mathbb{N}^*, \exists (p,(a_n)_{0\leq n\leq p})\text{ unique avec }p\in \mathbb{N}\text{ et }(a_n)_{0\leq n \leq p}\text{ suite de }\mathbb{N}\text{ dans }\{1;2\}\text{ tel que: }  \cr n=\sum_{i=0}^p a_i 2^i

Montrons l'existence:

\text{vraie pour n=1 et n=2:}\;1=1.2^0\;et\;2=2.2^0 \\ \cr \\ \text{Supposons l'existence vraie pour n quelconque de }\mathbb{N}^*:\cr \text{ il existe p de }\mathbb{N} \text{ et}(a_n)\text{ de }\mathbb{N}\text{ dans}\{1;2\}\text{ tels que }n=\sum_{i=0}^p a_i 2^i

2n+1=1+2\sum_{i=0}^p a_i 2^i=1+\sum_{i=1}^{p+1}a_{i-1}2^i \cr \\ \text{Posons }(b_n)_{0\leq n\leq p+1}\text{ telle que } b_0=1\;et\;\forall i \in\{1;2;...p+1\},\;b_i=a_{i-1} \cr \\ \text{On a bien }2n+1=\sum_{i=0}^{p+1} b_i2^i\;et\; \forall \; i\in \{0;1;2;...;p+1\},\; b_i\in\{1;2\}

Et ensuite:

2n+2=1+(2n+1)=1+\sum_{i=0}^{p+1} b_i2^i=(1+b_0)+\sum_{i=1}^{p+1} b_i2^i=2+\sum_{i=1}^{p+1} b_i2^i\cr \\ \text{et en posant }(c_n)\text{ telle que } c_0=2\text{ et } c_i=b_i\text{ pour }i\geq 1 \cr \\ \text{on a bien }2n+2=\sum_{i=0}^{p+1} c_i 2^i \text{avec } \forall i \in \{0;1;2;...;p+1\},\; c_i\in \{1;2\}

Question: peut-on parler de "récurrence", i.e. que l'existence est vraie pour tout n de \mathbb{N}^* puisqu'à partir de 1 et 2 et des suites n\mapsto 2n+1\text{ et } n\mapsto 2n+2 on couvre l'ensemble de \mathbb{N}^*?

On peut résoudre cet exercice en particulier avec une récurrence traditionelle:

L'existence est vraie pour n=1.

Supposons-la vraie pour n quelconque de \mathbb{N}^*

n+1=1+\sum_{i=0}^p a_i 2^i\\ \\ \\ \bullet \text{ Si }\forall i\in \{0;1;2;...;p\},\;a_i=2 \\ \\ n+1= 1+\sum_{i=1}^{p+1}1\times 2^i=\sum_{i=0}^{p+1} b_i2^i \\ \text{en posant }b_i=1 \text{ pour tout i de \{1;2;...;p+1\}}

\bullet \text{ Si }\exists k\in \{0;1;2;...;p\} \text{ tel que } a_k=1 \text{, notons }k_0\text{ le plus petit de ces k}

\text{On a }  \left \{ \begin{array}{l} a_i=2 \text{ pour }i<k_0\\a_k_0=1\\ \end{array}

\begin{array}{rl} \text{et }n+1=&1+\sum_{i=0}^{k_0-1}a_i 2^i+2^{k_0}+\sum_{i=k_0+1}^{p}a_i2^i\\ \\ =&1+\sum_{i=0}^{k_0-1}2\times 2^i +1+\sum_{i=0}^{k_0-1} 2^i +\sum_{i=k_0+1}^{p}a_i2^i \\ \\ &\text{ car } 2^{k_0}=1+\sum_{i=0}^{k_0-1} 2^i\text{ (somme de suite geometrique de premier terme 1 et de raison 2)}\\ \\ =& 2+\sum_{i=1}^{k_0}2^i+\sum_{i=0}^{k_0-1} 2^i +\sum_{i=k_0+1}^{p}a_i2^i \\=&2+2^0 +2^{k_0}+\sum_{i=1}^{k_0-1}2^i+\sum_{i=k_0+1}^{p}a_i2^i\\ \\ =&1\times 2^0+(1+1)\times 2^1 +\sum_{i=2}^{k_0-1}2^i+1\times 2^{k_0}+\sum_{i=k_0+1}^{p}a_i2^i \\ \end{array}

\text{En  posant }(b_n) \text{ telle que }\left \{ \begin{array}{l} b_0=1\\b_1=2\\1<i<k_0\Rightarrow b_i=1\\b_{k_0}=1\\i>k_o\Rightarrow b_i=a_i \end{array}  \cr\cr \text{on a bien }n+1=\sum_{i=0}^p b_i2^i \text{ avec }\forall i\in \{0;1;2;...;p\},\;b_i\in \{1;2\}

\text{L'existence est donc bien vraie pour tout }n\text{ de }\mathbb{N}^*

Posté par
rcompanyre : Numération - question sur la récurrence 19-02-19 à 03:46

Je corrige la fin du post précédent:

n+1 = 1\times 2^0+1\times 2^1 +\sum_{i=2}^{k_0-1} 2^i+1\times 2^{k_0} +\sum_{i=k_0+1}^p \\ \\ \text{En posant }(b_n) \text{ telle que } \left \{ \begin{array}{l} b_i=1\text{ pour }0\leq i\leq k_0\\b_i=a_i \text{ pour }i>k_0 \end{array} \\ \\ \text{On a bien }n+1=\sum_{i=0}^p b_i2^i \text{ avec } \forall i \in \{0;1;2;...;p\},\;b_i\in\{1;2\} \\ \\ \text{L'existence est donc bien vraie pout tout }n \text{ de }\mathbb{N}^*

Posté par
rcompanyre : Numération - question sur la récurrence 19-02-19 à 04:13

dernière correction: b_{k_0}=2

Posté par
luzakre : Numération - question sur la récurrence 19-02-19 à 08:17

Bonjour !
1. Où est la question ?
2. Ta récurrence à deux termes semble logique mais ce n'est plus une récurrence !
Tu devrais t'intéresser au passage à n+1,n+2 (éventuellement en distinguant les cas n pair ou impair).

Pour justifier ce que tu fais il faut "refaire la démonstration de récurrence" .
3. Où est l'unicité ?

Posté par
carpediemre : Numération - question sur la récurrence 19-02-19 à 09:45

salut

je ne vois pas l'intérêt d'une telle question ... surtout en choisissant la suite à valeur dans {1, 2} et pas dans {0, 1} qui donne le développement en base 2 ... bien plus important ...

Posté par
luzakre : Numération - question sur la récurrence 19-02-19 à 11:51

Eh ! bé !
Je n'avais même pas vu qu'il prenait des "chiffres" dans \{1,2\} !
Quel serait le "chiffre" de rang 0 dans l'écriture 6=?\times2^0+1\times 2^1+1\times2^2 ?

Brahmagupta doit se retourner dans sa tombe !
En somme on a un système de numération (sic) où l'opération d'addition a perdu son neutre ! Très commode !

Posté par
carpediemre : Numération - question sur la récurrence 19-02-19 à 12:15

surtout que l'écriture n'est plus unique

6 = 1 \times 2^1 + 1 \times 2^2 = 2 \times 2^0 + 1 \times 2^2



mais il manquerait toujours une puissance de 2 de toute façon ...

Posté par
luzakre : Numération - question sur la récurrence 19-02-19 à 15:03

Ouais !
"Inventer" un système de numération sans le chiffre "0" c'est revenir à la numération romaine. On sait combien il était facile pour les opérations...

L'unicité se retrouve si on impose que toutes les puissances de "2" ont un coefficient.
Le cas du "6" imposerait 6=2\times2^0+2\times2^1

Posté par
rcompanyre : Numération - question sur la récurrence 19-02-19 à 15:09

luzak @ 19-02-2019 à 08:17

Bonjour !
1. Où est la question ?
2. Ta récurrence à deux termes semble logique mais ce n'est plus une récurrence !
Tu devrais t'intéresser au passage à n+1,n+2 (éventuellement en distinguant les cas n pair ou impair).

Pour justifier ce que tu fais il faut "refaire la démonstration de récurrence" .
3. Où est l'unicité ?


1. La question est en rouge au milieu du texte
2. La méthode que j'utilise est-elle valable? S'il ne s'agit pas d'une récurrence bien qu'il y ait initialisation et hérédité, cette méthode porte-t-elle un nom?
On peut démontrer cet exercice en particulier avec une récurrence classique n->n+1, mais au-delà de cet exercice j'aimerais savoir si la méthode est valable: (P vraie pour n=1 et n=2) et (P vraie pour n implique P vraie pour 2n+1 et 2n+2) implique (P vraie pour tout n supérieur à 1)
3. L'unicité est facile à montrer par l'absurde en deux étapes (on suppose qu'on a n=\sum_{i=0}^{p}a_i 2^i=\sum_{i=0}^{q}b_i 2^i avec p\neq q ou (a_n)\neq (b_n) et l'on montre que l'on a forcément p=q puis que (a_n) = (b_n). Je vais la mettre en ligne pour ceux que cela intéresse.

Posté par
rcompanyre : Numération - question sur la récurrence 19-02-19 à 15:12

carpediem @ 19-02-2019 à 09:45

salut

je ne vois pas l'intérêt d'une telle question ... surtout en choisissant la suite à valeur dans {1, 2} et pas dans {0, 1} qui donne le développement en base 2 ... bien plus important ...


La question ne porte pas sur cet exercice en particulier, mais sur la validité de la méthode: (P vraie pour n=1 et n=2) et (P vraie pour n implique P vraie pour 2n+1 et 2n+2) implique (P vraie pour tout n supérieur à 1)

Posté par
carpediemre : Numération - question sur la récurrence 19-02-19 à 15:19

la récurrence ce n'est pas de passer de n à 2n + 1 ou 2n + 2 mais de passer de n à n + 1 ...

et cela que l'on suppose P(k) vraie pour deux ou pour tout les k =< n ...

Posté par
rcompanyre : Numération - question sur la récurrence 19-02-19 à 18:39

Démonstration de l'unicité pour ceux que la résolution de cet exercice en particulier intéresse:

Supposons que l'on ait pour n\in\mathbb{N}^*:

\text{Il existe }p,q\in\mathbb{N}\text{, et }(a_n)_{0\leq n\leq p}\text{ et }(b_n)_{0\leq n\leq q}\text{ deux suites de }\mathbb{N}\text{ dans}\{1;2\}\text{ tels que:}

(p,(a_n))\neq (q,(b_n)) \text{ et }n=\sum_{i=0}^p a_i 2^i=\sum_{i=0}^q b_i 2^i

\text{Supposons que }p<q

\left \{ \begin{array}{l} n=\sum_{i=0}^p a_i 2^i \Rightarrow n\leq \sum_{i=0}^p 2\times 2^i\text{ car }\forall i \in \{0;1;2;...;p\},; a_i\in \{1;2\}\\ \\ n=\sum_{i=0}^q b_i 2^i \Rightarrow n\geq\sum_{i=0}^q 1\times 2^i\text{ car }\forall i \in \{0;1;2;...;q\},; b_i\in \{1;2\} \end{array}

\text{d'où }\sum_{i=0}^q 1\times 2^i\leq\sum_{i=0}^p 2\times 2^i
\text{or } \sum_{i=0}^p 2\times 2^i-\sum_{i=0}^q 1\times 2^i=\sum_{i=1}^{p+1}2^i-\sum_{i=0}^q 2^i=-2^0-\sum_{i=p+2}^q 2^i<0\text{ donc on ne peut pas avoir }p<q

\text{On montre de la même façon de l'on ne peut pas avoir }p>q,\\ \text{et donc si }(p,(a_n))\text{ et }(q,(b_n))\text{ différents existent, alors }p=q

\text{Supposons maintenant qu'il existe }(a_n)\text{ et }(b_n)\text{ différentes  telles que: }n=\sum_{i=0}^p a_i2^i=\sum_{i=0}^p b_i2^i

(a_n)\neq(b_n)\Rightarrow (\exists k \in \{0;1;...;p\}\text{ tel que }a_k\neq b_k)

\text{Soit }k_0\text{ le plus petit de ces }k

\text{On a }\left \{ \begin{array}{l}a_i=b_i \text{ pour }i<k_0 \\[\medskipamount]a_{k_0}\neq b_{k_0}\\[\medskipamount]a_i,b_i \in \{1;2\}\text{ pour }i>k_0 \end{array}

  \begin{array}{ll} \sum_{i=0}^p a_i2^i=\sum_{i=0}^p b_i2^i  &\Leftrightarrow \sum_{i=0}^p a_i2^i-\sum_{i=0}^p b_i2^i=0 \\ &\Leftrightarrow\left \{ \begin{array}{l}\sum_{i=1}^{p} (b_i-a_i)2^i = a_0-b_0 \text{ si }k_0=0 \\\sum_{i=0}^{p-1}(b_i-a_i)2^i = (a_p-b_p)2^p \text{ si } k_0=p \\\sum_{i=0}^{k_0-1}(b_i-a_i)2^i +\sum_{i=k_0+1}^p(b_i-a_i)2^i = (a_{k_0}-b_{k_0})2^{k_0} \text{ si } k_0\neq 0 \text{ et }k_0\neq p\end{array} \\ \\ &\Leftrightarrow \left \{ \begin{array}{l}\sum_{i=1}^{p} (b_i-a_i)2^i = 1\text{ ou } \sum_{i=1}^{p} (b_i-a_i)2^i = -1\text{ si }k_0=0 \text{ car }a_0,b_0\in \{1;2\} \text{ et }a_0\neq b_0 \\(a_p-b_p)2^p=0 \text{ si } k_0=p \text{ car pour tout }i\leq p-1, a_i=b_i\\\sum_{i=k_0+1}^p(b_i-a_i)2^{i-k_0} = 1\text{ ou } \sum_{i=k_0+1}^p(b_i-a_i)2^{i-k_0} = -1 \text{ si } k_0\neq 0 \text{ et }k_0\neq p\end{array}\\ \\ &\Leftrightarrow \left \{ \begin{array}{l}\sum_{i=1}^{p} (b_i-a_i)2^{i-1} = \dfrac{1}{2}\text{ ou }\sum_{i=1}^{p} (b_i-a_i)2^{i-1} = -\dfrac{1}{2}\text{ si }k_0=0 \text{ : impossible car }\sum_{i=1}^{p} (b_i-a_i)2^{i-1} \in \mathbb{Z}\\(a_p-b_p)2^p=0 \text{ si } k_0=p \text{ : impossible car } a_p\neq b_p\\\sum_{i=k_0+1}^p(b_i-a_i)2^{i-k_0-1} = \dfrac{1}{2}\text{ ou } \sum_{i=k_0+1}^p(b_i-a_i)2^{i-k_0-1} = -\dfrac{1}{2} \text{ si } k_0\neq 0 \text{ et }k_0\neq p \text{ : impossible car } \sum_{i=k_0+1}^{p} (b_i-a_i)2^i \in \mathbb{Z}\end{array} \\ \end{array}  

k_0 \text{ n'existe pas et donc }(\exists k \in \{0;1;...;p\}\text{ tel que }a_k\neq b_k)\text{ est fausse, et donc }(a_n)=(b_n)

\text{On a bien montré l'unicité de }(p,(a_n))

\text{Et finalement on a bien:}

\forall n\in \mathbb{N}^*, \exists! (p,(a_n))\text{ avec }p\in\mathbb{N}\text{ et } (a_n)_{0\leq n\leq p}\text{ de }\mathbb{N}\text{ dans }\{1;2\}\text{, tel que }n=\sum_{i=0}^p=a_i 2^i

Posté par
rcompanyre : Numération - question sur la récurrence 19-02-19 à 20:12

carpediem @ 19-02-2019 à 15:19

la récurrence ce n'est pas de passer de n à 2n + 1 ou 2n + 2 mais de passer de n à n + 1 ...

et cela que l'on suppose P(k) vraie pour deux ou pour tout les k =< n ...


Oubliez le mot récurrence. Je sais ce que c'est, merci.

La QUESTION que je pose est de savoir si la méthode qui consiste à:
- prouver une proposition P pour n=1 et n=2,
- montrer que si P est vraie pour n alors elle est vraie pour 2n+1 et pour 2n+2 (2n+1 et 2n+2 héritent de la propriété de n)

est suffisante pour dire que la proposition est vraie pour tout n de \mathbb{N}^*, sachant que tout n de \mathbb{N}^* peut être exprimé comme l'image de 1 ou 2 par une composition des suites n\mapsto2n+1 et n\mapsto 2n+2

\begin{array}{rl}f&\mathbb{N}^*\rightarrow \mathbb{N}^*\\&n\mapsto2n+1\\ \\ g&\mathbb{N}^*\rightarrow \mathbb{N}^*\\&n\mapsto2n+2 \end{array}

\begin{array}{lcll} n &\text{antécédent} &\text{fonction}\cr&&\text{composée}& \\\hline \\3&1&f&3=2\times 1+1=f(1)\\4&1&g&4=2\times 1+2=g(1)\\5&2&f&5=2\times 1+1=f(2)\\6&2&g&6=2\times 1+2=g(2)\\ \\ 7&1&f\circ f&7=2\times 3+1=2\times (2\times 1+1)+1 =f\!\circ\! f(1)\text{  (7 hérite P de 3 par f qui l'hérite de 1 par f)}\\8&1&g\circ f&8=2\times 3+2=2\times (2\times 1+1)+2 =g\!\circ\! f(1)\text{  (8 hérite P de 3 par g qui l'hérite de 1 par f)}\\9&1&f\circ g&9=2\times 4+1=2\times (2\times 1+2)+1 =f\!\circ\! g(1)\text{  (9 hérite P de 4 par f ,4 l'hérite de 1 par g)}\\10&1&g\circ g&10=2\times 4+2=2\times (2\times 1+2)+1 =g\!\circ\! g(1)\text{  (10 hérite P de 4 par g ,4 l'hérite de 1 par g)}\\11&2&f\circ f&11=2\times 5+1=2\times (2\times 2+1)+1 =f\!\circ\! f(2)\text{  (11 hérite P de 5 par f, 5 l'hérite de 2 par f)}\\12&2&g\circ f&12=2\times 5+2=2\times (2\times 2+1)+2 =g\!\circ\! f(2)\text{  (12 hérite P de 5 par g, 5 l'hérite de 2 par f)}\\13&2&f\circ g&13=2\times 6+1=2\times (2\times 2+2)+1 =f\!\circ\! g(2)\text{  (13 hérite P de 6 par f ,6 l'hérite de 2 par g)}\\14&2&g\circ g&14=2\times 6+2=2\times (2\times 2+2)+2 =g\!\circ\! g(2)\text{  (10 hérite P de 6 par g ,6 l'hérite de 2 par g)} \\ \\15&1&f\circ f\circ f&15=2\times 7+1=2\times (f\!\circ\!f(1))+1 = f\!\circ\! f\!\circ\!f(1)\text{  (15 hérite P de 7 par f ,7 l'hérite de 3 par f),3 l'hérite de 1 par f)}\\16&1&g\circ f\circ f&16=2\times 7+2=2\times (f\!\circ\!f(1))+2=g\!\circ\! f\!\circ\!f(2)\text{  (16 hérite P de 7 par g ,7 l'hérite de 3 par f, 3 l'hérite de 1 par f )}\\\text{    ...etc...} \\ \end{array}

Posté par
carpediemre : Numération - question sur la récurrence 19-02-19 à 20:57

Citation :
Supposons que l'on ait pour n\in\mathbb{N}^*:

\text{Il existe }p,q\in\mathbb{N}\text{, et }(a_n)_{0\leq n\leq p}\text{ et }(b_n)_{0\leq n\leq q}\text{ deux suites de }\mathbb{N}\text{ dans}\{1;2\}\text{ tels que:}

\cancel {\red(p,(a_n))\neq (q,(b_n))} \text{ et }n=\sum_{i=0}^p a_i 2^i=\sum_{i=0}^q b_i 2^i

on ne suppose pas qu'ils sont différents ... puisqu'au final ils ne le sont pas !!!

on suppose simplement qu'il y en a deux ... et on démontre que les deux ne font qu'un !! d'ailleurs c'est ce que tu as fait ...

de même on ne suppose pas p < q mais p \le q ... puisqu'au final p = q !!!

et c'est bien compliqué ...

n = \sum_0^p a_k 2^k = \sum_0^q b_k 2^k   donc par différence 0 = \sum_0^p (b_k - a_k) 2^k + \sum_{p + 1}^q b_k 2^k

or par définition des coefficients (dans {1, 2})   \forall k  :  b_k - a_k \ge -1  donc la première somme s vérifie s \ge - \sum_0^p 2^k = 1 - 2^{p + 1}

et  la deuxième somme t est positive et vérifie t \ge 2^{p + 1} \sum_0^{q - p - 1} 2^k = 2^{p + 1}(2^{q - p} - 1)

donc s + t \ge 1 + 2^{p + 1}(2^{q - p} - 2)   et si q > p alors s + t > 0 ...

par conséquent (et par symétrie) on en déduit que p = q

donc n = \sum_0^p a_k 2^k = \sum_0^p b_k 2^k

et toujours par différence 0 = \sum_0^p (a_k - b_k) 2^k

to be continued ...

Posté par
carpediemre : Numération - question sur la récurrence 19-02-19 à 21:00

certes ... tu as raison ... mais je ne vois pas l'intérêt d'une récurrence ... si on le prouve pour un n quelconque ...

Posté par
rcompanyre : Numération - question sur la récurrence 20-02-19 à 01:06

carpediem @ 19-02-2019 à 21:00

certes ... tu as raison ... mais je ne vois pas l'intérêt d'une récurrence ... si on le prouve pour un n quelconque ...


Merci. La question  n'était pas tant sur l'exercice que sur la validité de la méthode. Après il y a plein de problèmes que l'on peut résoudre directement ou par récurrence.

je trouve évidemment plein de littérature sur les récurrences simples et doubles (n à n_1, n+2) mais pour l'instant rien sur des méthodes qui utiliseraient d'autres types d'hérédité.

Si quelqu'un a déjà lu quelque chose sur le sujet...

Posté par
rcompanyre : Numération - question sur la récurrence 20-02-19 à 03:57

carpediem @ 19-02-2019 à 20:57

Citation :
Supposons que l'on ait pour n\in\mathbb{N}^*:

\text{Il existe }p,q\in\mathbb{N}\text{, et }(a_n)_{0\leq n\leq p}\text{ et }(b_n)_{0\leq n\leq q}\text{ deux suites de }\mathbb{N}\text{ dans}\{1;2\}\text{ tels que:}

\cancel {\red(p,(a_n))\neq (q,(b_n))} \text{ et }n=\sum_{i=0}^p a_i 2^i=\sum_{i=0}^q b_i 2^i

on ne suppose pas qu'ils sont différents ... puisqu'au final ils ne le sont pas !!!

on suppose simplement qu'il y en a deux ... et on démontre que les deux ne font qu'un !! d'ailleurs c'est ce que tu as fait ...

de même on ne suppose pas p < q mais p \le q ... puisqu'au final p = q !!!

et c'est bien compliqué ...

n = \sum_0^p a_k 2^k = \sum_0^q b_k 2^k   donc par différence 0 = \sum_0^p (b_k - a_k) 2^k + \sum_{p + 1}^q b_k 2^k

or par définition des coefficients (dans {1, 2})   \forall k  :  b_k - a_k \ge -1  donc la première somme s vérifie s \ge - \sum_0^p 2^k = 1 - 2^{p + 1}

et  la deuxième somme t est positive et vérifie t \ge 2^{p + 1} \sum_0^{q - p - 1} 2^k = 2^{p + 1}(2^{q - p} - 1)

donc s + t \ge 1 + 2^{p + 1}(2^{q - p} - 2)   et si q > p alors s + t > 0 ...

par conséquent (et par symétrie) on en déduit que p = q

donc n = \sum_0^p a_k 2^k = \sum_0^p b_k 2^k

et toujours par différence 0 = \sum_0^p (a_k - b_k) 2^k

to be continued ...


Je ne comprends pas mon erreur.

J`essaie de démontrer  par l'absurde l'unicité du couple (p,(a_n)) en supposant qu'il existe un autre couple (q,(b_n))  satisfaisant la propriété p_n: n=\sum_{i=0}^q b_i2^i et en montrant que l'on arrive à des impossibilités.

Je suppose que (p,(a_n)) et (q,(b_n)) existent et sont différents.

Si deux couples sont différents, ils le sont par leurs premiers éléments ou par leurs seconds.

S'ils le sont par leurs premiers éléments, alors p\neq q, et donc p<q ou p>q. Dans chacun des deux cas (p<q et p>q) on arrive à une impossibilité sous la forme d'une quantité positive, de par l'hypothèse initiale (p<q ou p>q), inférieure à une quantité négative.
On en conclut que l'on a ni p<q ni p>q, i.e. que p=q ce qui invalide l'hypothèse que p\neq q
Une première conclusion est donc que si les deux couples existent et sont différents, ils sont différents par leur deuxièmes éléments.

On suppose alors que (p,(a_n)) et (q,(b_n)) existent, mais cette fois avec p=q et (a_n)\neq(b_n) (on vient de voir qu'ils ne peuvent pas exister, et être différents, avec p\neq q, s'ils satisfont p_n)

On suppose donc maintenant que l'on a (a_n)\neq(b_n) (les deux suites ont p éléments), avec (p,(a_n)) et (p,(b_n)) satisfaisant p_n et l'on arrive à deux impossibilités: soit que les termes de a et b supposés différents sont égaux (le a_{k_0}=b_{k_0}), soit qu'un entier relatif pair est égal à -1 ou +1 (le \sum_{i=k_0+1}^p (a_i-b_i)2^i=1 ou \sum_{i=k_0+1}^p (a_i-b_i)2^i=-1).
On a montré que l'hypothèse (a_n)\neq(b_n) est impossible, et donc que s'il existe un couple (p,(a_n)) vérifiant p_n il ne peut pas exister un couple (p,(b_n)) différent de (p,(a_n)) vérifiant aussi p_n

Au final, on a montré que:
- s'il existe (p,(a_n)) satisfaisant p_n, il ne peut pas exister un couple (q,(b_n)) différent de  (p,(a_n)) satisfaisant p_n si q\neq p
- s'il existe (p,(a_n)) satisfaisant p_n, il ne peut pas exister un couple (p,(b_n)) différent de  (p,(a_n)) satisfaisant p_n

et donc s'il existe (p,(a_n)) vérifiant p_n, il n'existe aucun autre couple (q,(b_n)) satisfaisant p_n

On avait montré l'existence de ((p,a_n)) auparavant, donc on peut affirmer que pour tout n de \mathbb{N}^*,\;(p,(a_n)) vérifiant p_n existe et est unique.

Et je crois que montrer que
\Bigg (\exists (p,(a_n))\text{ tel que } \left \{ \begin{array}{l} p\in\mathbb{N}\\\text{a suite de } \{0;1;2;...;p\}\text{ dans }\{1;2\}\\n=\sum_{i=0}^{p}a_i2^i \end{array}\Bigg )\Rightarrow \Bigg (\nexists (q,(b_n))\text{ tel que } \left \{ \begin{array}{l} (q,(b_n))\neq (p,(a_n))\\q\in\mathbb{N}\\\text{b suite de } \{0;1;2;...;q\}\text{ dans }\{1;2\}\\n=\sum_{i=0}^{q}b_i2^i \end{array}\Bigg )

est équivalent à montrer que:

\Bigg (\exists\;\Big ((p,(a_n))\text{ et }(q,(b_n))\Big) \text{ tels que } \left \{ \begin{array}{l} p,q\in\mathbb{N}\\\text{a suite de } \{0;1;2;...;p\}\text{ dans }\{1;2\}\\\text{b suite de } \{0;1;2;...;q\}\text{ dans }\{1;2\}\\n=\sum_{i=0}^{p}a_i2^i =\sum_{i=0}^{q}b_i2^i \end{array}\Bigg )\Rightarrow (p,(a_n))=(q,(b_n))

et montre l'unicité de \big (p,(a_n)\big) vérifiant p_n

Posté par
luzakre : Numération - question sur la récurrence 20-02-19 à 08:27

Citation :

S'ils le sont par leurs premiers éléments, alors p\neq q, et donc p<q ou p>q. Dans chacun des deux cas (p<q et p>q) on arrive à une impossibilité sous la forme d'une quantité positive, de par l'hypothèse initiale (p<q ou p>q), inférieure à une quantité négative.

C'est loin d'être évident pour q=p+1 et 2\times2^p+\dots=1\times2^{p+1}+\dots.

Posté par
carpediemre : Numération - question sur la récurrence 20-02-19 à 09:08

je ne dis pas que tu as fait des erreurs .. mais des erreurs de rédaction !!

quand on veut supposer l'unicité on en suppose pas qu'il y a deux solutions différentes mais qu'il y a deux solutions !!!

et on prouve que ces deux solutions ne font qu'une !!!

et ces deux solutions ne sont pas différentes puisqu'elles sont égales ... c'est simplement qu'on a noté la même chose de deux façons différentes et on montre que ces deux notations sont égales !!!

pour l'instant je n'ai prouvé que p = q (en montrant que p \le q $ et $ q \le p)

donc quand on écrit n = \sum_0^p a_k2^k = \sum_0^q b_k 2^k je ne fais qu'écrire deux notations de la même formule (il y a un p et un q et des a_k et des b_k)
et prouver l'unicité c'est prouver que ces deux écritures n'en sont qu'une en montrant que p = q et a_k = b_k

...


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 1768 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 !