Problèmes de Mathématiques
Nombres de Fibonacci
Énoncé
Nombres de Fibonacci
On définit la suite u par : u0 = 0, u1 = 1, et ∀ n ≥ 0, un+2 = un+1 + un .
Les un sont appelés nombres de Fibonacci.
Première partie
1. Vérifier que ∀ n ∈ IN∗ , un > 0.
2. Montrer que la suite u est croissante, et même strictement croissante à partir de n = 2.
3. Prouver que : ∀ n ≥ 6, un > n. On en déduit évidemment lim un = +∞.
+∞
n
X
4. Etablir que : ∀ n ∈ IN, uk = un+2 − 1.
k=0
Xn
5. Montrer que : ∀ n ∈ IN, u2k = un un+1 .
k=0
6. Prouver que : ∀ n ≥ 2, un un−2 − u2n−1 = (−1)n−1 (relation de Simson)
7. Montrer que : ∀ n ∈ IN, pgcd(un , un+1 ) = 1 (on demande deux démonstrations)
√
8. Montrer que : ∀ n ≥ 2, un 2 < un+1 ≤ 2un .
9. Prouver que les longueurs des cotés d’un vrai triangle rectangle ne peuvent être des
nombres de Fibonacci.
10. On veut montrer que tout entier naturel peut s’écrire comme une somme de nombres de
Fibonacci d’indices distincts (théorème de Hoggatt).
(a) Montrer, par récurrence sur n, que la propriété est vraie pour les entiers strictement
inférieurs à un .
(b) Conclure à l’existence de cette décomposition pour tout entier, puis à son unicité.
(c) Décomposer par exemple l’entier 1000000.
X
11. Prouver que : ∀ n ∈ IN∗ , un = C kn−1−k .
0≤k≤(n−1)/2
Comment les un se déduisent-ils du triangle de Pascal ?
12. On pose : v0 = a, v1 = b, et ∀ n ≥ 0, vn+2 = vn+1 + vn .
Montrer que : ∀ n ≥ 0, vn = aun−1 + bun .
Page 1 Jean-Michel Ferrard www.klubprepa.net
EduKlub
c S.A.
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
Problèmes de Mathématiques
Nombres de Fibonacci
Énoncé
Deuxième partie
1. Vérifier que : ∀ p ≥ 2, ∀ q ≥ 0, up uq+1 + up−1 uq = up−1 uq+2 + up−2 uq+1 .
2. En déduire : ∀ p ∈ IN∗ , ∀ q ∈ IN, up+q = up uq+1 + up−1 uq .
3. Montrer que : ∀ p ∈ IN∗ , ∀ q ∈ IN, p > q ⇒ up = up−q uq+1 + up−q−1 uq .
4. Montrer successivement :
(a) ∀ n ≥ 1, u2n = u2n+1 − u2n
(b) ∀ n ≥ 0, u2n+1 = u2n+1 + u2n .
(c) ∀ n ≥ 1, u3n = u3n+1 + u3n − u3n−1 .
(d) ∀ n ≥ 0, u3n+1 = u3n+1 + 3un+1 u2n − u3n .
(e) ∀ n ≥ 0, u3n+2 = 2u3n+1 + 3un+1 u2n − u3n−1 .
5. Montrer que ∀ m, n ∈ IN∗ , (n|m) ⇒ (un |um ).
m
Indication : procéder par récurrence sur la valeur du quotient.
n
6. Etablir que ∀ α, m, n ∈ IN∗ , avec m < n, (α|un et α|um ) ⇒ (α|un−m ).
7. En déduire que : ∀ m, n ∈ IN∗ , pgcd(un , um ) = upgcd(n,m) .
Indication : on s’inspirera de l’algorithme d’Euclide.
Troisième partie
Soit α l’une des racines de X 2 − X − 1.
1. Montrer que ∀ n ≥ 1, αn = un α + un−1 .
√ √
1+ 5 1− 5
2. Posons α = et β = .
2 2
1
Etablir que : ∀ n ∈ IN, un = √ (αn − β n ) (formule de Binet).
5
1
3. En déduire que un est l’entier le plus proche de √ αn .
5
n
4. Montrer que : ∀ n ∈ IN, un+1 = αun + β .
5. En déduire que : ∀ n ≥ 2, un+1 = E(αun − β), puis un+1 + 1 = E(α(un + 1)).
√
2 1 3 + 5 n
6. Montrer que un est l’entier le plus proche de vn = .
5 2
Indication : on distinguera les cas n pair et n impair.
n
X uk
7. Montrer que lim k
= 2.
+∞
k=0
2
Page 2 Jean-Michel Ferrard www.klubprepa.net
EduKlub
c S.A.
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
