Polynômes et séries formelles

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 formellesI Séries formelles → I-1 L'anneau des séries formelles
Un polynôme P= n=0 pa nX n est simplement une façon commode de noter la suite finie (a n) 0np de ses coefficients. Si Q= n=0 qb nX n est un autre polynôme, on définit leur somme et leur produit par

P+Q= n=0 max(p,q)(a n+b n)X n, etPQ= n=0 p+q( i=0 na ib ni)X n.

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 (a n) n à 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 (a n) n à valeurs dans un anneau commutatif 𝒜, on associe donc une série entière formelle, notée

A= n=0 a nX n

et on définit des opérations sur ces objets. Si B= n=0 b nX n est une autre série entière formelle, leur somme S=A+B= n=0 s nX n et leur produit P=AB= n=0 p nX n sont définis par

n,s n=a n+b n etp n= i=0 na ib ni= i+j=na ib j.


Pour tout élément a de 𝒜 la suite de coefficients a 0=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 𝒜[[X]] l'ensemble des séries entières formelles à coefficients dans 𝒜.

Théorème

Muni des lois ci-dessus, l'ensemble 𝒜[[X]] 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 A= n=0 (a n)X n.

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 C= n=0 c nX n une troisième série. On a
(AB)C = n( i+j=n( k+l=ia kb l)c j)X n = n( k+l+j=na kb lcj)X n = n( k+m=na k( l+j=mb lcj))X n = A(BC)
et
A(B+C) = n( i+j=na i(b j+c j))X n = n( i+j=na ibj+a icj)X n = n( i+j=na ibj)X n+ n( i+j=na icj)X n = AB+AC

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

Théorème

Si 𝒜 est intègre, 𝒜[[X]] l'est aussi.

Démonstration
Supposons A0 et B0. La suite (a n) n n'est pas identiquement nulle. Il existe donc un entier i 0 tel que a i 00 et i<i 0,a i=0. De même, il existe j 0 tel que b j 00 et j<j 0,b j=0. Posons n 0=i 0+j 0. On a

i+j=n 0a ibj= i+j=n 0 i<i 0a ibj+a i 0b j 0+ i+j=n 0 j<j 0a ibj=a i 0b j 00

puisque 𝒜 est intègre. On en déduit que le coefficent de X n 0 dans AB est non nul et AB0.

I-2 Inversion, composition, dérivation

Polynômes et séries formellesI Séries formelles → I-2 Inversion, composition, dérivation
Les séries dont le terme constant est 1 sont inversibles:

Proposition

Si A=1+ n1a nX n est une série entière formelle dont le coefficient constant est 1, il existe une unique série

B=1+ n1b nX n

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

Démonstration
La condition s'écrit a 0b 0=1 et k=0 na kb nk=0 pour n>0. La suite définie par récurrence par

