Polynômes et séries formelles

I Séries formelles

II Polynômes

I Séries formelles

Polynômes et séries formelles → I Séries formelles

I-1 L'anneau des séries formelles

I-2 Inversion, composition, dérivation

I-3 Quelques exemples

I-4 Récurrences linéaires à coefficients constants.

I-5 Les nombres de Catalan

I-1 L'anneau des séries formelles

Polynômes et séries formelles → I Séries formelles → I-1 L'anneau des séries formelles

Un polynôme est simplement une façon commode de noter la suite finie de ses coefficients. Si est un autre polynôme, on définit leur somme et leur produit par

mais ces formules ne sont valables qu'à condition d'accepter la convention a_n=0 pour n>p. En fait, les coefficients d'un polynôme ne sont pas les éléments d'une suite finie, mais ceux d'une suite infinie à support fini c'est-à-dire que l'on impose que les a_n sont nuls, sauf pour un nombre fini de valeurs de n. Si l'on s'affranchit de cette restriction, on arrive à un objet en un sens encore plus simple qu'un polynôme.
Dans la suite de ce chapitre, nous notons un anneau commutatif quelconque, mais nous sommes surtout intéressés par les cas , , ou .
Ë toute suite à valeurs dans un anneau commutatif , on associe donc une série entière formelle, notée

et on définit des opérations sur ces objets. Si est une autre série entière formelle, leur somme et leur produit sont définis par

Pour tout élément a de la suite de coefficients a₀=a et a_n=0 pour n>0 est associée à une série entière formelle que l'on note encore simplement a. On dit que a est une constante. On note l'ensemble des séries entières formelles à coefficients dans .

Théorème

Muni des lois ci-dessus, l'ensemble des séries entières formelles à coefficients dans l'anneau commutatif forme lui-même un anneau commutatif. Les éléments neutres de l'addition et de la multiplication sont les séries constantes 0 et 1, et l'opposé de A est donné par .

Démonstration

Il suffit de vérifier un à un les axiomes des anneaux commutatifs énoncés plus haut. Toutes ces vérifications sont immédiates. Nous traiterons seulement l'associativité de la multiplication et la distributivité. Soit donc une troisième série. On a

Un anneau est intègre si l'équation x y=0 dans implique x=0 ou y=0.

Théorème

Si est intègre, l'est aussi.

Démonstration

Supposons et . La suite n'est pas identiquement nulle. Il existe donc un entier i₀ tel que et . De même, il existe tel que et . Posons n₀=i₀+j₀. On a

puisque est intègre. On en déduit que le coefficent de dans A B est non nul et .

I-2 Inversion, composition, dérivation

Polynômes et séries formelles → I Séries formelles → I-2 Inversion, composition, dérivation

Les séries dont le terme constant est 1 sont inversibles:

Proposition

Si est une série entière formelle dont le coefficient constant est 1, il existe une unique série

telle que A B=1. Cette série sera notée .

Démonstration

La condition s'écrit a₀ b₀=1 et pour n>0. La suite définie par récurrence par

} {array} .)

vérifie donc les hypothèses, et c'est la seule.

Contrairement à ce qui se passe pour les polynômes, il n'est pas possible d'évaluer une série formelle en en un point . Par contre, il est possible de composer les séries A et B, ce qui revient à évaluer A en B, à condition que le coefficient constant de B soit nul.

Proposition

Si est une série entière formelle quelconque, et est une série entière formelle dont le coefficient constant est nul, il existe une série et une seule, notée A(B) ou , telle que pour tout n c_n soit le coefficient de Xⁿ dans l'écriture de la série pour tout . On écrit aussi .

On peut définir une dérivation. Si on appelle dérivée de A et on note A' la série

On a les relations habituelles

Démonstration

Démontrons la deuxième égalité. On a

I-3 Quelques exemples

Polynômes et séries formelles → I Séries formelles → I-3 Quelques exemples

La série 1-X est inversible. Il est facile de voir que son inverse est

plus généralement, si , on peut écrire

On peut définir une exponentielle formelle dans

et un logarithme formel

et on a les relations

En effet, on voit facilement que E'=E et . On a donc , ce qui donne L(E-1)=X puisque le coefficient constant est 0. De même, (E(L))'=L'E(L), donc (1+X)(E(L))'=E(L). Les coefficients de E(L) vérifient donc la récurrence , ou encore qui, compte tenu de a₀=1, donne a₁=1 et a_n=0 pour n>1, donc E(L)=1+X.
Pour tout et tout , introduisons la factorielle descendante définie par récurrence par et . Si et on peut définir

En effet, on a . Les coefficients de E(L) vérifient donc la récurrence , ou encore qui, compte tenu de a₀=1, donne bien .
Si , la série est un polynôme, et on retrouve bien la formule du binôme. On a alors la

