Polynômes et séries formelles

. 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

𝒜 = ℤ

ℚ

ℝ

ℂ

.
Ë toute suite

(a_{n})_{n \in ℕ}

à valeurs dans un anneau commutatif

𝒜

, on associe donc une série entière formelle, notée

$A = \sum_{n = 0}^{∞} a_{n} X^{n}$

et on définit des opérations sur ces objets. Si

B = \sum_{n = 0}^{∞} b_{n} X^{n}

est une autre série entière formelle, leur somme

S = A + B = \sum_{n = 0}^{∞} s_{n} X^{n}

et leur produit

P = A B = \sum_{n = 0}^{∞} p_{n} X^{n}

sont définis par

$\forall n \in ℕ, s_{n} = a_{n} + b_{n} et p_{n} = \sum_{i = 0}^{n} a_{i} b_{n - i} = \sum_{i + j = n} a_{i} b_{j} .$

Pour tout élément

a

𝒜

la suite de coefficients

a_{0} = a

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

1

, et l'opposé de

A

est donné par

- A = \sum_{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 = \sum_{n = 0}^{∞} c_{n} X^{n}

une troisième série. On a

\begin{matrix} (A B) C & = & \sum_{n \in ℕ} (\sum_{i + j = n} (\sum_{k + l = i} a_{k} b_{l}) c_{j}) X^{n} \\ = & \sum_{n \in ℕ} (\sum_{k + l + j = n} a_{k} b_{lc}_{j}) X^{n} \\ = & \sum_{n \in ℕ} (\sum_{k + m = n} a_{k} (\sum_{l + j = m} b_{lc}_{j})) X^{n} \\ = & A (BC) \end{matrix}

\begin{matrix} A (B + C) & = & \sum_{n \in ℕ} (\sum_{i + j = n} a_{i} (b_{j} + c_{j})) X^{n} \\ = & \sum_{n \in ℕ} (\sum_{i + j = n} a_{ib}_{j} + a_{ic}_{j}) X^{n} \\ = & \sum_{n \in ℕ} (\sum_{i + j = n} a_{ib}_{j}) X^{n} + \sum_{n \in ℕ} (\sum_{i + j = n} a_{ic}_{j}) X^{n} \\ = & AB + AC \end{matrix}

Un anneau

𝒜

est intègre si l'équation

x y = 0

dans

𝒜

implique

x = 0

y = 0

Théorème

𝒜

est intègre,

𝒜 [[X]]

l'est aussi.

Démonstration

Supposons

A \neq 0

B \neq 0

. La suite

(a_{n})_{n \in ℕ}

n'est pas identiquement nulle. Il existe donc un entier

i_{0}

tel que

a_{i_{0}} \neq 0

\forall i < i_{0}, a_{i} = 0

. De même, il existe

j_{0} \in ℕ

tel que

b_{j_{0}} \neq 0

\forall j < j_{0}, b_{j} = 0

. Posons

n_{0} = i_{0} + j_{0}

. On a

$\sum_{i + j = n_{0}} a_{ib}_{j} = \sum_{\begin{array}{c} i + j = n_{0} \\ i < i_{0} \end{array}} a_{ib}_{j} + a_{i_{0}} b_{j_{0}} + \sum_{\begin{array}{c} i + j = n_{0} \\ j < j_{0} \end{array}} a_{ib}_{j} = a_{i_{0}} b_{j_{0}} \neq 0$

puisque

𝒜

est intègre. On en déduit que le coefficent de

X^{n_{0}}

dans

A B

est non nul et

A B \neq 0

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

A = 1 + \sum_{n \geq 1} a_{n} X^{n}

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

$B = 1 + \sum_{n \geq 1} b_{n} X^{n}$

telle que

A B = 1

. Cette série sera notée

\frac{1}{A}

Démonstration

La condition s'écrit

a_{0} b_{0} = 1

\sum_{k = 0}^{n} a_{k} b_{n - k} = 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 \in 𝒜

. Par contre, il est possible de composer les séries

A

B

, ce qui revient à évaluer

A

B

, à condition que le coefficient constant de

B

soit nul.

Proposition

A = \sum_{n \in ℕ} a_{n} X^{n}

est une série entière formelle quelconque, et

B = \sum_{n \geq 1} b_{n} X^{n}

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

C = \sum_{n \in ℕ} c_{n} X^{n}

et une seule, notée

A (B)

A \circ B

, telle que pour tout

n

c_{n}

soit le coefficient de

X^{n}

dans l'écriture de la série

\sum_{k = 0}^{ma}_{k} B^{k}

pour tout

m \geq n

. On écrit aussi

C = \sum_{n \in ℕ} a_{n} B^{n}

On peut définir une dérivation. Si

A = \sum_{n \in ℕ} a_{n} X^{n}

on appelle dérivée de

A

et on note

A'

la série

$A' = \sum_{n \in ℕ} (n + 1) a_{n + 1} X^{n} = \sum_{n \geq 1} n a_{n} X^{n - 1} .$

On a les relations habituelles

\begin{matrix} (A + B)' & = & A' + B' \\ (A B)' & = & A' B + A B' \\ (A \circ B)' & = & B' . (A' \circ B) . \end{matrix}

Démonstration

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

\begin{matrix} (A B)' & = & \sum_{n \in ℕ} ((n + 1) \sum_{k = 0}^{n + 1} a_{k} b_{n + 1 - k}) X^{n} \\ = & \sum_{n \in ℕ} (\sum_{k = 1}^{n + 1} k a_{k} b_{n + 1 - k} + \sum_{k = 0}^{n} (n + 1 - k) a_{k} b_{n + 1 - k}) X^{n} \\ = & \sum_{n \in ℕ} (\sum_{k = 0}^{n} (k + 1) a_{k + 1} b_{n - k}) X^{n} + \sum_{n \in ℕ} (\sum_{k = 0}^{n} a_{k} (n - k + 1) b_{n - k - 1}) X^{n} \\ = & A' B + A B' \end{matrix}

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

$\frac{1}{1 - X} = \sum_{n \in ℕ} X^{n} = 1 + X + X^{2} + X^{3} + \dots$

plus généralement, si

α \in 𝒜

, on peut écrire

$\frac{1}{1 - α X} = \sum_{n \in ℕ} α^{n} X^{n} = 1 + α X + α^{2} X^{2} + α^{3} X^{3} + \dots$

On peut définir une exponentielle formelle dans

ℚ [[X]]

$E (X) = \sum_{n \in ℕ} \frac{X^{n}}{n!} = 1 + X + \frac{X^{2}}{2} + \frac{X^{3}}{6} + \dots$

et un logarithme formel

$L (X) = \sum_{n \geq 1} (- 1)^{n + 1} \frac{X^{n}}{n} = X - \frac{X^{2}}{2} + \frac{X^{3}}{3} + \dots$

et on a les relations

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

En effet, on voit facilement que

E' = E

L' = \frac{1}{1 + X}

. On a donc

(L (E - 1))' = E . L' (E - 1) = \frac{E}{E} = 1

, 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

(n + 1) a_{n + 1} + n a_{n} = a_{n}

, ou encore

a_{n + 1} = \frac{1 - n}{1 + n} a_{n}

qui, compte tenu de

a_{0} = 1

, donne

a_{1} = 1

a_{n} = 0

pour

n > 1

, donc

E (L) = 1 + X

.
Pour tout

a \in 𝒜

et tout

n \in ℕ

, introduisons la factorielle descendante

a^{\underset{̲}{n}} = a (a - 1) \dots (a - n + 1)

définie par récurrence par

a^{\underset{̲}{0}} = 1

a^{\underset{̲}{n + 1}} = (a - n) a^{\underset{̲}{n}}

. Si

ℚ \subset 𝒜

α \in 𝒜

on peut définir

(1 + X)^{α} = E (α L (X)) = \sum_{n \in ℕ} \frac{α^{\underset{̲}{n}}}{n!} X^{n}

= = 1 + α X + \frac{α (α - 1)}{2} X^{2} + \frac{α (α - 1) (α - 2)}{6} X^{3} + \dots

En effet, on a

E (α L)' = α L' E (α L)

. Les coefficients de

E (L)

vérifient donc la récurrence

(n + 1) a_{n + 1} + n a_{n} = α a_{n}

, ou encore

a_{n + 1} = \frac{α - n}{1 + n} a_{n}

qui, compte tenu de

a_{0} = 1

, donne bien

a_{n} = \frac{< α >_{n}}{n!}

.
Si

α \in ℕ

, la série est un polynôme, et on retrouve bien la formule du binôme. On a alors la

Proposition

$\forall α, β \in 𝒜, (1 + X)^{α + β} = (1 + X)^{α} \cdot (1 + X)^{β} .$

Démonstration

En utilisant la formule du binôme, on prouve

\begin{matrix} E (α X) E (β X) & = & \sum_{n \in ℕ} (\sum_{k = 0}^{n} \frac{α^{k}}{k!} \cdot \frac{β^{n - k}}{(n - k)!}) X^{n} \\ = & \sum_{n \in ℕ} \frac{1}{n!} (\sum_{k = 0}^{n} (\binom{n}{k}) α^{k} β^{n - k}) X^{n} \\ = & \sum_{n \in ℕ} \frac{(α + β)^{n}}{n!} X^{n} \\ = & E ((α + β) X) \end{matrix}

et on obtient la relation cherchée en substituant

L

X

Explicitons en particulier le cas de la racine carrée

$\sqrt{1 + X} = 1 + \sum_{n \geq 1} \frac{(- 1)^{n - 1}}{2^{2 n - 1} n} (\binom{2 n - 2}{n - 1}) X^{n} .$

En effet, le coefficient

\frac{(1 / 2)^{\underset{̲}{n}}}{n!}

peut s'écrire

$\frac{\frac{1}{2} \cdot \frac{- 1}{2} \cdot \frac{- 3}{2} \dots \frac{3 - 2 n}{2}}{n!} = \frac{(- 1)^{n - 1} 1.3 .5 . \dots (2 n - 3)}{2^{nn}!} = \frac{(- 1)^{n - 1} (2 n - 2)!}{2^{2 n - 1} n! (n - 1)!}$

en ``complétant la factorielle'' au numérateur par les facteurs impairs manquants

2.4 .6 \dots (2 n - 2) = 2^{n - 1} (n - 1)!

, 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_{0} = 4

u_{1} = 13

u_{n} = 5 u_{n - 1} - 6 u_{n - 2}

pour

n \geq 2

. On forme la série

\begin{matrix} U & = & \sum_{n \in ℕ} u_{n} X^{n} \\ = & 4 + 13 X + \sum_{n \geq 2} u_{n} X^{n} \\ = & 4 + 13 X + 5 \sum_{n \geq 2} u_{n - 1} X^{n} - 6 \sum_{n \geq 2} u_{n - 2} X^{n} \\ = & 4 + 13 X + 5 X (U - 4) - 6 X^{2} U \\ = & 4 - 7 X + (5 X - 6 X^{2}) U \end{matrix}

Il s'agit d'une équation de degré 1 en

U

, que l'on résout:

$U = \frac{4 - 7 X}{1 - 5 X + 6 X^{2}} = \frac{4 - 7 X}{(1 - 2 X) (1 - 3 X)}$

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

$U = \frac{5}{1 - 3 X} - \frac{1}{1 - 2 X} = \sum_{n \in ℕ} ({5.3}^{n} - 2^{n}) X^{n}$

et la formule finale

\forall n \in ℕ, u_{n} = {5.3}^{n} - 2^{n}

.
Dans ce cas, le polynôme caractéristique

1 - 5 X + 6 X^{2}

avait deux racines distinctes,

\frac{1}{2}

\frac{1}{3}

. Voyons ce qui se passe s'il a une racine double. Définissons la suite

v

par

v_{0} = 1

v_{1} = 6

v_{n} = 6 v_{n - 1} - 9 v_{n - 2}

. Un calcul similaire donne

$V = \frac{1}{1 - 6 X + 9 X^{2}} = \frac{1}{(1 - 3 X)^{2}} = \sum_{n \in ℕ} (n + 1) 3^{n} X^{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

\frac{1}{(1 - X)^{2}}

est la dérivée de

\frac{1}{1 - X} = \sum_{n \in ℕ} X^{n}

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_{3} = 5

. On voit facilement que

C_{0} = C_{1} = 1

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, k - 1)

et entre les points

(1, 0)

(k, k - 1)

, il parcourt un chemin acceptable dans le carré de sommets

(1, 0)

(k, k - 1)

qui est de côté

k - 1

. La figure représente un cas avec

n = 7

k = 4

Il y a donc

C_{k - 1}

possibilités pour cette première étape. Entre

D = (k, k)

E = (n, n)

, il parcourt un chemin acceptable dans le carré de sommets

(k, k)

(n, n)

qui est de côté

n - k

. Il y a donc

C_{n - k}

possibilités pour cette deuxième étape. Le nombre de chemins possibles à

k

fixé est donc

C_{k - 1} C_{n - k}

et on a établi la formule

$\forall n \geq 1, C_{n} = \sum_{k = 1}^{nC}_{k - 1} C_{n - k} = \sum_{k = 0}^{n - 1} C_{kC}_{n - 1 - k}$

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 = \sum_{n \in ℕ} C_{n} X^{n}

. On a donc

$F = 1 + \sum_{n \geq 1} (\sum_{k = 0}^{n - 1} C_{kC}_{n - 1 - k}) X^{n} = 1 + X \sum_{m \in ℕ} (\sum_{k = 0}^{mC}_{kC}_{m - k}) X^{m}$

en posant

m = n - 1

. On reconnait sur la droite le développement de

F^{2}

. On a donc prouvé

$F = 1 + X F^{2}$

ce qui est une équation du second degré en

F

. La résolution habituelle de l'équation

X F^{2} - F + 1 = 0

, de discriminant

Δ = 1 - 4 X

donnerait

$F = \frac{1 \pm \sqrt{1 - 4 X}}{2 X}$

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

\sqrt{1 + X}

, on trouve

$\sqrt{1 - 4 X} = 1 - \sum_{n \geq 1} \frac{2}{n} (\binom{2 n - 2}{n - 1}) X^{n} .$

On a donc

$F = \frac{1 - \sqrt{1 - 4 X}}{2 X} = \sum_{n \geq 1} \frac{1}{n} (\binom{2 n - 2}{n - 1}) X^{n - 1} = \sum_{n \in ℕ} \frac{1}{n + 1} (\binom{2 n}{n}) X^{n}$

et la formule

$\forall n \in ℕ, C_{n} = \frac{1}{n + 1} (\binom{2 n}{n}) = \frac{2 n!}{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 = \frac{1 - \sqrt{1 - 4 X}}{2 X} = \sum_{n \in ℕ} \frac{1}{n + 1} (\binom{2 n}{n}) X^{n}$

vérifie bien

G = 1 + X G^{2}

. En soustrayant cette équation à

F = 1 + X F^{2}

, on trouve

(F - G) (1 - X (F + G)) = 0

. Comme le facteur

1 - X (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

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

(α_{1}, α_{2}, \dots, α_{n})

n

-uplet d'éléments d'un anneau commutatif

A

. On définit le polynôme unitaire

$P = \prod_{i = 1}^{n} (X - α_{i}) .$

On peut encore utiliser la formule du produit en posant

a_{i} = - α_{i}

b_{i} = X

. On trouve

$P = \sum_{I \subset [1, n]} (- 1)^{∣ I ∣} (\prod_{i \in I} α_{i}) X^{n - ∣ I ∣}$

ce qui suggère de regrouper les

I

de même cardinal

k

$P = \sum_{k = 0}^{n} (- 1)^{k} \sum_{\begin{array}{c} I \subset [1, n] \\ ∣ I ∣ = k \end{array}} (\prod_{i \in I} α_{i}) X^{n - k} = \sum_{k = 0}^{n} (- 1)^{k} σ_{k} X^{n - k} .$

où

$σ_{k} = \sum_{\begin{array}{c} I \subset [1, n] \\ ∣ I ∣ = k \end{array}} (\prod_{i \in I} α_{i})$

est le

k

-ième polynôme symétrique élémentaire des

(α_{i})_{i \in [1, n]}

. Par exemple, pour

n = 4

, en notant

a

b

c

c

plutôt que

α_{1}

α_{2}

α_{3}

α_{4}

, on trouve

\begin{matrix} σ_{0} & = & 1 \\ σ_{1} & = & = a + b + c + d \\ σ_{2} & = & a b + a c + a d + b c + b d + c d \\ σ_{3} & = & a b c + a b d + a c d + b c d \\ σ_{4} & = & a b c d \\ σ_{k} & = & 0 pour k > 4 . \end{matrix}

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

σ_{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

f \in A [α_{1}, \dots, α_{n}]

symétrique en les indéterminées

(α_{i})_{1 \leq i \leq n}

, il existe un polynôme

g \in A [S_{1}, \dots, S_{n}]

(et un seul) tel que

f (α_{1}, \dots, α_{n}) = g (σ_{1}, \dots, σ_{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}} \dots α_{n}^{k_{n}}

de la façon suivante:

α_{1}^{k_{1}} \dots α_{n}^{k_{n}}

vient avant

α_{1}^{k'_{1}} \dots α_{n}^{k'_{n}}

si et seulement si

k_{1} > k'_{1}

, ou

k_{1} = k'_{1}

k_{2} > k'_{2}

, ou

k_{1} = k'_{1}

k_{2} = k'_{2}

k_{3} > k'_{3}

, etc. Tout polynôme

f

non nul a un terme dominant

d (f) = c . α_{1}^{k_{1}} \dots α_{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_{1} \geq k_{2} \geq \dots \geq k_{n}

. On définit alors

$s (f) = c S_{1}^{k_{1} - k_{2}} S_{2}^{k_{2} - k_{3}} \dots S_{n - 1}^{k_{n - 1} - k_{n}} S_{n}^{k_{n}}$

Substituons

σ_{1}, \dots, σ_{n}

S_{1}, \dots, 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

c

plutôt que

α_{1}

α_{2}

α_{3}

. On part du polynôme symétrique

$f = a^{3} b + a^{3} c + a b^{3} + {ac}^{3} + b c^{3} + b^{3} c$

présenté en ordre lexicographique décroissant. On a donc

d (f) = a^{3} c

s (f) = S_{1}^{2} S_{2}

, donc

t (f) = (a + b + c)^{2} (a b + a c + b c)

= = a^{3} b + a^{3} c + 2 a^{2} b^{2} + 5 a^{2} b c + 2 a^{2} c^{2} + a b^{3}

5 a b^{2} c + 5 a b c^{2} + {ac}^{3} + b^{3} c + 2 b^{2} c^{2} + b c^{3.0}

On recommence donc avec une nouvelle valeur de

$f = - 2 a^{2} b^{2} - 5 a^{2} b c - 2 a^{2} c^{2} - 5 a b^{2} c - 5 a b c^{2} - 2 b^{2} c^{2}$

Le terme dominant est

d (f) = - 2 a^{2} b^{2}

s (f) = - 2 S_{2}^{2}

, donc

$t (f) = - 2 (a b + a c + b c)^{2} = - 2 a^{2} b^{2} - 4 a^{2} b c - 2 a^{2} c^{2} - 4 a b^{2} c - 4 a b c^{2} - 2 b^{2} c^{2}$

On recommence donc avec une nouvelle valeur de

$f = - a^{2} b c - a b^{2} c - a b c^{2}$

Le terme dominant est

d (f) = - a^{2} b c

s (f) = - S_{1} S_{3}

donc

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

ce qui achève l'algorithme. Le polynôme obtenu est donc

g = S_{1}^{2} S_{2} - 2 S_{2}^{2} - S_{1} S_{3}

et on obtient l'identité

$a^{3} b + a^{3} c + a b^{3} + a c^{3} + b c^{3} + b^{3} c = σ_{1}^{2} σ_{2} - 2 σ_{2}^{2} - σ_{1} σ_{3} .$

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

$s_{k} = \sum_{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

k \leq n

, on a

$s_{k} = \sum_{i = 1}^{k - 1} (- 1)^{i - 1} σ_{i} s_{k - i} + (- 1)^{k - 1} k σ_{k}$

et pour

k \geq n

$s_{k} = \sum_{i = 1}^{n} (- 1)^{i - 1} σ_{i} s_{k - i} .$

Démonstration

Partons de la relation de définition

$\prod_{i = 1}^{n} (X - α_{i}) = \sum_{i = 0}^{n} (- 1)^{i} σ_{i} X^{n - i} = X^{n} - σ_{1} X^{n - 1} + \dots,$

dérivons-la

$\sum_{i = 1}^{n} \prod_{j \neq i} (X - α_{j}) = \sum_{i = 0}^{n - 1} (- 1)^{i} (n - i) σ_{iX}^{n - i - 1} = n X^{n - 1} - (n - 1) σ_{1} X^{n - 1} + \dots,$

divisons membre à membre ces deux égalités

$\sum_{i = 1}^{n} \frac{1}{X - α_{i}} = \frac{\sum_{i = 0}^{n - 1} (- 1)^{i} (n - i) σ_{iX}^{n - i - 1}}{\sum_{i = 0}^{n} (- 1)^{i} σ_{i} X^{n - i}} = \frac{n X^{n - 1} - (n - 1) σ_{1} X^{n - 1} + \dots}{X^{n} - σ_{1} X^{n - 1} + \dots},$

substituons

\frac{1}{T}

X

et chassons les dénominateurs en

T

$\sum_{i = 1}^{n} \frac{1}{1 - α_{iT}} = \frac{\sum_{i = 0}^{n - 1} (- 1)^{i} (n - i) σ_{i} T^{i}}{\sum_{i = 0}^{n} (- 1)^{i} σ_{i} T^{i}} = \frac{n - (n - 1) σ_{1} T + \dots}{1 - σ_{1} T + \dots} .$

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

$L = \sum_{i = 1}^{n} \frac{1}{1 - α_{i} T} = \sum_{i = 1}^{n} (\sum_{j \in ℕ} σ_{i}^{j} T^{j}) = \sum_{j \in ℕ} s_{j} T^{j} .$

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

$(\sum_{i = 0}^{n} (- 1)^{i} σ_{i} T^{i}) (\sum_{j \in ℕ} s_{j} T^{j}) = \sum_{i = 0}^{n - 1} (- 1)^{i} (n - i) σ_{i} T^{i}$

ou encore

(s_{0} + s_{1} T + s_{2} T^{2} \dots) (1 - σ_{1} T + \dots + (- 1)^{n} σ_{n} T^{n})

= = n - (n - 1) σ_{1} T + \dots + (- 1)^{n - 1} σ_{n - 1} T^{n - 1} .

Le coefficient de

T^{k}

dans le premier membre est

$\sum_{i = 0}^{min (k, n)} (- 1)^{i} σ_{is}_{k - i} .$

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}

\begin{matrix} s_{1} & = & σ_{1} \\ s_{2} & = & σ_{1}^{2} - 2 σ_{2} \\ s_{3} & = & σ_{1}^{3} - 3 σ_{1} σ_{2} + 3 σ_{3} \\ s_{4} & = & σ_{1}^{4} - 4 σ_{1}^{2} σ_{2} + 4 σ_{1} σ_{3} + 2 σ_{2}^{2} - 4 σ_{4} \end{matrix}

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^{4} - X^{3} - 2 X^{2} + 5 X - 1

a quatre racines dans

ℂ

α_{1} ≃ - 1.8072

α_{2} ≃ 0.2213

α_{3} ≃ 1.2929 - 0.9105 i

α_{4} = \bar{α_{3}} ≃ 1.2929 + 0.9105 i

. On a

\begin{matrix} σ_{1} & = & 1 \\ σ_{2} & = & - 2 \\ σ_{3} & = & - 5 \\ σ_{4} & = & - 1 \end{matrix}

On en déduit les sommes de puissances successives

$\begin{matrix} s_{1} & = & σ_{1} & = & σ_{1} & = & 1 \\ s_{2} & = & σ_{1} s_{1} - 2 σ_{2} & = & s_{1} + 4 & = & 5 \\ s_{3} & = & σ_{1} s_{2} - σ_{2} s_{1} + 3 σ_{3} & = & s_{2} + 2 s_{1} - 15 & = & - 8 \\ s_{4} & = & σ_{1} s_{3} - σ_{2} s_{2} + σ_{3} s_{1} - 4 σ_{4} & = & s_{3} + 2 s_{2} - 5 s_{1} + 4 & = & 1 \\ s_{5} & = & σ_{1} s_{4} - σ_{2} s_{3} + σ_{3} s_{2} - σ_{4} s_{1} & = & s_{4} + 2 s_{3} - 5 s_{2} + s_{1} & = & - 39 \\ s_{6} & = & σ_{1} s_{5} - σ_{2} s_{4} + σ_{3} s_{3} - σ_{4} s_{2} & = & s_{5} + 2 s_{4} - 5 s_{3} + s_{2} & = & 8 \end{matrix}$

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, CFAI,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.