Suites numériques

Une suite de nombres commence par 1, 9, 25, 49 ... Quel est le nombre suivant dans cette liste ?

Pour répondre à cette question, il a fallu trouver l'algorithme qui engendrait les 4 premiers nombres, et appliquer cet algorithme pour trouver le nombre suivant; d'où les définitions suivantes:

Définitions

Lorsqu'un algorithme comporte une boucle, les nombres calculés à chaque passage dans la boucle consituent une suite numérique (ou simplement "suite"). Une suite u est donc la donnée d'une infinité de nombres qui se suivent.
Le nombre de passages dans la boucle est appelé indice; si on note n l'indice, le nombre u_n calculé après n passages dans la boucle est appelé terme de rang n (ou d'indice n) de la suite. On l'appelle également terme général.
Une suite est dite explicite si l'algorithme de calcul de u_n n'utilise que l'indice n comme variable. Par exemple, u = n/(n+1) vu ci-dessous, où la seule variable apparaissant à droite du "=" est n. La définition explicite de la suite u se notant u_n=n/(n+1)
Si, au contraire, chaque terme est calculé uniquement à partir du terme précédent, la suite est dite récurrente. Par exemple, u=4*u*(1-u) qui, pour toute valeur de u₀, donne une suite pseudo-aléatoire:
u=0.1 for n in [1..4] u = 4*u*(1-u) alert u
Si, à chaque passage dans la boucle, le terme calculé est au moins aussi grand que le précédent, la suite est croissante; on note u_n+1≥u_n
Si, au contraire, le terme est systématiquement plus petit que le précédent, la suite est dite décroissante; on note u_n+1≤u_n

Implémentation

Une suite étant constituée d'une infinité de nombres, ne peut être stockée dans un ordinateur dont la mémoire est finie. On est donc obligé de se restreindre à quelques valeurs de l'indice. Par exemple, la suite u définie par u_n=n/(n+1):

for indice in [0..4] termeGénéral = indice/(indice+1) alert "Maintenant l'indice vaut #{indice} et le terme général vaut #{termeGénéral}"

Même si on raccourcit avec des lettres u et n:

for n in [0..4] u = n/(n+1) alert "Le terme d'indice vaut #{n} vaut #{u}"

On gagne donc à considérer un objet suite qui est un tableau, et à afficher ce tableau avec alert u:

u = (n/(n+1) for n in [0..4]) alert ("u(#{n})=#{u[n]}" for n in [0..4])

Cette technique ne fonctionne pas avec une suite récurrente. Mais on peut créer un tableau et, après chaque calcul du terme général u, le rajouter au tableau en faisant tableau.push u. Ou bien (ici pour la suite des puissances de 2, qui est récurrente; voir plus bas):

tableau=[] u=1 for n in [0..10] tableau[n]=u u *=2 alert tableau

Remarque : Dans l'exemple donné au début de ce chapitre, il y a un algorithme explicite qui permet de répondre à la question (en reconnaissant des nombres particuliers), mais aussi un algorithme récurrent (en comparant les nombres). Lequel aviez-vous utilisé ?

Suites arithmétiques

Définition

On dit qu'une suite récurrente est arithmétique de raison r si u_n+1=u_n+r; par exemple, la suite des nombres impairs est arithmétique de raison 2:

u=1 tableau=[u] for n in [1..10] u += 2 tableau.push u alert tableau

Calcul direct

Si u est arithmétique de raison r, alors ∀ n ∈ N, u_n=u₀+r×n.

Les suites arithmétiques sont celles qu'on obtient automatiquement en copiant des cellules d'un tableur, ou en fixant les antécédents sur "auto" dans le tableau de fonctions de la calculatrice.

u = (n for n in [1..21] by 2) alert u

Variations

Une suite arithmétique est croissante ou décroissante selon que sa raison est positive ou négative.

Suites géométriques

Définition

On dit qu'une suite récurrente est géométrique de raison r si u_n+1=u_n×r; par exemple, la suite des puissances de 2 vue ci-dessus.

Remarque : Le mot "raison" vient du latin ratio qui veut dire "quotient": Le quotient de chaque terme par le précédent est toujours le même "ratio". C'est par abus de langage que le mot "raison" a été gardé pour les suites arithmétiques. Un autre abus de langage a été vu au début du chapitre: Le mot "terme", en algèbre, désigne un nombre ou une expression qui a vocation à être additionné ou soustrait. Ce n'est pas forcément le cas pour les termes d'une suite.

Calcul direct

Si u est géométrique de raison r alors ∀ n ∈ N, u_n=u₀× rⁿ.

Variations

Une suite géométrique est croissante ou décroissante selon que sa raison est supérieure ou inférieure à 1.

