Aller au contenu
Topos Uranos
Français

Sommes, suites arithmétiques et géométriques, récurrence

Résumé

Cette leçon introduit la notation de sommation et ses propriétés (linéarité, décomposition, décalage de l’indice et inversion de l’ordre), et l’applique au calcul de sommes télescopiques et des sommes des suites arithmétiques et géométriques. Elle étudie ensuite la récurrence forte et le principe du bon ordre, démontre que la récurrence implique l’un et l’autre, précise en quel sens ils lui sont équivalents et les emploie pour prouver que tout entier naturel strictement supérieur à 11 est un produit de nombres premiers.

Objectifs d’apprentissage

  1. Écrire et transformer des sommes avec la notation de sommation, en appliquant ses propriétés de linéarité, de décomposition, de décalage de l’indice et d’inversion de l’ordre.
  2. Calculer des sommes télescopiques et les employer pour déduire, et non seulement vérifier, des formules de sommes.
  3. Déterminer le terme général et la somme des premiers termes d’une suite arithmétique ou géométrique, et les appliquer à la résolution de problèmes.
  4. Démontrer par récurrence forte et par le principe du bon ordre, déduire l’un et l’autre du principe de récurrence et expliquer grâce à quels faits supplémentaires le bon ordre permet de retrouver la récurrence.

La notation de sommation

Dans la leçon sur les axiomes de Peano sont apparues des sommes de nombreux termes qui suivent une règle, comme 1+2+⋯+n1 + 2 + \cdots + n. Les points de suspension confient au lecteur la tâche de deviner cette règle ; la notation de sommation l’énonce. Si am,am+1,…,ana_m, a_{m + 1}, \ldots, a_n sont des nombres, avec m≤nm \leq n, on écrit

∑k=mnak=am+am+1+⋯+an\sum_{k=m}^{n} a_k = a_m + a_{m + 1} + \cdots + a_n

et on lit « la somme des aka_k pour kk allant de mm à nn ». La lettre kk est l’indice de la somme ; mm et nn sont ses bornes inférieure et supérieure, et aka_k est le terme général. La somme a n−m+1n - m + 1 termes. L’indice est une variable muette : la valeur de la somme ne dépend pas de la lettre qui le désigne, de sorte que ∑k=1nk2\sum_{k=1}^{n} k^2 et ∑j=1nj2\sum_{j=1}^{n} j^2 sont le même nombre. L’indice parcourt des entiers naturels ; les termes, en revanche, peuvent être des nombres d’une autre sorte. Dans cette leçon apparaissent, outre les entiers naturels, des entiers relatifs avec leurs opposés et des fractions, que l’unité suivante construit : ils sont ici anticipés, et on n’en utilise que les règles élémentaires de calcul et d’ordre (commutativité, associativité, distributivité, règles des signes, soustraction et division par un nombre non nul). Les propriétés de la somme qui suivent se démontrent avec ces règles, et valent donc pour des termes de n’importe laquelle de ces sortes.

Comme l’addition, la multiplication et la puissance dans la leçon sur les opérations sur les entiers naturels, la somme admet une définition par récurrence qui se passe des points de suspension : la somme d’un seul terme est ce terme, et pour ajouter un terme on l’additionne au résultat précédent.

∑k=mmak=am,∑k=mn+1ak=∑k=mnak+an+1\sum_{k=m}^{m} a_k = a_m, \qquad \sum_{k=m}^{n + 1} a_k = \sum_{k=m}^{n} a_k + a_{n + 1}

Cette définition commence en mm, tandis que le théorème de récurrence, tel qu’il a été énoncé, définit des fonctions à partir de 11. Or il suffit de décaler l’indice : au lieu de la somme jusqu’à nn, on définit la somme des qq premiers termes à partir de ama_m. Avec la valeur initiale ama_m et la règle gq(x)=x+am+qg_q(x) = x + a_{m + q}, le théorème de récurrence donne une unique fonction FF de N\mathbb{N} dans les nombres telle que F(1)=amF(1) = a_m et F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} pour tout entier naturel qq. Pour n≥mn \geq m, on définit alors la somme jusqu’à nn comme la valeur de FF au nombre de ses termes, n−m+1n - m + 1, qui est un entier naturel parce que m<n+1m < n + 1 :

