Accueil

Relations entre éléments des suites

Suites récurrentes du second ordre

1 Propriétés fondamentales

1 Propriétés fondamentales

2 Relations entre les suites

3 Relations avec les suites d'ordres supérieurs

4 Applications

Formulaire


1.1 Définitions

  Les suites récurrentes du second ordre,sous leur forme la plus générale, sont soumises à la relation de récurrence :

(1.1.1)

  Elles se distinguent par les valeurs attribuées aux coefficients a et b et aux deux premiers termes u0 et u1.

  Pour a et b donnés, si le terme d’indice 0 est différent de 0 ou le terme d’indice 1 différent de 1, la suite sera représentée par une lettre minuscule.

  On adoptera la majuscule pour la suite fondamentale dont le terme d’indice 0 vaut 0 et celui d’indice 1 vaut 1.

  Si a et b sont égaux à 1 on a affaire à une suite de Fibonacci pour la quelle on adoptera le style italique, minuscule en général ou majuscule pour la suite fondamentale. Dans ce dernier cas il s’agira de la célèbre suite de Fibonacci.

  A une suite { u } correspond une suite { v } représentée avec les mêmes conventions typographiques dont l’énième terme vn, est donné par :

(1.1.2)

  Cette nouvelle suite obéit à la même relation de récurrence, pour le vérifier il suffit de calculer un+1 et un-1 avec (1.1.1), puis de les reporter dans (1.1.2).

(1.1.3)

  Pour exprimer un en fonction de vn+1 et vn-1, ces deux derniers termes sont calculés avec (1.1.2). Leur somme donne :

  Soit, en anticipant sur la suite et en adoptant :

(1.1.4)

  Le terme d'indice n de l'une de ses deux suites peut aussi s'exprimer soit en fonction des deux termes d'indice n-1 soit de ceux d'indices n+1.

  (1.1.1) et (1.1.2) conduisent à :

(1.1.5)

  Parallèlement, (1.1.3) et (1.1.4) donnent :

(1.1.6)

mais aussi

(1.1.7)

et

(1.1.8)

  De ces 4 relations, on déduit les expressions qui lient les deux premiers termes de chacune des deux suites :

si n=1 dans (1.1.5) et (1.1.6)

(1.1.9)


1.2 Calcul du énième terme

  Pour exprimer l'énième terme de la suite récurrente :

on détermine d'abord la solution générale, combinaison linéaire de deux solutions particulières à rechercher parmi les progressions géométriques :

celle qui satisfait

c'est à dire

  La résolution du problème présente une analogie certaine avec la résolution des équations différentielles du second ordre à coefficients constants, et ici aussi il convient de distinguer 3 cas, selon que le discriminant :

est positif, nul ou négatif.

(1.1.10)

si n=0 dans (1.1.7) et (1.1.8)

(1.1.11)

(1.1.12)

 Puisque U0= 0 et U1= 1 par définition, les deux premiers termes de la seconde suite fondamentale V vaudront :

  Par la suite, on recourra fréquemment au raisonnement par récurrence :
  - pour les propositions introduites plus ou moins empiriquement
  - pour celles résultant d’une extrapolation de cas ponctuels
  - pour généraliser une formule applicable dans un cadre restreint

Démonstration par récurrence appliquée aux suites du second ordre

  Pour tenir compte de la règle de récurrence, on supposera la proposition exacte pour deux valeurs successives quelconques de l’indice : n et n+1.
  On s’attachera, par application la règle de récurrence, à montrer qu’ elle est aussi vraie pour n+2.
  On la vérifiera ensuite pour les deux termes successifs les plus faciles à calculer ( n=0 et n=1 le plus souvent ).
  La proposition étant vérifiée pour ces deux termes elle le sera aussi pour le suivant et donc, par récurrence, pour tous les suivants.
  On aura ainsi démontré que la relation est vraie pour tout n et que la règle de récurrence est toujours appliquée.
  L’opération se compliquera à peine si deux indices m et n sont en jeu. La démonstration sera conduite comme précédemment sur le premier indice n en supposant m quelconque et constant, ceci démontrera la véracité de la proposition pour tout n et tout m, et le respect de la règle de récurrence seulement pour n. Il restera donc à vérifier sa véracité pour m.


