Fibonacci et récurrence retorse
dans Arithmétique
Soit $(F_n)$ la suite de Fibonacci : $F_0=0$, $F_1=1$ et $F_{n+2}=F_{n+1}+F_n$.
Pour $n \geq 2$ et $k \geq 0$, on a $$
F_{kn} = \sum_{i=0}^k \binom{k}{i}F_iF_n^iF_{n-1}^{k-i}
$$ Je connais une preuve rapide avec les formules de Binet, j'en cherche une par récurrence.
La relation $$
F_{kn}=L_kF_{k(n-1)}-(-1)^kF_{k(n-2)}
$$ me semblait une piste de départ, où $(L_n)$ est la suite de Lucas qui vérifie la même relation de récurrence que $(F_n)$ mais avec les valeurs initiales $L_0=2$ et $L_1=1$. Elle est liée à $F_n$ par $F_{n-1}+F_{n+1}=L_n$ et aussi $L_{n-1}+L_{n+1}=5F_n$.
Quand je fais une récurrence sur $n$, ce que j'arrive à mettre en facteur dans la somme en utilisant cette relation n'est pas égal au morceau attendu à l'étape suivante ; il a l'air de se passer de drôle de chose dans cette somme ! Quant à la récurrence sur $k$, je n'aboutis à rien.
Si quelqu'un a une idée, je suis preneur.
Merci.
Pour $n \geq 2$ et $k \geq 0$, on a $$
F_{kn} = \sum_{i=0}^k \binom{k}{i}F_iF_n^iF_{n-1}^{k-i}
$$ Je connais une preuve rapide avec les formules de Binet, j'en cherche une par récurrence.
La relation $$
F_{kn}=L_kF_{k(n-1)}-(-1)^kF_{k(n-2)}
$$ me semblait une piste de départ, où $(L_n)$ est la suite de Lucas qui vérifie la même relation de récurrence que $(F_n)$ mais avec les valeurs initiales $L_0=2$ et $L_1=1$. Elle est liée à $F_n$ par $F_{n-1}+F_{n+1}=L_n$ et aussi $L_{n-1}+L_{n+1}=5F_n$.
Quand je fais une récurrence sur $n$, ce que j'arrive à mettre en facteur dans la somme en utilisant cette relation n'est pas égal au morceau attendu à l'étape suivante ; il a l'air de se passer de drôle de chose dans cette somme ! Quant à la récurrence sur $k$, je n'aboutis à rien.
Si quelqu'un a une idée, je suis preneur.
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Et puis surtout de le mettre en gras comme un professeur qui corrige ses élèves, c'est très élégant. 8-)
[ Gilles. Tu peux modifier ton message pour retirer le gras qui fait tache.
Si je corrige sans le marquer, tu ne t'en rends pas compte et tu continueras à faire la faute. :-) AD]
-- Schnoebelen, Philippe
Une idée qui devrait marcher : mais de tête je ne peux le confirmer.
Généralisation de ta formule avec $F_{k n+r}$ à gauche et $F_{i+r}$ à droite où $r$ est un entier.
Récurrence forte sur $k.$
Identité de Pascal.
Récurrence des nombres de Fibonacci.
Voilà !?
Gilles écrivait : http://www.les-mathematiques.net/phorum/read.php?5,1762254,1762318#msg-1762318
[Inutile de recopier l'avant dernier message. Un lien suffit. AD]
e.v.
[Inutile de reproduire le message précédent. AD]
$$F_{kn+r} = \sum_{i=0}^k \binom{k}{i}F_{i+r}F_n^iF_{n-1}^{k-i}$$
C'est immédiat pour $k=0$ et le passage de $k$ à $k+1$ utilise la formule $F_{n+p}=F_pF_{n-1}+F_{p+1}F_n$ qui se démontre par récurrence sur $p$ (ou $n$).
Merci pour ton idée, j'ai commencé à regarder la démonstration, je n'ai pas le temps de terminer maintenant mais cela s'annonce bien mieux que celle de mon cas particulier.
$$
F_{kn+r}=\frac{(\alpha^n)^k\alpha^r -(\beta^n)^k\beta^r}{\alpha-\beta} = \sum_{i=0}^k \binom{k}{i} F_n^iF_{n-1}^{k-i}\frac{\alpha^i \alpha ^r - \beta^i \beta ^r}{\alpha-\beta} = \sum_{i=0}^k \binom{k}{i} F_n^iF_{n-1}^{k-i} F_{r+i}.
$$
Ton $\alpha^n = \alpha F_n + F_{n-1}$, c'est ultra-classique. Et c'est une manière de calculer les $F_n$. De manière formelle, on n'utilise pas $\sqrt 5$ mais le quotient ;
$$
\Z[x] = {\Z[X] \over \langle X^2 - X - 1\rangle} = \Z.1 \oplus \Z.x \qquad x^2 = x+1
$$
Ci-dessus, $x$ est la classe de $X$ modulo $X^2 - X - 1$, et $\Z[x]$ est une $\Z$-algèbre libre de dimension 2 de base $(1,x)$ avec la relation $x^2 = x+1$. Tu peux penser à $x = {1 + \sqrt 5 \over 2}$. Tu peux aussi penser à ce que tu veux. C'est une manière vachement efficace de calculer $F_n$ si on calcule $x^n$ par exponentiation dichotomique.
Hum : on a $\beta = \alpha$, chez toi, c'est voulu ?
histoire de parler de polynômes,
si on a sous la main les polynômes en $F_n$
$F_{5n}=25(F_{n})^5+(-1)^{n}25(F_{n})^3+5F_{n}$
$F_{3n}=5(F_{n})^3+(-1)^{n}3F_{n}$
alors (je ne dis évidemment pas que c'est mieux)
à partir de $F_{14}=377,F_{23}=28657$ on retrouve, avec une tablette, $F_{70},F_{69}$
On note :
$\chi=X^{2}-X-1\in\mathbb{Z}\left[X\right]$.
$A=\frac{\mathbb{Z}\left[X\right]}{\left(\chi\right)}$ et $Q\mapsto\overline{Q}$ la surjection canonique.
$\tau$ l'opérateur de $M=\mathbb{Z}^{\mathbb{N}}$ de translation à droite.
La suite de Fibonacci $F\in\ker\chi\left(\tau\right)$.
Soit $\overline{Q}\in A$. On pose $g\left(\overline{Q}\right)=Q\left(\tau\right)\left(F\right)$ qui est un morphisme (défini sans ambiguïté) de $\mathbb{Z}$ modules de $A$ dans $M$.
On a alors, par division euclidienne de $X^{n}$ par $\chi$, $\overline{X}^{n}=a_{n}\overline{X}+b_{n}$. En appliquant $g$ aux deux membres, puis en évaluant la suite obtenue en 0 puis 1 on obtient, pour $n\geqslant1$, $a_{n}=F_{n}$ et $b_{n}=F_{n-1}$. Soient alors $q\geqslant0$, et $n\geqslant1$, on obtient donc :
\[
\overline{X}^{qn}=\left(F_{n}\overline{X}+F_{n-1}\right)^{q}=\sum_{i=0}^{q}\binom{q}{i}F_{n}^{i}F_{n-1}^{q-i}\overline{X}^{i}
\]
On applique $g$ aux deux membres, puis on évalue en 0 et on obtient
\[
F_{qn}=\sum_{i=0}^{q}\binom{q}{i}F_{n}^{i}F_{n-1}^{q-i}F_{i}
\]
Oui, c'est cela : dichotomique car grosso modo, l'exposant est divisé par 2 à chaque étape. Il s'agit de l'exponentation dichotomique qualifiée d'ordinaire par mézigue. Je t'attache une petite note là-dessus (laisse béton les deux lignes du entre-nous ainsi que le programme maple à la fin).
Il y a une autre exponentiation dichotomique dite à la Hörner. Si tu ne craches pas sur les méthodes de calcul, je peux essayer de retrouver une note dans le cadre de l'enseignement (écrite, il y a bien longtemps, pour des petit(e)s de deuxième année). Cela vaut le coup quand on l'applique dans le cadre de la suite de Fibonacci
PS : à une époque (il y a très très longtemps, quand j'étais en activité), on donnait des ``projets'' en informatique. Avec obligation de production d'un dossier de programmation comprenant de la documentation et des programmes. Il y avait deux phrases célèbres de la part des étudiant(e)s : (1) ``mon programme, il est clair, ce n'est pas la peine que j'en fournisse de la documentation'' et (2) ``Je l'ai testé (mon programme) et il marche''. Un étudiant(e) qui nous disait cela une fois ne le disait pas deux fois. Tu vois comme on était des vieux c.ns, à l'époque ?
Merci pour ce document fort bien rédigé comme d'habitude, il va sans dire que je suis très intéressé par celui sur Hörner.
Je ne m'étais jamais penché jusqu'à ce matin sur l'exponentiation rapide. Je m'étais convaincu de son bon fonctionnement par l'invariant de boucle que d'ailleurs tu as mis en évidence sur ton document (c'est ça être un vieux c.n ? :-D) mais j'ai eu bien du mal à comprendre son côté intuitif.
Tous les algorithmes que j'avais trouvé sur le net incluait le dernier calcul du dernier carré dans la boucle, je m'étais bien rendu compte de son inutilité, ça double presque le temps de calcul !
@troisqua
Merci pour cette démonstration je vais essayer de la décortiquer.
L'introduction de ces objets algébriques est extrêmement fécond. En fait avec ces objets on touche précisément la nature algébrique définie par Fibonacci (et les suites du même type).
Avec ça tu peux par exemple démontrer en 3 lignes, sans la moindre récurrence ni la moindre division euclidienne, que $F_{m\wedge n}=F_m\wedge F_n$. Tu peux aussi regarder très vite les valeurs des $F_p$ modulo $p$ (premier), ou montrer que chaque entier $n$ non nul divise au moins l'un des $2n$ premiers termes de la suite de Fibonacci.
Cela faisait longtemps que je n'avais manipulé de polynômes de morphismes, je suis convaincu de ce que tu as écrit (même s'il n'est pas impossible qu'une subtilité algébrique m'ait échappée).
Tu m'as mis l'eau à la bouche avec les résultats que tu annonces, je suis preneur d'indications (ou de référence ?).
Le seul résultat que je connaisse de divisibilité sur les $F_p$ ($p$ premier) est le suivant : $F_p \equiv 0 \bmod p$ si et seulement si $p=5$, et si $p\geq 7$, on a $F_{p-1} \equiv 0 \bmod p$ ou $F_{p+1} \equiv 0 \bmod p$ selon respectivement que $5$ est ou non un résidu quadratique modulo $p$. Je joins la preuve que je connais, trouvée sur le forum il y a quelques années.
Du coup j'ai essayé de partir d'une expression de $F_{2n}$ comme dans cette preuve, mais en écrivant $\overline{X}^{2n}=(\overline{X}^2)^n$ ou $\overline{X}^{2n}=(\overline{X}^n)^2$ j'obtiens $F_{2n}=\sum_{k=0}^n \binom{n}{k} F_k$ et $F_{2n}=F_n^2+2F_{n-1}F_n$ et ça ne fait pas avancer le schmilblick. D'ailleurs je ne vois d'où des "$5$" pourrait sortir.
Merci d'avance pour ton éclairage.
Pour les valeurs de la suite aux indices premiers $p$ modulo $p$, en gardant les mêmes notations:
Soit $p$ premier. On pose $\chi=X^{2}-X-1\in\mathbb{F}_{p}\left[X\right]$. On note le discriminant $\Delta=5$.
Si $\Delta$ est un carré non nul de $\mathbb{F}_{p}$ alors les racines $r$ et $s$ de $\chi$ sont dans $\mathbb{F}_{p}$. Et alors l'évaluation de $X^{p}=\chi Q+aX+b$ en $r$ et $s$ donne,
\begin{align*}
r & =ar+b\\
s & =as+b
\end{align*} d'où $a=1$ puis $b=0$. Avec les notations précédentes: $g\left(\overline{X}^{p}\right)=g\left(\overline{X}\right)$ qui donne en 0, dans $\mathbb{F}_{p}$ : $F_{p}=F_{1}=1$. En 1: $F_{p+1}=1$ et donc $F_{p-1}=0$.
Si maintenant $\Delta$ n'est pas un carré de $\mathbb{F}_{p}$, alors comme le morphisme d'algèbre $x\mapsto x^{p}$ (de Frobenius) envoie toute racine de $\chi$ sur une racine de $\chi$ et qu'il fixe tous les éléments de $\mathbb{F}_{p}$, il permute nécessairement $r$ et $s$. On obtient donc
\begin{align*}
s & =ar+b\\
r & =as+b
\end{align*} donc $s-r=a\left(r-s\right)$ donc $a=-1$ puis $b=r+s=1$. Ainsi, comme précédemment, on obtient $F_{p}=-F_{1}+F_{0}=-1$ et par évaluation en $1$, $F_{p+1}=-F_{2}+F_{1}=0.$
Reste à conclure en considérant la loi de réciprocité quadratique si on veut préciser davantage suivant les valeurs de $p$.
Je bloque sur un détail technique. Quand $\Delta$ n'est pas un carré dans $\mathbb{F}_p$, tes $r$ et $s$ sont les racines de $X^2-X-1$ dans un (le) corps de décomposition de ce polynôme et tu considères le Frobenius sur ce corps de décomposition en identifiant $\mathbb{F}_p$ à son sous-corps premier ?
Sinon je n'ai pas bien compris ce que tu voulais que j'éclaircisse à propos du cas où $\Delta$ n'est pas un carré modulo $p$. Tu sembles avoir répondu tout seul à ta question
Demain matin comme petit (je pense) exercice, j'étudierais le problème des congruences modulo $p$ pour $L_p$ dont je connais la réponse.
Tant mieux si je me suis auto-répondu, je préférais avoir confirmation.
Sur le fait que parmi les $2n$ premiers nombres de Fibonacci, au moins un est divisible par $n$, je me suis posé la question de savoir si 2 est optimal, c'est bien le cas et on trouve des cas limites même pour les $n$ grands, et je conjecture que ce sont les $n$ de la forme $6\cdot 5^k$ avec $k\in \mathbb{N}$.
C'est programmé avec les pieds, sans soucis d'optimisation. ::o
La formule en question peut être établie pour toute relation de récurrence linéaire d'ordre 2 à condition d'avoir comme premiers termes 0 et 1.
Je ne sais pas si c'est toujours d'actualité (exponentation dichotomique) car je vois que beaucoup de choses intéressantes sont arrivées depuis dans ton fil. Tu risques d'exploser si cela continue. Je me contente de faire un petit post ici.
1. Calcul de $x^n$. Une manière de voir deux méthodes dichotomiques est de les fournir sous forme récursive : $x^n = P_n(x) = Q_n(x)$ avec :
$$
m = \left\lfloor {n \over 2} \right\rfloor \qquad
\left|
\begin {array} {l}
P_0(x) = 1, \qquad P_1(x) = x \\
P_n(x) = \cases {P_m(x^2) &si $n$ est pair\cr P_m(x^2) \times x&si $n$ est impair}
\end {array}
\right.
\qquad\qquad\qquad
\left|
\begin {array} {l}
Q_0(x) = 1, \qquad Q_1(x) = x \\
Q_n(x) = \cases {\big(Q_m(x)\big)^2 &si $n$ est pair\cr \big(Q_m(x)\big)^2 \times x&si $n$ est impair}
\end {array}
\right.
$$
Il faut bien comprendre que ce ne sont pas les mêmes calculs qui sont réalisés. J'attache deux pages manuscrites (que je n'ai jamais eu le courage de taper en TeX). J'espère que le scan n'est pas trop mauvais. Pour éviter les torticolis, j'ai réalisé un quart de tour.
Plus tard, mais je ne veux pas que tu exploses, des choses tapées en TeX sur la méthode dichotomique ``à la Hörner'' (il s'agit de $Q_n(x)$ tandis que $P_n(x)$ est la méthode ordinaire).
2. Les vieux c.ns. Si un(e) étudiant(e) nous sortait une des deux phrases mentionnées, il se prenait une copieuse engueulade de notre part. Et s'il insistait, on lui disait qu'on lui mettait une note entre 0 à 5 à son projet. Tu vois un peu le genre de c.ns que nous étions, nous enseignants à l'époque. En général, pour le deuxième projet, cela se passait beaucoup mieux.
Dit autrement, si tu montrais tes programmes Python sans documentation/explication, tu te prenais une engu.. pour commencer. Tu étais obligé de fournir à côté une documentation sérieuse de la chose (sinon une note divisée par 4, donc entre 0 et 5).
Par conséquent le produit des $F_{k_i}$ est divisible par $n$, donc $F_{PGCD(k_i)}$ est divisible par $n$ puisque $a|b$ implique $F_a | F_b$.
Il me "reste" à trouver une construction s'il y a des répétitions dans les facteurs premiers de $n$ et surtout à montrer que ce PGCD est inférieur à $2n$ (sans être sûr que cette construction soit la meilleur possible).
Malheureusement il faut que j'aille travailler, cette recherche devra attendre. :-(
On peut procéder en commençant par montrer (par récurrence) que si $\overline{P}$ est constant dans $A$ modulo $p$ (premier) alors $\overline{P}^\left(p^k\right)$ est constant dans $A$ modulo $p^{k+1}$ pour tout naturel $k$.
@troisqua Je n'ai pas compris ta propriété. Si $P$ est constant, $P^{p^k}$ aussi ?
Avec ça et le travail que tu as fait, la formule tombe toute seule.
J'imagine que tout ce travail c'est pour fabriquer un nombre de Fibonacci divisible par une puissance d'un nombre premier, mais je n'arrive pas à voir à quelle congruence tes indications doivent me mener ? J'ai essayé des conjectures numériques sans succès. Pourrais-tu me la donner ? Merci.
Par exemple $\overline{X}^{n}=a \overline{X}+ b$ est constant modulo $p$ si et seulement si si $a$ est nul modulo $p$.
Comme on l'a vu précédemment, pour la suite de Fibonacci (et pour d'autres on peut généraliser un peu) on a $\overline{X}^{n}=F_{n}\overline{X}+c_{n}$ donc $F_{n}$ est nul modulo $p$ si et seulement si $\overline{X}^{n}$ est constant modulo $p$.
On utilise alors les deux propositions précédentes et le fait qu'on connaît des $n$ (en fonction de $p$ et du résidu quadratique de $\Delta$ modulo $p$), pour lesquels $\overline{X}^{n}$ est constant modulo $p$. Un petit ppcm permet de finaliser la formule cherchée.
Comme multiple commun des $p_i^{\alpha_i}-p_i^{\alpha_i-1}$, $q_j^{\beta_j}$ et $r_k^{\gamma_k}+r_k^{\gamma_k-1}$ on peut prendre leur produit. En majorant $p_i^{\alpha_i}-p_i^{\alpha_i-1}$ par $p_i^{\alpha_i}$ et $r_k^{\gamma_k}+r_k^{\gamma_k-1}$ par $2r_k^{\gamma_k}$, on obtient que ce multiple commun est inférieur ou égal à $2n$.
Pour $n=2\cdot 3 \cdot 5^k$, comme ni $r_1=2$, ni $r_2=3$ ne sont des carrés modulo 5 et que $5$ est l'unique $q_j$, on obtient $r_1^{\gamma_1}+r_1^{\gamma_1-1}=3$ et $r_2^{\gamma_2}+r_2^{\gamma_2-1}=4$, donc cette fois le commun multiple de mon précédent message est bien un PPCM et il vaut $5^k \cdot 3 \cdot 4 = 2n$. Réciproque à voir.
Ce $r$ n'est pas le plus petit possible, et il est réputé être majoré par $2n$.
Si la valuation $2$-adique de $n$ est supérieure ou égal à 2, tous les $p_i^{\alpha_i}- \left(\frac{p}{5}\right)p_i ^{\alpha_i-1}$ sont pairs, sauf pour $p_i=5$. En posant $r_i=p_i^{\alpha_i}- \left(\frac{p}{5}\right)p_i ^{\alpha_i-1}$ (sauf pour $p_i=5$) ainsi que $\alpha$ la valuation $5$-adique de $n$, on a $r_i \leq 2p_i^{\alpha _i}$ et
$$r = \text{PPCM}\left(r_i,5^{\alpha}\right) = \text{PPCM}\left(2 \text{PPCM}\left(\frac{r_i}{2}\right),5^{\alpha} \right) \leq 2\times 5^\alpha \prod p_i^{\alpha_i} =2n.$$
Si $n$ s'écrit $n=2q$ avec $q$ impair, je cherche encore ! Je pensais appliquer à $q$ le cas précédent : il existe $r$ tel que $q$ divise $F_r$ avec $r \leq 2q$ et comme $2$ divise $F_3$, alors $n$ divise $F_{3r}$ mais $3r \leq 3n$ et non $\leq 2n$... Si quelqu'un a une idée ?
Aux plus assidus d'entre vous (j'espère que Gilles et Claude en font encore partie), j'ai rédigé un petit papier (dont je ne prétends aucunement qu'il soit vierge de toute coquille). Je vous le soumets ci-dessous.
En espérant qu'il éclaircisse certains points dont Gilles était demandeur et qu'il intéresse d'autres qui passeraient par ici
voir dans Quadrature n° 101 (2016) un article où on montre que la période de répétition de $0$ dans la suite de Fibonacci modulo $m$ est inférieure ou égale à $2m$, les cas d'égalité étant précisés.
Il y a aussi la majoration de la période de Fibonacci modulo $m$ par $6m$, avec les cas d'égalité.
Merci troisqua pour ce papier, j'ai trouvé là où ma majoration était trop forte.
J'ai relevé une petite coquille page 3 : le produit est majorée par $\frac{3}{4} \frac{q+1}{2q}$ et non $\frac{3}{2} \frac{q+1}{2q}$. Je sais, c'est un détail. :-D
J'essaierai de trouver le quadrature n°101, il doit traîner dans mon CDI.
Bonne soirée.
J'ai tiré ta petite note très soignée sur mon imprimante. Merci. Je n'ai pas encore lu en détails. Pareil que Gilles au milieu de la page 3 : on obtient bien la majoration $\omega(n) \le 2n$ mais pas compris d'où pouvait sortir ta petite somme ${1\over 2} + {1 \over 6}$. Pas grave.
Mais il y aurait des choses structurelles à dire (même si je n'ai pas lu en détails). Vaste chantier. Comme je suis petit joueur, je considère ici uniquement la suite de Fibonacci habituelle $(F_n)_{n \in \Z}$. Note que je l'indexe par $\Z$ et pas par $\N$ et elle est définie comme tu le penses. Je suppose que tu sais que, pour un $n \ge 1$ donné :
$$
\{r \in \Z \mid F_r \equiv 0 \bmod n \} \quad \hbox {est un sous-groupe (non nul) de $\Z$, un idéal si tu veux}
$$
Et donc un plus petit $r \ge 1$ tel que $F_r \equiv 0 \bmod n$, plus petit au sens de la divisibilité. Le voit-on dans ta note ? Et entre dans la course le groupe multiplicatif $\Z[\phi]^\times$ où $\phi = {1 + \sqrt 5 \over 2}$ ou encore si tu veux la classe de $X$ dans $\Z[X]/\langle X^2 - X - 1\rangle$. Et il y a aussi le sous-anneau $\Z[n\phi] = \Z + n\Z[\phi]$ qui s'invite à table ...etc...
$$\prod_{p\in \mathcal{P}}\frac{p+1}{2p}=\frac{3}{4} \prod_{p\in \mathcal{P\backslash\{2\}}}\frac{p+1}{2p}$$
et comme pour $p \geq 3$ on a
$$
\frac{p+1}{2p} = \frac{1}{2}+\frac{1}{2p} \leq \frac{1}{2} + \frac{1}{6}=\frac{2}{3}
$$
il vient bien
$$
\prod_{p\in \mathcal{P}}\frac{p+1}{2p} \leq \frac{1}{2}.
$$