∑k=mnak=F(n−m+1)\sum_{k=m}^{n} a_k = F(n - m + 1)

Avec n=mn = m, on obtient F(1)=amF(1) = a_m, et avec q=n−m+1q = n - m + 1, comme m+q=n+1m + q = n + 1, l’égalité F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} est exactement la seconde règle de la définition. Par conséquent, la définition par récurrence à partir de mm détermine une unique somme pour chaque n≥mn \geq m, et si m=1m = 1, elle coïncide avec celle que le théorème de récurrence donne directement, parce qu’alors F(n)=∑k=1nakF(n) = \sum_{k=1}^{n} a_k.

Avec cette notation, la formule démontrée par récurrence dans la leçon sur les axiomes de Peano, celle de la somme des nn premiers entiers naturels, s’écrit ainsi :

∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n + 1)}{2}

La somme des carrés, ∑k=1nk2\sum_{k=1}^{n} k^2, est l’étape suivante, et cette leçon ne se bornera pas à la vérifier : la section sur les sommes télescopiques la déduit sans la connaître d’avance.

Les récurrences sur la borne supérieure d’une somme commencent à la borne inférieure mm, qui n’est pas nécessairement 11. Or le principe de récurrence des axiomes de Peano commence en 11 ; pour commencer à un autre entier naturel, il faut le lemme suivant.

LemmeRécurrence à partir d’un entier naturel quelconque

Soit n0n_0 un entier naturel. Si une propriété est vérifiée pour n0n_0 et si, en admettant qu’elle est vérifiée pour un entier naturel quelconque k≥n0k \geq n_0, elle est vérifiée aussi pour k+1k + 1, alors cette propriété est vérifiée pour tous les entiers naturels n≥n0n \geq n_0. L’idée est de renuméroter les entiers naturels à partir de n0n_0 pour revenir au principe de récurrence simple. On utilise le lemme de la leçon sur les opérations sur les entiers naturels selon lequel tout entier naturel différent de 11 est un successeur, et la monotonie de l’addition. Sur la figure, n0=4n_0 = 4 et p=3p = 3 : sous chaque entier naturel à partir de n0n_0 figure son nouveau numéro qq.

Démonstration

  1. n0=p+1,Q(q)↔P(p+q)n_0 = p + 1, \quad Q(q) \leftrightarrow P(p + q)

    Si n0=1n_0 = 1, c’est le principe de récurrence. Sinon, n0=p+1n_0 = p + 1 pour un certain entier naturel pp, et nous considérons la propriété QQ qui affirme PP pour p+qp + q.

  2. Q(1)↔P(p+1)↔P(n0)Q(1) \leftrightarrow P(\resaltar{p + 1}) \leftrightarrow P(\resaltar{n_0})

    La propriété QQ est vérifiée pour 11, parce que Q(1)Q(1) est P(n0)P(n_0).

  3. P(p+q)→P((p+q)+1)=P(p+(q+1))P(p + q) \rightarrow P(\resaltar{(p + q) + 1}) = P(\resaltar{p + (q + 1)})

    Si Q(q)Q(q) est vraie, comme 1≤q1 \leq q, la monotonie de l’addition donne p+q≥p+1=n0p + q \geq p + 1 = n_0, et l’hérédité supposée s’applique à k=p+qk = p + q : Q(q+1)Q(q + 1) est vraie.

  4. n≥n0→(∃q∈N)(n=p+q)n \geq n_0 \rightarrow (\exists q \in \mathbb{N})(n = p + q)

    D’après le principe de récurrence, Q(q)Q(q) est vraie pour tout qq. Tout n≥n0n \geq n_0 est de la forme p+qp + q : si n=n0n = n_0, avec q=1q = 1, et si n=n0+ln = n_0 + l, avec q=1+lq = 1 + l.