1.2.1 Discriminant positif

  Si le discriminant est positif, les deux racines sont réelles et distinctes :

elles conduisent à la solution générale :

(1.2.1)

  A noter les 3 relations évidentes mais très utiles :

 

  Les constantes k1 et k2 seront déterminées à partir des deux valeurs initiales u0 et u1

système dont on tire :

d'où :

(1.2.2)

soit

(1.2.3)

(1.2.4) (1.2.5

et toujours

avec

  Concernant la suite { v }, on a avec (1.1.9) et (1.1.11) :

 

et finalement :

(1.2.6)

  Parmi les suites récurrentes du second ordre deux familles particulières, notées en majuscules, sont formées des suites dont les 2 premiers termes valent :

  Pour ces suites, C1 et C2 valant 1, les formules (1.2.3) et (1.2.6) se réduisent à :

(1.2.7) (1.2.8)

Exemple

  Si a=1 , b=1 , U0=0 et U1=1 on retrouve la formule de Binet applicable aux nombres de la suite de Fibonacci :

0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , ...

et

 pour la suite des nombres de Lucas qui lui est associée :

 1 , 3 , 4 , 7 , 11 , 18 , 29 , ...

.

  Un et Vn joueront un rôle essentiel, entre autre dans le calcul du énième terme d'une suite du second ordre de la forme la plus générale.

  Partant de (1.2.2) :

soit, puisque AB = -b

et, avec (1.2.7), un est donné par:

(1.2.9)

  Bien que cette relation ait été établie dans le cadre d’un discriminant positif, elle est cependant vérifiée quels que soient a et b, comme on peut s’en assurer en la démontrant par récurrence :

Démonstration par récurrence

  Cette relation est manifestement vraie pour n=1 et n=2 puisque U0=0, U1=1 et U2=a
   Si elle est vérifiée pour n et n+1, on peut démontrer qu’elle est aussi si vérifiée pour n+2

  (1.2.9) conduit à :

dont la somme membre à membre restitue :


  Ainsi, si cette relation est vérifiée pour deux valeurs successives de n elle le sera aussi pour la suivante. Etant vérifiée pour n =1 et n=2 elle sera donc pour n=3 et par récurrence pour toutes les valeurs suivantes.

  En prenant v0 et v1 comme référence à la place de u0 et u1 il vient :

(1.2.10)

(1.2.9) et (1.2.10) sont généralisables en :

(1.2.11)
(1.2.12)

où um et um+1 d’une part, vm et vm+1 d’autre part, remplacent les termes de référence u0 et u1 et v0 et v1. Comme pour les originaux, des démonstrations par récurrence confirmeraient qu’elles sont applicables à toutes les suites récurrentes indépendamment du signe du discriminant.


1.2.2 Discriminant nul

  Un discriminant nul implique une valeur paire pour a puisque :

  L’application de la relation de récurrence aux termes successifs de la suite {U} donne, puisque U0 = 0 et U1 = 1 par définition :

(1.2.13)

généralisation qu'il convient de démontrer.

Démonstration par récurrence

  La proposition est vraie pour n=0 et n=1.Si elle est vérifiée pour n on a, puisque b=-(a/2)2 :

  Si elle est aussi vérifiée pour n+1 on aura :

  La somme membre à membre donne compte tenu de (1.1.1)

  Ainsi, quel que soit n, si la proposition est vraie pour n et n+1 elle l’est aussi pour n+2, étant vraie pour n=0 et n=1 elle sera toujours vraie si b = -(a/2)2 , c’est à dire si le discriminant est négatif.

  De (1.2.13) on déduit, avec (1.1.2)

(1.2.14)

  Et, puisque (1.2.11) et (1.1.2) sont toujours applicables, nous aurons sous la seule réserve que n soit positif :

(1.2.15)
(1.2.16)

  A noter encore l’analogie avec la solution générale des équations différentielles du second ordre dont le discriminant est nul.


1.2.3 Discriminant négatif

  Un discriminant négatif impose b<0 et -b>a2/4 et conduit à deux racines complexes

avec

  Pour utiliser les fonctions circulaires, on prendra :

ainsi la solution générale peut se mettre sous la forme :

ou plus classiquement :

  En posant

(1.2.21) (1.2.22)

pour les suites fondamentales.

   En utilisant une nouvelle fois (1.2.11)

<:p>

(1.2.23)

(1.2.24)

à utiliser quand le discriminant est négatif.

Exemple

  Avec  a = 1  b = -1  le discriminant vaut -3  et les suites  u  et  v  seront périodiques
  Si   u(0) = 0  et   u(1) = 1 :
                   u = { 0 , 1 , 1 , 0 , -1 , -1 , 0 , 1 , 1 ,  . . . }
                   v = { 2 , 1 , -1 , -2 , -1 , 1 , 2 , 1 , -1 ,  . . . }


1.3 Indices négatifs

  Parmi ces suites, seules celles pour les quelles b=1 auront leurs termes d'indices négatifs entiers, ils sont alors accessibles par un calcul à rebours selon :

  Pour les suites relevant des formules (1.2.7) et (1.2.8)

et puisque AB = -b

(1.3.1) (1.3.2)

  Quand un terme d’indice négatif est fractionnaire le produit (-b)nU-n est nécessairement entier.

  La suite {u} sera étendue aux termes d’indices négatifs en changeant le signe de l’indice dans (1.2.9) et en multipliant les deux membres par (-b)n

  Soit, après substitution avec (1.3.1)

(1.3.3)

la même démarche avec {v} donne :

(1.3.4)

  Où, ici aussi, les produits (-b)nu-n et (-b)nv-n seront toujours entiers, même quand l’élément de la suite ne l’est pas.


1.4 Constante caractéristique d'une suite récurrente du second ordre

   Cette constante , Ku , s’imposera dès le début de la seconde partie, elle est égale au produit de C1 par C2, définis par (1.2.4) et (1.2.5)

expression généralisable sous la forme :

(1.4.1)

où a , b , un et un+1 sont liés par la relation de récurrence (1.1.1) des suites du second ordre.

Démonstration par récurrence

  La proposition est supposée vraie pour une valeur particulière n , on multiplie les deux membres de (1.4.1) par b et on applique la relation de récurrence en développant bun selon bun = un+2 - a un+1

soit

  Ainsi, si la proposition est vérifiée pour un indice elle le sera aussi pour l'indice suivant, par conséquent en choisissant la constante telle que la proposition soit vérifiée pour n=0 , c’est à dire :

elle le sera aussi pour n=1et par récurrence pour tout n.

  En factorisant

(1.4.2)

  Pour n=0 (1.4.1) et (1.4.2) on retrouve effectivement :

(1.4.3)(1.4.4)

Ku est donc une constante caractérisant chaque suite.

  On a aussi :

(1.4.5)

(qui conduit à (1.4.4) si n=1 )

Démonstration par récurrence

  La proposition est supposée vraie pour les deux valeurs n et n+1

dont la somme membre a membre donne effectivement Un+2

  Elle aussi vérifiée pour n=0

et aussi pour n=1 puisque U0 vaut toujours 0

U1 valant toujours 1, on retrouve (1.4.4)

  Selon le raisonnement habituel elle est donc toujours vérifiée.

  Ou bien encore

(1.4.6)

qui se démontre de façon semblable.

Démonstration par récurrence

  La proposition est supposée vraie pour n et n+1

dont la somme membre a membre donne effectivement Un+2

  Elle aussi vérifiée pour n=1

car U0 = 0 et aussi pour n=2

puisqu’en exprimant u3 en fonction de u2 et u1 on retrouve (1.4.1) pour n=1

  Par conséquent, selon le raisonnement habituel, la proposition est toujours vérifiée.

  Parallèlement, la suite {v} , liée à la suite {u} par la relation (1.1.2) conduit à :

(1.4.7)

avec

(1.4.8)

et

(1.4.9)

  Avec l’équivalent pour v de (1.4.5)

(1.4.10)

qui se démontre comme pour u.

  Pour toute suite fondamentale, où par définition u0=0 et u1=1 on a KU = 1


Extraire la page pour l'enregistrer ou l'imprimer