Suite — Les-mathematiques.net The most powerful custom community solution in the world

Suite

Modifié (10 Sep) dans Arithmétique
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 !
«1

Réponses

  • Modifié (10 Sep)
    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 ?
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (10 Sep)
    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.
  • Modifié (10 Sep)
    $\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
  • Modifié (10 Sep)
    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).
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • 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+1
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • 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 ?
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • 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$
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • 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.
  • Modifié (10 Sep)
    Commence par  démontrer que la suite $(\frac{u_n}{u_{n-1}})_n$ est convergente 
    (Eh , je n'ai pas réfléchi)

    @AD je m'améliore ? Je fais plus attention.
    [ AD]
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (10 Sep)
    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 donne
    5    5
    6    2
    9    3
    12    2
    27    3
    48    3
    ...
    ...
    22855    5
    22875    3
    22880    11
    22932    7

    puis 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? 
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (11 Sep)
    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$?
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (12 Sep)
    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$
  • Modifié (12 Sep)
    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.
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (13 Sep)
    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 :
    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
  • Modifié (14 Sep)
    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$.
  • Modifié (14 Sep)
    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 ?
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Je l'ai écartée car pas intéressante :) le pgcd est 1 rapidement.
  • Modifié (14 Sep)
     ;)
    Pour ta récurrence d'ordre1 , ta simulation te suggère quoi comme limite de $u_n /  u_{n-1} $.
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • 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... 
  • Modifié (14 Sep)
    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}$
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • @gebrane J'ai dit pas intéressante dans le sens où elle ne génère pas un comportement assez bizarre  :D Dans l'absolu c'est intéressant comme montrer que (F(n),F(n+1))=1.
  • Modifié (14 Sep)
    gebrane a dit :
     ;)
    Pour ta récurrence d'ordre1 , ta simulation te suggère quoi comme limite de $u_n /  u_{n-1} $.
    C'est très erratique (pas de limite) mais cela semble borné et je subodore que c'est dense entre les liminf et limsup.
  • Modifié (14 Sep)
    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é
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (14 Sep)
    GLT? C'est un nouveau moteur de voiture? :) Je vais voir ta suggestion.
  • Ne pas oublier de donner le lien
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (15 Sep)
    @gebrane
    Cher ami j'ai posté la question sur MSE. Advienne que pourra.
  • Modifié (15 Sep)
    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 modifier 
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Pourquoi tu ne veux pas mettre ta simulation numérique  sur le rapport $u_n /  u_{n-1}$

    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (16 Sep)
    Plutôt le pgcd. C'est fait mais c'est moche :/
  • Modifié (16 Sep)
    ok

    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Je t'avais dit que ta question était intouchable   :cold_sweat:    
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • 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$.
  • Qu'est ce qui te fait dire ça? Sur MSE :  de coutume, on reçoit rapidement une solution ou une indication . 
    Dans une semaine, si on ne reçoit rien , le dernier recourt c'est MO. On a besoin juste une idée pour la développer ici même !
    dommage que  @Siméon   ne vient plus au forum
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je suis Jack 
  • Modifié (18 Sep)
    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 ?
  • Modifié (18 Sep)
    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.
  • Modifié (18 Sep)
    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.
Success message!