Propriétés des sommes

De la définition par récurrence se déduisent, par récurrence sur la borne supérieure, les propriétés suivantes, valables pour des termes quelconques aka_k et bkb_k et pour tout nombre cc :

  1. Linéarité : ∑k=mn(ak+bk)=∑k=mnak+∑k=mnbk\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k et ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k. En particulier, additionner nn fois une constante revient à la multiplier par nn : ∑k=1nc=nc\sum_{k=1}^{n} c = nc.
  2. Décomposition : si m≤p<nm \leq p < n, alors ∑k=mnak=∑k=mpak+∑k=p+1nak\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k.
  3. Décalage de l’indice : pour tout entier naturel pp, ∑k=mnak=∑j=m+pn+paj−p\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j - p}.
  4. Inversion de l’ordre : ∑k=1nak=∑j=1nan+1−j\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_{n + 1 - j}.
ThéorèmePropriétés des sommes

Pour des termes quelconques aka_k et bkb_k et pour tout nombre cc, la somme est linéaire, se décompose en deux sommes consécutives, admet le décalage de l’indice et l’inversion de l’ordre, dans les termes de la liste précédente. Chaque propriété se démontre par récurrence sur la borne supérieure, qui commence à la borne inférieure grâce au lemme précédent. On n’utilise que la définition par récurrence et les propriétés de l’addition et de la multiplication ; l’inversion s’appuie en outre sur la décomposition et sur le décalage.

Démonstration

  1. ∑k=mn+1(ak+bk)=∑k=mnak+∑k=mnbk+(an+1+bn+1)=∑k=mn+1ak+∑k=mn+1bk\sum_{k=m}^{n + 1} (a_k + b_k) = \resaltar{\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k} + (a_{n + 1} + b_{n + 1}) = \sum_{k=m}^{n + 1} a_k + \sum_{k=m}^{n + 1} b_k

    Linéarité. Pour n=mn = m, les deux membres valent am+bma_m + b_m. Si elle est vraie pour nn, on applique la définition par récurrence, l’hypothèse de récurrence ainsi que l’associativité et la commutativité de l’addition. De même, avec la distributivité, on prouve que ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k, et que ∑k=1nc=nc\sum_{k=1}^{n} c = nc, parce que nc+c=(n+1)cnc + c = (n + 1)c.

  2. ∑k=mp+1ak=∑k=mpak+ap+1=∑k=mpak+∑k=p+1p+1ak\sum_{k=m}^{p + 1} a_k = \sum_{k=m}^{p} a_k + \resaltar{a_{p + 1}} = \sum_{k=m}^{p} a_k + \resaltar{\sum_{k=p+1}^{p + 1} a_k}

    Décomposition, avec pp fixé, par récurrence sur nn à partir de p+1p + 1. Pour n=p+1n = p + 1, c’est la définition par récurrence, parce que la somme d’un seul terme est ce terme.

  3. ∑k=mn+1ak=∑k=mpak+∑k=p+1nak+an+1=∑k=mpak+∑k=p+1n+1ak\sum_{k=m}^{n + 1} a_k = \resaltar{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k} + a_{n + 1} = \dato{d}{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n + 1} a_k}

    Si la décomposition est vraie pour nn, on ajoute le terme an+1a_{n + 1} aux deux membres et on applique la définition par récurrence à chaque somme.

  4. ∑j=m+pn+1+paj−p=∑j=m+pn+paj−p+an+1=∑k=mnak+an+1=∑k=mn+1ak\sum_{j=m+p}^{n+1+p} a_{j - p} = \resaltar{\sum_{j=m+p}^{n+p} a_{j - p}} + a_{n + 1} = \resaltar{\sum_{k=m}^{n} a_k} + a_{n + 1} = \dato{s}{\sum_{k=m}^{n + 1} a_k}

    Décalage. Pour n=mn = m, les deux membres valent ama_m. Si elle est vraie pour nn, comme la borne supérieure (n+p)+1(n + p) + 1 est (n+1)+p(n + 1) + p, on applique la définition par récurrence et l’hypothèse de récurrence.

  5. ∑j=1n+1an+2−j=an+1+∑j=2n+1an+2−j=an+1+∑i=1nan+1−i\sum_{j=1}^{n + 1} a_{n + 2 - j} = a_{n + 1} + \resaltar{\sum_{j=2}^{n + 1} a_{n + 2 - j}} = a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}}

    Inversion, par récurrence sur nn. Pour n=1n = 1, les deux membres valent a1a_1. Si elle est vraie pour nn, on sépare le premier terme de la somme inversée de n+1n + 1 termes par la décomposition, et on décale l’indice d’une unité, avec j=i+1j = i + 1.

  6. an+1+∑i=1nan+1−i=an+1+∑k=1nak=∑k=1n+1aka_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}} = a_{n + 1} + \resaltar{\sum_{k=1}^{n} a_k} = \sum_{k=1}^{n + 1} a_k

    D’après l’hypothèse de récurrence, la dernière somme vaut ∑k=1nak\sum_{k=1}^{n} a_k ; par la commutativité et la définition par récurrence, on obtient l’inversion pour n+1n + 1.