{ pour \( n\gt 0 \right.$ERROR} {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 a𝒜. 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 A= na nX n est une série entière formelle quelconque, et B= n1b nX n est une série entière formelle dont le coefficient constant est nul, il existe une série C= nc nX n et une seule, notée A(B) ou AB, telle que pour tout n c n soit le coefficient de X n dans l'écriture de la série k=0 makB k pour tout mn. On écrit aussi C= na nB n.

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

A= n(n+1)a n+1X n= n1na nX n1.

On a les relations habituelles
(A+B) = A+B (AB) = AB+AB (AB) = B.(AB).

Démonstration
Démontrons la deuxième égalité. On a
(AB) = n((n+1) k=0 n+1a kb n+1k)X n = n( k=1 n+1ka kb n+1k+ k=0 n(n+1k)a kb n+1k)X n = n( k=0 n(k+1)a k+1b nk)X n+ n( k=0 na k(nk+1)b nk1)X n = AB+AB

I-3 Quelques exemples


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

11X= nX n=1+X+X 2+X 3+

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

11αX= nα nX n=1+αX+α 2X 2+α 3X 3+

On peut définir une exponentielle formelle dans [[X]]

E(X)= nX nn!=1+X+X 22+X 36+

et un logarithme formel

L(X)= n1(1) n+1X nn=XX 22+X 33+

et on a les relations

E(L(X))=1+X,L(E(X)1)=X.


En effet, on voit facilement que E=E et L=11+X. On a donc (L(E1))=E.L(E1)=EE=1, ce qui donne L(E1)=X puisque le coefficient constant est 0. De même, (E(L))=LE(L), donc (1+X)(E(L))=E(L). Les coefficients de E(L) vérifient donc la récurrence (n+1)a n+1+na n=a n, ou encore a n+1=1n1+na n qui, compte tenu de a 0=1, donne a 1=1 et a n=0 pour n>1, donc E(L)=1+X.
Pour tout a𝒜 et tout n, introduisons la factorielle descendante a n̲=a(a1)(an+1) définie par récurrence par a 0̲=1 et a n+1̲=(an)a n̲. Si 𝒜 et α𝒜 on peut définir
(1+X) α=E(αL(X))= nα n̲n!X n
==1+αX+α(α1)2X 2+α(α1)(α2)6X 3+

En effet, on a E(αL)=αLE(αL). Les coefficients de E(L) vérifient donc la récurrence (n+1)a n+1+na n=αa n, ou encore a n+1=αn1+na n qui, compte tenu de a 0=1, donne bien a n=<α> nn!.
Si α, la série est un polynôme, et on retrouve bien la formule du binôme. On a alors la

Proposition

α,β𝒜,(1+X) α+β=(1+X) α(1+X) β.


Démonstration
En utilisant la formule du binôme, on prouve
E(αX)E(βX) = n( k=0 nα kk!β nk(nk)!)X n = n1n!( k=0 n(nk)α kβ nk)X n = n(α+β) nn!X n = E((α+β)X)
et on obtient la relation cherchée en substituant L à X.

Explicitons en particulier le cas de la racine carrée

1+X=1+ n1(1) n12 2n1n(2n2n1)X n.

En effet, le coefficient (1/2) n̲n! peut s'écrire

12123232n2n!=(1) n11.3.5.(2n3)2 nn!=(1) n1(2n2)!2 2n1n!(n1)!

en ``complétant la factorielle'' au numérateur par les facteurs impairs manquants 2.4.6(2n2)=2 n1(n1)!, d'où le résultat.

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

Polynômes et séries formellesI 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 0=4, u 1=13 et u n=5u n16u n2 pour n2. On forme la série
U = nu nX n = 4+13X+ n2u nX n = 4+13X+5 n2u n1X n6 n2u n2X n = 4+13X+5X(U4)6X 2U = 47X+(5X6X 2)U
Il s'agit d'une équation de degré 1 en U, que l'on résout:

U=47X15X+6X 2=47X(12X)(13X)

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

U=513X112X= n(5.3 n2 n)X n

et la formule finale n,u n=5.3 n2 n.
Dans ce cas, le polynôme caractéristique 15X+6X 2 avait deux racines distinctes, 12 et 13. Voyons ce qui se passe s'il a une racine double. Définissons la suite v par v 0=1, v 1=6 et v n=6v n19v n2. Un calcul similaire donne

V=116X+9X 2=1(13X) 2= n(n+1)3 nX n

Cette dernière formule peut s'obtenir soit à partir de la formule générale pour (1+X) α avec α=2, soit en remarquant que 1(1X) 2 est la dérivée de 11X= nX n.

I-5 Les nombres de Catalan

Polynômes et séries formellesI 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 3=5. On voit facilement que C 0=C 1=1 et C 2=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,k1) et entre les points (1,0) et (k,k1), il parcourt un chemin acceptable dans le carré de sommets (1,0) et (k,k1) qui est de côté k1. La figure représente un cas avec n=7 et k=4.
Il y a donc C k1 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é nk. Il y a donc C nk possibilités pour cette deuxième étape. Le nombre de chemins possibles à k fixé est donc C k1C nk et on a établi la formule

n1,C n= k=1 nCk1C nk= k=0 n1C kCn1k

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

F=1+ n1( k=0 n1C kCn1k)X n=1+X m( k=0 mCkCmk)X m

en posant m=n1. On reconnait sur la droite le développement de F 2. On a donc prouvé

F=1+XF 2

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

F=1±14X2X

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

14X=1 n12n(2n2n1)X n.


On a donc

F=114X2X= n11n(2n2n1)X n1= n1n+1(2nn)X n

et la formule

n,C n=1n+1(2nn)=2n!n!(n+1)!.


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

G=114X2X= n1n+1(2nn)X n

vérifie bien G=1+XG 2. En soustrayant cette équation à F=1+XF 2, on trouve (FG)(1X(F+G))=0. Comme le facteur 1X(F+G) n'est pas nul et [[X]] 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

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 formellesII Polynômes → II-1 Relations entre racines et coefficients
Soit (α 1,α 2,,α n) un n-uplet d'éléments d'un anneau commutatif A. On définit le polynôme unitaire

P= i=1 n(Xα i).

On peut encore utiliser la formule du produit en posant a i=α i et b i=X. On trouve

P= I[1,n](1) I( iIα i)X nI

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

P= k=0 n(1) k I[1,n] I=k( iIα i)X nk= k=0 n(1) kσ kX nk.

σ k= I[1,n] I=k( iIα i)

est le k-ième polynôme symétrique élémentaire des (α i) i[1,n]. Par exemple, pour n=4, en notant a, b, c et c plutôt que α 1, α 2, α 3, α 4, on trouve
σ 0 = 1 σ 1 = =a+b+c+d σ 2 = ab+ac+ad+bc+bd+cd σ 3 = abc+abd+acd+bcd σ 4 = abcd σ k = 0 pour k>4.

II-2 Polynômes symétriques

Polynômes et séries formellesII 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 σ k est une fonction symétrique des α i. 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 fA[α 1,,α n] symétrique en les indéterminées (α i) 1in, il existe un polynôme gA[S 1,,S n] (et un seul) tel que f(α 1,,α n)=g(σ 1,,σ n).

Démonstration

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

s(f)=cS 1 k 1k 2S 2 k 2k 3S n1 k n1k nS n k n


Substituons σ 1,,σ n à S 1,,S n, puis développons en les α i. On obtient un polynôme t(f) symétrique en les α i 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 α 1, α 2 et α 3. On part du polynôme symétrique

f=a 3b+a 3c+ab 3+ac 3+bc 3+b 3c

présenté en ordre lexicographique décroissant. On a donc d(f)=a 3c et s(f)=S 1 2S 2, donc
t(f)=(a+b+c) 2(ab+ac+bc)
==a 3b+a 3c+2a 2b 2+5a 2bc+2a 2c 2+ab 3
5ab 2c+5abc 2+ac 3+b 3c+2b 2c 2+bc 3.0

On recommence donc avec une nouvelle valeur de

f=2a 2b 25a 2bc2a 2c 25ab 2c5abc 22b 2c 2

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

t(f)=2(ab+ac+bc) 2=2a 2b 24a 2bc2a 2c 24ab 2c4abc 22b 2c 2


On recommence donc avec une nouvelle valeur de

f=a 2bcab 2cabc 2

Le terme dominant est d(f)=a 2bc et s(f)=S 1S 3 donc

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

ce qui achève l'algorithme. Le polynôme obtenu est donc g=S 1 2S 22S 2 2S 1S 3 et on obtient l'identité

a 3b+a 3c+ab 3+ac 3+bc 3+b 3c=σ 1 2σ 22σ 2 2σ 1σ 3.

II-3 Les formules de Newton

Polynômes et séries formellesII 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

s k= i=1 nα i k

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

Théorème

Pour kn, on a

s k= i=1 k1(1) i1σ is ki+(1) k1kσ k

et pour kn

s k= i=1 n(1) i1σ is ki.


Démonstration
Partons de la relation de définition

i=1 n(Xα i)= i=0 n(1) iσ iX ni=X nσ 1X n1+,

dérivons-la

i=1 n ji(Xα j)= i=0 n1(1) i(ni)σ iX ni1=nX n1(n1)σ 1X n1+,

divisons membre à membre ces deux égalités

i=1 n1Xα i= i=0 n1(1) i(ni)σ iX ni1 i=0 n(1) iσ iX ni=nX n1(n1)σ 1X n1+X nσ 1X n1+,

substituons 1T à X et chassons les dénominateurs en T

i=1 n11α iT= i=0 n1(1) i(ni)σ iT i i=0 n(1) iσ iT i=n(n1)σ 1T+1σ 1T+.

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

L= i=1 n11α iT= i=1 n( jσ i jT j)= js jT j.

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

( i=0 n(1) iσ iT i)( js jT j)= i=0 n1(1) i(ni)σ iT i

ou encore
(s 0+s 1T+s 2T 2)(1σ 1T++(1) nσ nT n)
==n(n1)σ 1T++(1) n1σ n1T n1.

Le coefficient de T k dans le premier membre est

i=0 min(k,n)(1) iσ iski.

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 σ i:
s 1 = σ 1 s 2 = σ 1 22σ 2 s 3 = σ 1 33σ 1σ 2+3σ 3 s 4 = σ 1 44σ 1 2σ 2+4σ 1σ 3+2σ 2 24σ 4
mais cette expression explicite devient vite compliquée.

II-4 Un exemple

Le polynôme X 4X 32X 2+5X1 a quatre racines dans : α 11.8072, α 20.2213, α 31.29290.9105i et α 4=α 3 ¯ 1.2929+0.9105i. On a
σ 1 = 1 σ 2 = 2 σ 3 = 5 σ 4 = 1

On en déduit les sommes de puissances successives

s 1 = σ 1 = σ 1 = 1 s 2 = σ 1s 12σ 2 = s 1+4 = 5 s 3 = σ 1s 2σ 2s 1+3σ 3 = s 2+2s 115 = 8 s 4 = σ 1s 3σ 2s 2+σ 3s 14σ 4 = s 3+2s 25s 1+4 = 1 s 5 = σ 1s 4σ 2s 3+σ 3s 2σ 4s 1 = s 4+2s 35s 2+s 1 = 39 s 6 = σ 1s 5σ 2s 4+σ 3s 3σ 4s 2 = s 5+2s 45s 3+s 2 = 8

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 α i qui permettent d'exprimer s k comme combinaison linéaire des puissances k-ièmes des α i, on part des α i et on trouve une récurrence linéaire satisfaite par la suite s k.

document de cours.
: series,polynomials, serveur interactif, enseignement, cours en ligne, ressources pédagogiques, sciences, langues, qcm,classes,exercices

The most recent version

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

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.