Limite

Limite infinie

La suite de Fibonacci décrit, de façon très simplifiée, l'évolution d'une population de lapins donnant tous les 6 mois des lapereaux, qui eux-mêmes donnent au bout d'un an des lapereaux. On la modélise par une suite F telle que:

F₀=1 (on suppose qu'au début on n'a qu'une lapine , trop jeune pour donner des lapereaux)
F₁=1 (âgée de 6 mois, la lapine n'a pas encore pu donner de petit, mais ensuite elle en donne un tous les 6 mois)
F_n+2=F_n+1+F_n (aux F_n+1 lapins présents il y a 6 mois, se sont ajoutés F_n naissances, soit autant que de lapines qui étaient déjà présentes il y a un an)

L'algorithme suivant s'arrête toujours, quelle que soit la valeur du seuil choisie:

seuil = 1000 [u,v,n]=[1,1,1] until v > seuil n++ [u,v]=[v,u+v] alert "Au bout de #{n} générations, il y a #{v} lapines, ce qui dépasse pour la première fois le seuil de #{seuil}"

Définition:

Lorsque, pour toute valeur du seuil, l'algorithme calculant une suite croissante jusqu'à ce que le seuil soit dépassé, se termine au bout d'un temps fini, on dit que la suite tend vers l'infini, et on écrit lim u_n=+∞

Limite finie

Définition

Si, pour toute valeur du seuil, l'algorithme de calcul d'une suite monotone jusqu'à ce que u_n-ℓ soit inférieur (en valeur absolue) au seuil, s'arrête au bout d'un temps fini, on dit que la suite tend vers ℓ, ou admet ℓ comme limite, et on note lim u_n=ℓ

Exemple

Le calcul de √(3) par l'algorithme de Heron consiste à appliquer l'algorithme de la définition à une suite u_n qui tend vers √(3). On choisit la suite récurrente u_n+1=(u_n+3/u_n)/2

seuil=1e-6 u=1 u=(u+3/u)/2 until Math.abs(u-Math.sqrt(3)) < seuil alert u

Cas particuliers

Suites arithmétiques

Une suite arithmétique tend vers +∞ si sa raison est positive et vers -∞ si sa raison est négative.

Pour le vérifier, il suffit de modifier le premier terme et la raison ci-dessous :

premierTerme = -5 raison = 3 u = (n) -> premierTerme + raison * n alert u(Infinity)

Suites géométriques

On se restreint aux suites géométriques de raison et de premier terme positifs; alors

Si la raison est supérieure à 1, la suite tend vers +∞
Si la raison est inférieure à 1, la suite tend vers 0.

Pour le vérifier, on peut modifier le premier terme et la raison ci-dessous :

premierTerme = 8 raison = 1.6 u = (n) -> premierTerme * Math.pow raison, n alert u(Infinity)

Somme des termes

Voici un algorithme pour additionner les premiers termes d'une suite:

premierTerme = 800 raison = 0.8 N = 10 u = (n) -> premierTerme * Math.pow raison, n somme = 0 somme += u(n) for n in [0...N] alert "la somme des #{N} premiers termes de la suite est #{somme}"

Cas particuliers

Pour les suites arithmétiques, comme pour les suites géométriques, il y a des formules qui évitent d'avoir recours à des algorithmes.

Attention: Si la suite est numérotée à partir de u₀, les N premiers termes vont de u₀ jusqu'à u_N-1

Suites arithmétiques

La somme des N premiers termes d'une suite arithmétique est N×(u₀+u_N-1)/2 (algorithme: On calcule la moyenne entre le premier terme et le "dernier" terme, et on la multiplie par le nombre de termes).

premierTerme = -5 raison = 3 N = 10 u = (n) -> premierTerme + raison * n somme = 0 somme += u(n) for n in [0...N] alert "#{somme} = #{N*(u(0)+u(N-1))/2}"

Suites géométriques

La somme des N premiers termes d'une suite géométrique de raison r est u₀(1-r^N)/(1-r)

premierTerme = 800 raison = 0.8 N = 10 u = (n) -> premierTerme * Math.pow raison, n somme = 0 somme += u(n) for n in [0...N] alert "#{somme} = #{u(0)*(1 - Math.pow raison, N)/(1 - raison)}"

Le délire d'Euler

1+2+4+8+16+32+64+128+256+512+1024+...=-1

(la somme des termes d'une suite géométrique de raison 2 est, d'après la formule précédente, 1+2+4+8+16+32+64+128+256+512+1024+...+2^∞=(1-2^∞)/(1-2)=2^∞-1. En supprimant 2^∞ à chaque membre, on obtient l'égalité...)