La linéarité permet de ramener une somme compliquée à des sommes connues. Les deux dernières propriétés sont des changements de variable : le décalage substitue k=j−pk = j - p et parcourt les mêmes termes avec une autre numérotation, et l’inversion substitue k=n+1−jk = n + 1 - j et les parcourt du dernier au premier. Or la somme ne se comporte pas de la même façon avec le produit : la somme des produits n’est pas le produit des sommes. Un exemple avec deux termes et ak=bk=ka_k = b_k = k suffit :

∑k=12k⋅k=1+4=5≠9=(1+2)(1+2)\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5 \neq 9 = (1 + 2)(1 + 2)
PropositionLa somme des premiers nombres impairs

Démontrer que la somme des nn premiers nombres impairs est n2n^2. La linéarité ramène la somme à deux autres déjà connues, sans qu’il faille une nouvelle récurrence.

Démonstration

  1. 1+3+5+⋯+(2n−1)=∑k=1n(2k−1)1 + 3 + 5 + \cdots + (2n - 1) = \dato{s}{\sum_{k=1}^{n} (2k - 1)}

    L’impair qui occupe le rang kk est 2k−12k - 1 : le premier est 11, le deuxième 33 et celui de rang nn est 2n−12n - 1. La somme demandée s’écrit ainsi.

  2. ∑k=1n(2k−1)=2∑k=1nk−∑k=1n1\sum_{k=1}^{n} \resaltar{(2k - 1)} = \resaltar{2 \sum_{k=1}^{n} k - \sum_{k=1}^{n} 1}

    Par linéarité, la somme se sépare en deux : le double de la somme des kk, moins la somme de nn uns.

  3. 2∑k=1nk−∑k=1n1=n(n+1)−n2 \resaltar{\sum_{k=1}^{n} k} - \resaltar{\sum_{k=1}^{n} 1} = \resaltar{n(n + 1)} - \resaltar{n}

    La première somme est celle des nn premiers entiers naturels, n(n+1)2\frac{n(n + 1)}{2}, et le facteur 22 simplifie son dénominateur ; la seconde additionne nn fois le nombre 11.

  4. n(n+1)−n=n2+n−n=n2\resaltar{n(n + 1)} - n = \resaltar{n^2 + n} - n = n^2

    Nous développons le produit ; les termes nn et −n-n s’annulent.

  5. k2−(k−1)2=2k−1k^2 - (k - 1)^2 = 2k - 1

    La figure montre pourquoi : chaque impair est la différence de deux carrés consécutifs, l’équerre qui transforme le carré de côté k−1k - 1 en celui de côté kk.