Proposition

Démonstration

En utilisant la formule du binôme, on prouve

et on obtient la relation cherchée en substituant L à X.

Explicitons en particulier le cas de la racine carrée

En effet, le coefficient peut s'écrire

en ``complétant la factorielle'' au numérateur par les facteurs impairs manquants , d'où le résultat.

I-4 Récurrences linéaires à coefficients constants.

Polynômes et séries formelles → I Séries formelles → I-4 Récurrences linéaires à coefficients constants.

On peut utiliser les séries génératrices pour retrouver les résultats classiques sur les suites récurrentes linéaires à coefficients constants
Considérons par exemple la suite d'entiers définie par u₀=4, u₁=13 et pour . On forme la série

Il s'agit d'une équation de degré 1 en U, que l'on résout:

en décomposant la fraction rationnelle en éléments simples, on obtient

et la formule finale .
Dans ce cas, le polynôme caractéristique 1-5X+6X² avait deux racines distinctes, et . Voyons ce qui se passe s'il a une racine double. Définissons la suite v par v₀=1, v₁=6 et . Un calcul similaire donne

Cette dernière formule peut s'obtenir soit à partir de la formule générale pour avec , soit en remarquant que est la dérivée de .

I-5 Les nombres de Catalan

Polynômes et séries formelles → I Séries formelles → I-5 Les nombres de Catalan

Nous concluons cette section par un théorème célèbre dû à Euler (1707-1783). Nous allons calculer le nombre C_n de chemins qui mènent du coin en bas à gauche d'un carré de côté n au coin en haut à droite en suivant les côtés des carrés de côté 1, en allant toujours vers le haut ou vers la droite et sans jamais monter au dessus de la diagonale principale du carré. La figure ci-dessous illustre les chemins acceptables pour n=3 et prouve que C₃=5. On voit facilement que C₀=C₁=1 et C₂=2, mais comment obtenir une formule générale ?

On voit que tout chemin acceptable commence par aller de A=(0,0) à B=(1,0). Il refera contact avec la diagonale pour la première fois au point D=(k,k). L'entier k est compris entre 1 et n. Combien y a t'il de chemins acceptables pour une valeur donnée de k ? Juste avant d'atteindre (k,k), le chemin venait forcément de C=(k,k-1) et entre les points (1,0) et (k,k-1), il parcourt un chemin acceptable dans le carré de sommets (1,0) et (k,k-1) qui est de côté k-1. La figure représente un cas avec n=7 et k=4.

Il y a donc possibilités pour cette première étape. Entre D=(k,k) et E=(n,n), il parcourt un chemin acceptable dans le carré de sommets (k,k) et (n,n) qui est de côté n-k. Il y a donc possibilités pour cette deuxième étape. Le nombre de chemins possibles à k fixé est donc et on a établi la formule

qui permet de calculer les C_n par récurrence. On a donc C₄=1.5+1.2+2.1+5.1=14, C₅=1.14+1.5+2.2+5.1+14.1=42, etc. Formons la série génératrice . On a donc

en posant m=n-1. On reconnait sur la droite le développement de F². On a donc prouvé

F=1+X F²

ce qui est une équation du second degré en F. La résolution habituelle de l'équation X F²-F+1=0, de discriminant donnerait

Le choix du signe ne donne pas une série entière formelle. En utilisant la formule ci dessus pour , on trouve

On a donc

et la formule

On pourrait objecter que la formule pour la résolution des équations du second degré n'a pas été démontrée dans le cadre des séries entières formelles. Pour compléter le raisonnement, on peut partir de la solution proposée: la série

vérifie bien G=1+X G². En soustrayant cette équation à F=1+X F², on trouve (F-G)(1-X(F+G))=0. Comme le facteur 1-X(F+G) n'est pas nul et est intègre, on en déduit bien F=G.
Les nombres de Catalan ne comptent pas seulement des trajets dans un carré. On peut montrer que C_n est le nombre de façons de diviser en triangles un polygone convexe à n+2 côtés, le nombre de façons correctes d'imbriquer n parenthèses ouvrantes et n parenthèses fermantes, le nombre d'arbres binaires pleins à n noeuds intérieurs, etc.

II Polynômes

Polynômes et séries formelles → II Polynômes

II-1 Relations entre racines et coefficients

II-2 Polynômes symétriques

II-3 Les formules de Newton

II-4 Un exemple

II-1 Relations entre racines et coefficients

Polynômes et séries formelles → II Polynômes → II-1 Relations entre racines et coefficients

Soit un n-uplet d'éléments d'un anneau commutatif A. On définit le polynôme unitaire

On peut encore utiliser la formule du produit en posant et b_i=X. On trouve

ce qui suggère de regrouper les I de même cardinal k:

où

