Peut-être plus accessible avec une récurrence d'ordre un. Soit $u_{1}=1$ et pour $n\geq2$
$$u_{n}=\frac{u_{n-1}+n}{(u_{n-1},n)}$$ Montrer que $u_{n}$ n'est jamais égal à $6$. Pour l'instant je bloque . Cette suite commence ainsi :
Suite
Bonjour, bonsoir
Soit la suite définie par $u_{1},u_{2}$ entiers non nuls et $$u_{n}=\frac{u_{n-1}+u_{n-2}+n}{\left(u_{n-1},u_{n-2},n\right)},$$ où $\left(x,y,z\right)$ désigne le pgcd de $x,y,z$. J'observe que quelles que soient les valeurs de départ $u_{1},u_{2}$ le rapport $\frac{u_{n}}{u_{n-1}}$ tend vers $\frac{1+\sqrt{5}}{2}$. Est-ce démontrable ? À vue d’œil on se doute que la suite peut se comporter en moyenne comme celle de Fibonacci. Mais ce n'est pas un argument !
Soit la suite définie par $u_{1},u_{2}$ entiers non nuls et $$u_{n}=\frac{u_{n-1}+u_{n-2}+n}{\left(u_{n-1},u_{n-2},n\right)},$$ où $\left(x,y,z\right)$ désigne le pgcd de $x,y,z$. J'observe que quelles que soient les valeurs de départ $u_{1},u_{2}$ le rapport $\frac{u_{n}}{u_{n-1}}$ tend vers $\frac{1+\sqrt{5}}{2}$. Est-ce démontrable ? À vue d’œil on se doute que la suite peut se comporter en moyenne comme celle de Fibonacci. Mais ce n'est pas un argument !
Réponses
-
Bonjour, c'est le genre de questions intouchables. Peux-tu donner les 100 premières valeurs de la suite ainsi que ce pgcd pour voir.
Y a-t-il un but ou un intérêt de cette suite ?Le 😄 Farceur -
Salut. Oui je peux donner les 100 premières valeurs de cette suite pour par exemple u1=u2=1. J'arrive dans 10 minutes.Quel est l'intérêt ? Satisfaire une curiosité personnelle ! Ce n'est peut être pas si intouchable.
-
$\renewcommand{\gcd}{\mathrm{pgcd\,}}$Voici ce que j'obtiens pour $u_n $ avec $u_1=u_2=1$ . Les colonnes donnent $n$, $u_n$ et $\gcd(u_{n-1},u_{n-2},n)$. On voit que le $\gcd$ c'est souvent $1$ ce qui explique cela mais comment quantifier ce souvent ?erreur de données
-
Je voulais savoir si ton pgcd est égal à1 à partir d'un certain rang. On sait que le pgcd de $F_n,F_{n-1}$, où $F_n$ est la suite de Fibonacci, est égal à 1.
J'avais cru que ta suite était croissante (pour $n=50$, elle diminue).Le 😄 Farceur -
J'ai recalculé avec $u_1=u_2=1$ . Les colonnes donnent $n$, $u_n$ et $\gcd(u_{n},u_{n-1},n+1)$.3 5 1
4 10 5
5 4 2
6 10 1
7 21 1
8 39 3
9 23 1
10 72 1
11 106 2
12 95 1
13 214 2
14 323 1
15 552 8
16 891 1
17 1460 2
18 2369 1
19 3848 4
20 6237 21
21 10106 2
22 16365 1
23 26494 2
24 42883 1
25 69402 2
26 112311 9
27 60580 4
28 172919 1
29 233528 2
30 406477 1
31 640036 4
32 1046545 1
33 1686614 2
34 2733193 1
35 4419842 2
36 7153071 1
37 11572950 2
38 18726059 1
39 30299048 8
40 49025147 1
41 79324236 6
42 128349425 1
43 207673704 4
44 336023173 1
45 543696922 2
46 879720141 1
47 1423417110 6
48 767712433 1
49 2191129592 2
50 2958842075 1
51 5149971718 2
52 8108813845 1
53 13258785616 2
54 21367599515 5
55 34626385186 2
56 55993984757 1
57 90620370000 2
58 146614354815 1
59 237234724874 2
60 383849079749 1
61 621083804684 2
62 1004932884495 3
63 1626016689242 2
64 2630949573801 1
65 4256966263108 2
66 6887915836975 1
67 11144882100150 2
68 18032797937193 3
69 9725893345804 2
70 27758691283067 1
71 37484584628942 2
72 65243275912081 1
73 102727860541096 2
74 167971136453251 1
75 270698996994422 2
76 438670133447749 7
77 709369130442248 2
78 1148039263890075 1
79 1857408394332402 2
80 3005447658222557 1
81 4862856052555040 2
82 7868303710777679 1
83 12731159763332802 6
84 20599463474110565 5
85 33330623237443452 2
86 53930086711554103 1
87 87260709948997642 2
88 141190796660551833 1
89 228451506609549564 18
90 123214101090033829 1
91 351665607699583484 4
92 474879708789617405 1
93 826545316489200982 2
94 1301425025278818481 1
95 2127970341768019558 2
96 3429395367046838135 1
97 5557365708814857790 2
98 8986761075861696023 1
99 14544126784676553912 4
100 23530887860538250035 1
-
On ne peut rien en tirer avec le n+1Le 😄 Farceur
-
Pardon? Sinon voici un graphique donnant $u_n/u_{n-1}$ pour $n$ jusqu'à $2000$. On a l'impression que ça colle au nombre d'or à partir d'un moment.
-
A 1% près ?---------> []
-
Etrange, peux-tu aller jusqu'à 5000 ?Le 😄 Farceur
-
Je ne comprends pas la remarque de J lapin.
-
-
Il me semble que $u_n/u_{n-1}$ tend vers le nombre d'or si et seulement si $\left(u_{n-1},u_{n-2},n\right)=1$ à partir d'un certain rang.
-
D'accord avec JLT, pour le sens direct on utilise qu'une suite d'entiers convergente est stationnaire
Pour la réciproque on aura la suite u de la forme $\forall n\ge n_0,\quad u_n=a\phi^n+b(\frac {-1}{\phi})^n+\alpha n+\beta\sim a\phi^n$Le 😄 Farceur -
Pour le cas $(u_1,u_2)=(1,1)$ il semble en effet que $(u_{n-1},u_{n-2},n)=1$ à partir de $n=22933$ mais je ne vois pas comment le montrer.
-
Juste une question: quel est le logiciel ou langage utilisé par Béotien?
Je ne suis pas accoutumé à des représentation des entiers à longueur variable (et là il doit être sur des centaines d'octets)
Edit : une remarque, le PGCD c'est avec n ou n+1? Dans le message d'intro, c'est n, mais ça ne colle pas avec la liste... -
J'utilise pari gp mais sans assurance que pour les très grands entiers il n'y a pas de pb avec la fonction gcd. Voici mon code pour faire sortir les n tels que le pgcd est >1.u1=1;u2=1;for(n=3,100000,u3=(u2+u1+n)/gcd(u2,gcd(u1,n));p=gcd(u2,gcd(u1,n));u1=u2;u2=u3;if(p>1,print(n," ",p,"")))qui donne5 5
6 2
9 3
12 2
27 3
48 3
......22855 5
22875 3
22880 11
22932 7puis plus rien
-
J'ai l'impression que c'est un bug car je ne vois pas de raison pour que le pgcd soit 1 à partir d'un certain rang.
-
J'ai fait les calculs avec XCas et je ne trouve rien non plus entre 22933 et 500000 mais ça ne prouve rien, après tout il y a un trou entre $n=1444$ et $n=16781$.
-
Merci JLT. Cela en fait quand même un sacré nombre. Faisons confiance à pari gp alors. En prenant $(u_1,u_2)=(1,2)$ je trouve que le pgcd vaut $1$ à partir de $n=8436$, testé jusqu'à $1.000.000$. Pour $(u_1,u_2)=(1,3)$ je trouve $9514$.
-
Bonsoir,Juste un petit truc. Si on enlève la division par le PGCD à la relation de récurrence, on trouve alors, sauf erreur de ma part, que l'ensemble des solutions est de forme: $u_n = -(n+3) + \alpha \left(\frac{1 + \sqrt{5}}{2}\right)^n + \beta \left( \frac{1-\sqrt{5}}{2}\right)^n$, où $\alpha$ et $\beta$ constantes dépendantes de $(u_0,u_1)$. J'imagine que ça peut aider à y voir un peu plus clair, mais je ne sais pas comment aller plus loin.
-
@Titi le curieux Ce que tu dis sert ( avec modification : la récurrence commence à partir d'un certain rang, voir mon post) pour démontrer la reciproque de la proposition de JLT.
Vois-tu le sens direct?Le 😄 Farceur -
Ah ouais, désolé. Pour la question, je ne sais pas, j'ai l'impression qu'il n'est pas si évident d'exclure une limite (du rapport $u_{n+1}/u_n$) vers 1. En revanche, je suppose qu'on a ce qu'il faut pour savoir que l'adhérence (de la suite des rapports) est non vide.
-
Connais-tu la preuve de la règle de d'Alembert lorsque la limite de $\frac {u_{n}}{u_{n-1}}\to l>1$?Le 😄 Farceur
-
Euh... Je parlais de la suite de $(u_{n+1}/u_n)_{n\in\mathbb{N}}$, je n'espère pas trouver une suite $u_n$ qui converge (je doute même de l'adhérence non vide).edit : j'étais un peu fatigué: j'ai cru que la proposition était $u_{n+1}/u_n$ converge si et seulement si il existe $k$ tel que $\forall n > k,pgcd(n,u_n,u_{n+1}) = 1$
-
Je te donne les étapes, on suppose que $u_n/u_{n-1}$ tend vers le nombre d'or
1- Montre que $u_n / n$ tend vers $+\infty$ (d'où $\frac n{u_{n-1}}$ tend vers 0)
2- En déduire $\left(u_{n-1},u_{n-2},n\right)$ tend vers 1 en remarquant que $\frac{u_n}{u_{n-1}}=\dfrac {1+\frac{u_{n-2}}{u_{n-1}}+\frac n{u_{n-1}}}{\left(u_{n-1},u_{n-2},n\right)}$.
3- Conclure.
Le 😄 Farceur -
2 3
3 2
4 3
5 8
6 7
7 2
8 5
9 14
10 12
11 23
12 35
13 48
14 31
15 46
16 31
17 48
18 11
19 30
20 5 -
Si on considère l'ordre 3 avec $u_1,u_2,u_3$ des entiers donnés et$$u_{n}=\frac{u_{n-1}+u_{n-2}+u_{n-3}+n}{\left(u_{n-1},u_{n-2},u_{n-3},n\right)}$$on dirait qu'il faut attendre beaucoup moins longtemps pour que le pgcd soit constant égal à 1.Par exemple avec les valeurs de départ (1,1,1,6) avec ce code pari-gp :
u1=1;u2=1;u3=6;for(n=4,100,u4=(u3+u2+u1+n)/gcd(u3,gcd(u2,gcd(u1,n)));p=gcd(u3,gcd(u2,gcd(u1,n))); u1=u2;u2=u3;u3=u4;if(p>1,print(n," ",p,""))) 6 6 14 2 65 5 78 3 85 5
plus rien après 86.Et donc le rapport $u_n/u_{n-1}$ tendrait vers la racine réelle de $P(x)=x^3-x^2-x-1$. -
Bonjour l'ami, peux-tu me sous-traiter cet exercice.
Soiit la suite définie par $u_{1},u_{2}$ entiers non nuls avec leur pgcd égal à 1et
$$u_{n}=\frac{u_{n-1}+u_{n-2}}{\gcd(u_{n-1},u_{n-2})},$$
Peux-tu dire quoi sur cette suite ?Le 😄 Farceur -
Je l'ai écartée car pas intéressante le pgcd est 1 rapidement.
-
Pour ta récurrence d'ordre1 , ta simulation te suggère quoi comme limite de $u_n / u_{n-1} $.
Le 😄 Farceur -
L'idée de gebrane n'est pas si idiote que cela. Sa suite est celle de Fibonacci si je ne me suis pas trompé. Donc elle est facilement calculable. En utilisant des théorèmes proches de ceux de la barrière, on peut peut-être arriver à quelque-chose de rigoureux...
-
Bonjour @Bibix
Ma suite n'est pas celle de Fibonacci car on a pas nécessairement $u_1=u_2=1$
À démontrer que (mais @Boécien ne trouve pas la question intéressante) $$u_n = u_1F_{n-2} + u_2F_{n-1},\quad \forall n\ge 3,$$ avec $F_n$ la suite de Fibonacci (je rappelle) définie par $u_1=u_2=1$ et $F_n=F_{n-1}+F_{n-2}$Le 😄 Farceur -
Il semble recommandé que tu poses ta question initiale sur la récurrence d'ordre 2 sur MSE en précisant ta simulation qui suggère que u(n)/u(n-1) tend vers le nombre d'or et en démontrant la proposition de GLT pour les intéresser sinon ton fil sera ferméLe 😄 Farceur
-
GLT? C'est un nouveau moteur de voiture? Je vais voir ta suggestion.
-
Ne pas oublier de donner le lienLe 😄 Farceur
-
-
Merci mais ton message est sec, il fallait donner tes simulations numériques et démontrer ce que tu avances comme certitude. Tu peux le modifierLe 😄 Farceur
-
Pourquoi tu ne veux pas mettre ta simulation numérique sur le rapport $u_n / u_{n-1}$
Le 😄 Farceur -
Plutôt le pgcd. C'est fait mais c'est moche
-
ok
Le 😄 Farceur -
Je t'avais dit que ta question était intouchableLe 😄 Farceur
-
Qu'est ce qui te fait dire ça? Tu veux dire que les mathématiques ne sont pas prêtes? Vu qu'à l'ordre $3$ ça à l'air d'être "encore plus vrai" peut être est-ce montrable pour un ordre disons $m>2$.
-
Salut
En remarquant qu'à chaque étape, $\max (u_{n-1}, u_{n-2}, n)=n$ et $\min (u_{n-1}, u_{n-2}, n)=1$, on pose $$a_{n}=\frac{u_{n-1}+u_{n-2}+n}{n}\quad\text{et}\quad b_{n}=u_{n-1}+u_{n-2}+n.$$ Et de là on a donc $$a_{n}\leqslant u_{n}\leqslant b_{n}.$$ Ensuite si on peut démontrer que $$\lim \limits_{n\to +\infty}\frac{a_{n}}{a_{n-1}}=\lim \limits_{n\to +\infty}\frac{b_{n}}{b_{n-1}}=\frac{1+\sqrt{5}}{2}$$ on peut conclure, non ?
-
Oui, mais cela revient au même. Par contre, je pense que l'approche que j'avais proposé peut être pertinente (avec les théorèmes de la barrière). On peut en effet remarquer que :$$ \forall (p, q, n) \in \mathbb{N}^*, \quad \frac{p + q}{\gcd(p, q)} \leqslant \frac{p + q + n}{\gcd(p, q, n)} \leqslant p + q + n$$Donc par exemple pour $f(p,q) = \frac{p + q}{\gcd(p, q)}$, on définit $v_n = f(v_{n-1}, v_{n-2})$ ce qui permet d'écrire :$$\begin{cases} & v_1 = u_1, v_2 = u_2 \\ & v_n = f(v_{n-1}, v_{n-2}) \\ & u_n \geqslant f(u_{n-1}, u_{n-2}) \end{cases} $$D'où l'on pourrait peut-être conclure (par analogie avec les théorèmes du continu) que $\forall n \in \mathbb{N}^*, u_n \geqslant v_n$. Le seul hic, c'est que les théorèmes de la barrière en version discrète sont compliqués (et qu'en plus, ce serait de l'ordre $2$ donc c'est vraiment pas sûr qu'on arrive à quelque-chose mais bon...).
-
Bonjour Bibix. Tu peux donner un exemple d'application de ces théorèmes de la barrière? Je suppose que c'est dans le cadre des equa diff.
-
En essayant de généraliser l'ordre 2 voici une observation expérimentale. Soit $a,b$ des entiers strictement positifs et soit la suite $u_{n}$ définie par $\left(u_{1},u_{2}\right)\in\left(\mathbb{N^{\star}}\right)^{2}$ et$$u_{n}=\frac{au_{n-1}+bu_{n-2}+n}{\gcd\left(u_{n-1},u_{n-2},n\right)}$$alors $\frac{u_{n+1}}{u_{n}}$ converge vers $\frac{a+\sqrt{a^{2}+4b}}{2}$ la plus grande racine réelle de $x^{2}-ax-b$. Mais ce n'est visiblement pas le cas de la suite définie par $\left(v_{1},v_{2}\right)\in\left(\mathbb{N^{\star}}\right)^{2}$ et$$v_{n}=\frac{av_{n-1}+bv_{n-2}+n}{\gcd\left(av_{n-1},bv_{n-2},n\right)}$$Par exemple pour $(a,b)=(1,2)$ on a clairement $\frac{u_{n+1}}{u_{n}}$ qui converge vers $2$ tandis que $\frac{v_{n+1}}{v_{n}}$ semble même non borné.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres