Fibonacci

J' étudie la suite de Fibonacci définie par
$F_0=0$, $F_1=1$ et la récurrence:

$F_{n+2}=F_{n+1}+F_{n}$ pour $n \geq 0$.

J' aimerai montrer le fait suivant, $n|m$ implique $F_n|F_m$.

Avez vous des idées?

Réponses

  • On raisonne modulo $F_n$. On a alors $F_n=0$. Je pose $a=F_{n-1}$. On a alors $F_n=0$, $F_{n+1}=a$, $F_{n+2}=a$, $F_{n+3}=2a$, ...
    Bref on a $F_n=aF_0$, $F_{n+1}=aF_1$, ...
    On a donc $F_{2n}=F_na=0$. On continue...

    On peut surement en donner une preuve mieux léchées. L'idée semble être d'utiliser la linéarité.

    Je dis des bêtises ? Tes questions sont en général plus délicates...
  • Vous pouvez essayer avec les formules de Binet:
    F(n)=(a^n-b^n)/(a-b), avec a=(1+racine(5))/2 et b=-1/a.
    Si m=kn, on a:
    a^(kn)-b^(kn)=(a^n-b^n)(.....). On en déduit que
    F(kn)=F(n)(....). Il reste à vérifier que (...) est un nombre entier.
    On a par exemple:
    F(3n)=F(n)(a^(2n)+(ab)^n+b^2n)=F(n)(L(2n)+(-1)^n), en notant L(n) le nombre de Lucas:
    L(n)=a^n+b^n.
  • J'ai peut-être confondu Pilz et Pilzenbir...
  • Non les deux c'est moi, oui c'était pas trop dur j' ai essayé avec les expressions explicites alors c'était moins facile, merci Probaloser
  • On peut préciser la preuve de Probaloser, en montrant que:
    F(n+p)=F(n-1)F(p)+F(n)F(p+1) (pour p fixé, les deux membres vérifient la même récurrence et sont égales pour n=0 et n=1, donc égales pour tout n). En posant p=kn, le résultat cherché en découle par récurrence sur k.
  • Pour aller plus loin je conseille la lecture de l'article joint.
Connectez-vous ou Inscrivez-vous pour répondre.