est le k-ième polynôme symétrique élémentaire des . Par exemple, pour n=4, en notant a, b, c et c plutôt que , , , , on trouve

II-2 Polynômes symétriques

Polynômes et séries formelles → II Polynômes → II-2 Polynômes symétriques

Un polynôme de plusieurs variables est dit symétrique s'il ne dépend pas de l'ordre des variables. Par exemple chaque est une fonction symétrique des . En fait tous les polynômes symétriques s'obtiennent à partir de ces derniers, ce qui justifie leur nom.

Théorème

Pour tout polynôme symétrique en les indéterminées , il existe un polynôme (et un seul) tel que .

Démonstration

Nous allons prouver l'existence de g en énonçant un algorithme permettant de le calculer. On peut ordonner les monômes de la façon suivante: vient avant si et seulement si k₁>k'₁, ou k₁=k'₁ et k₂>k'₂, ou k₁=k'₁ et k₂=k'₂ et k₃>k'₃, etc. Tout polynôme f non nul a un terme dominant qui est le premier qui intervient avec un coefficient c non nul. Si f est symétrique, on voit que ce terme vérifie . On définit alors

Substituons à , puis développons en les . On obtient un polynôme t(f) symétrique en les et un examen attentif montre que le terme dominant du polynôme t(f) est le même que celui de f. Cela justifie l'algorithme suivant

Donnée: un polynôme f symétrique en n indéterminées
Sortie: un polynôme g satisfaisant à la condition du théorème


g <- 0
tant que f n'est pas nul faire
  g <- g + s(f)
  f <- f - t(f)
fin tant que

Il reste à voir que l'algorithme s'arrête. Cela est dû au fait que la suite des termes dominants est strictement décroissante au sens de l'ordre défini plus haut et que cet ordre lexicographique est un bon ordre dans lequel, comme dans , toute suite strictement décroissante est finie.

Donnons un exemple du procédé. Nous prenons n=3 et les variables a, b et c plutôt que , et . On part du polynôme symétrique

f=a³ b+a³ c+a b³+ac³+b c³+b³ c

présenté en ordre lexicographique décroissant. On a donc d(f)=a³ c et s(f)=S₁² S₂, donc

t(f)=(a+b+c)²(a b+a c+b c)
== a³ b+a³ c+2a² b²+5a² b c+2a² c²+a b³
5a b² c+5a b c²+ac³+b³ c+2b² c²+b c^3.0

On recommence donc avec une nouvelle valeur de

f= -2a² b²-5a² b c-2a² c²-5a b² c-5a b c²-2b² c²

Le terme dominant est d(f)= -2a² b² et s(f)= -2S₂², donc

t(f)= -2(a b+a c+b c)²= -2a² b²-4a² b c-2a² c²-4a b² c-4a b c²-2b² c²

On recommence donc avec une nouvelle valeur de

f= -a² b c-a b² c-a b c²

Le terme dominant est d(f)= -a² b c et s(f)= -S₁ S₃ donc

t(f)= -(a+b+c)(a b c)= f

ce qui achève l'algorithme. Le polynôme obtenu est donc g=S₁² S₂-2S₂²-S₁ S₃ et on obtient l'identité

II-3 Les formules de Newton

Polynômes et séries formelles → II Polynômes → II-3 Les formules de Newton

Nous allons donner une version explicite du théorème précédent dans un cas particulier. Notons

la somme des puissances k-ièmes des . C'est une fonction symétrique des , que l'on peut donc exprimer en fonction des . Il est en fait possible de calculer les s_k par récurrence grâce aux formules de Newton:

Théorème

Pour , on a

et pour

Démonstration

Partons de la relation de définition

dérivons-la

divisons membre à membre ces deux égalités

substituons à X et chassons les dénominateurs en T

Écrivons le développement en série formelle du premier membre:

L'identité ci-dessus peut donc s'écrire

ou encore

Le coefficient de T^k dans le premier membre est

La comparaison avec le second membre donne les formules de Newton.

On déduit de ces formules l'expression des s_k en fonction polynômiale des :

mais cette expression explicite devient vite compliquée.

II-4 Un exemple

Polynômes et séries formelles → II Polynômes → II-4 Un exemple

Le polynôme X⁴-X³-2X²+5X-1 a quatre racines dans : , , et . On a

On en déduit les sommes de puissances successives

et ainsi de suite. On remarque que cette procédure est en quelque sorte l'inverse de celle concernant les récurrences linéaires à coefficients constants: au lieu de partir d'une suite s_k qui satisfait une récurrence linéaire et de trouver des qui permettent d'exprimer s_k comme combinaison linéaire des puissances k-ièmes des , on part des et on trouve une récurrence linéaire satisfaite par la suite s_k.

document de cours.
: series,polynomials, interactive mathematics, interactive math, server side interactivity

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.