Le raisonnement par récurrence

Chaque fois qu'on voudra démontrer une infinité de propriétés , où , il y a de grandes chances que le principe de récurrence se montre éminemment utile.
Nous ne le démontrerons pas intégralement, mais montrerons simplement qu'il est extrêmement intuitif et facile à appliquer.

[modifier ( modifier-404-section-1.cours)]Raisonnement par récurrence

[modifier ( modifier-404-section-4.cours)]Quelques exemples et applications du raisonnement par récurrence

1.Etablissement de quelques formules sommatoires.
Montrons que pour la somme des premiers entiers positifs est
(1)
(on aurait pu le faire facilement par une autre méthode, mais établissons-la à titre d'exercice)
1) Partons de n = 2 :
est exacte.
2) Montrons que si (1) est vraie (c'est-à-dire si est vraie), alors la même formule, avec à la place de , est vraie, (c'est-à-dire si est vraie), à savoir :
(à prouver, donc)
On peut ajouter aux deux membres de (1), qui est supposée vraie ; on obtient :


C'est prouvé !
Autre exemple : montrons que (2)
Puisque l'on parle de somme, commençons par la somme de deux termes : vérifions

soit

ce qui est exact.
Montrons que (2), que nous appellerons implique

que nous appellerons .
Supposons donc (2) vraie, et ajoutons
aux deux membres :
On obtient





En effet, s'annule pour , donc se factorise par .
On trouve aisément

et finalement

ce qui achève la démonstration.

2. Un principe très utile
Prouvons l'important résultat, vrai pour tout et tout :
(3)
Nous faisons un raisonnement par récurrence surtout à titre d'exercice ; on aurait pu écrire à la place : )
Vérifions pour  :
 : c'est vrai, car .
Prouvons à présent que (3) implique

En effet, si (3) est vraie, multiplions les deux membres de l'inégalité par le nombre positif  ; on trouve
, soit

(car ). La preuve est faite.
Ce principe nous permet de prouver qu'une suite géométrique de raison , avec , diverge vers l'infini, et qu'une suite géométrique de raison telle que converge vers 0 :
En effet, si , posons .
Le terme général de la suite a pour valeur absolue :

et cette quantité peut être aussi grande qu'on le veut, comme , si l'on a
Il est facile d'imposer une contrainte encore plus forte : , car alors

Cette inégalité est vérifiée dès que l'on a , soit
Dire que peut prendre des valeurs aussi grandes qu'on veut si est suffisamment grand signifie simplement que

(La suite diverge à l'infini).
Si par contre on a , on peut dire que et l'on pourra encore poser
On montre de la même manière que plus haut que prend des valeurs aussi grandes qu'on veut pourvu que soit assez grand, ce qui veut dire que c'est-à-dire .
En résumé, si , une suite géométrique de raison diverge vers l'infini ;
si , elle converge vers 0.

3. Facile à prouver et extrêmement utile : la formule de De Moivre
Elle s'énonce
(4)
(avec (nous étendrons ceci aisément à ))
(Pour les amateurs qui n'ont pas encore été initiés à la trigonométrie de [Bacc-1], nous utiliserons les formules (pas difficiles à prouver, du reste) :

et pour ceux, celles qui attendent (même un jour lointain !) de faire le programme de Terminale sur les nombres complexes, disons qu'il n'y a qu'une toute petite chose à savoir, c'est que l'"unité imaginaire" i est un "nombre" dont le carré vaut -1 :

et rien d'autre)
Vérifions que la formule est vraie pour  :
ce qui est vrai... Bon, nous avons admis que la puissance zéro d'un nombre complexe valait 1...
Pour les sceptiques, recommençons pour (puisque la formule de De Moivre est destinée à se rendre utile pour n=2,3,4...) :
 : il n'y a pas plus vrai !
Supposons (4) vraie, c'est-à-dire supposons vraie.
Multiplions les deux membres de l'égalité par  :



(voir formules données plus haut !)
On reconnaît :

ce qui démontre la formule.

4. Formule du binôme de Newton
Enonçons-la : pour
(5)
avec
. Les sont appelés coefficients binômiaux. On les note aussi
Vérifions pour  :
 : c'est vrai car
Supposons (5) vraie, c'est-à-dire vraie. Montrons qu'alors est vraie aussi, en multipliant les deux membres de (5) par  :



Remarquons deux choses :
Pour tout ,
On a donc
D'autre part,




On peut maintenant réécrire plus simplement

La formule est ainsi démontrée.

Formule du multinôme de Newton
Enoncé : pour avec
(6)
Nous allons raisonner par récurrence sur .
Pour , on retrouve la formule du binôme de Newton, quelle que soit la valeur de , car
si
La formule est donc vraie pour .
Supposons qu'elle soit vraie pour donné, et avec un exposant arbitraire.
Alors

(on a juste développé une somme de deux termes : élevée à la puissance )
D'après l'hypothèse, on peut écrire

On peut écrire ceci plus simplement :

ce qui prouve la formule.