Prérequis
Résumé
Ce chapitre est plutôt un chapitre de découverte, dans lequel nous nous attaquerons à quelques notions d'analyse discrète et les appliquerons à des problèmes de polynômes. Pour ceux ayant déjà vu les définitions usuelles de dérivées et intégrales, nous ferons des parallèles entre les résultats usuels et discrets. Dans le cas contraire, vous pouvez voir l'analyse discrète comme un prototype de l'analyse "infinitésimale", qui pourrait donc vous aider par la suite.
Ce chapitre a été
écrit par C. Bodart et
mis en ligne le 23 février 2020.
1. Dérivée discrète
Définition
Tout d'abord, rappelons la définition de fonction dérivée de $f\colon\mathbb R\to\mathbb R$ : on définit une nouvelle fonction $f'\colon\mathbb R\to \mathbb R$ via
$$f'(x) := \lim_{h\to 0} \frac{f(x+h)-f(x)}h$$ (pour peu que cette limite existe). Dans le cadre de l'analyse discrète, on veut se débarrasser de ce concept barbare de limite, et vous verrez que tout se passera bien (enfin... vous verrez).
Pour faciliter les énoncés, et car nous n'aurons pas besoin de plus, nous allons nous restreindre au cas des fonctions $f \colon \mathbb Z \to \mathbb R$ définies sur les entiers. Sachez toutefois que tout est facilement généralisable au cas des fonctions $f \colon \mathbb R \to \mathbb R$.
Par exemple, si $h = 2$ et $f(x) = 3^x$, alors
$$(\Delta_2f)(x) = \frac12\cdot\big(3^{x+2}-3^x\big) = 4\cdot 3^x.$$ Une fois cette construction faite, on peut itérer et définir les $2^\text{ème}$, $3^\text{ème}$... dérivées discrètes par récurrence : $\Delta_h^{n+1}f = \Delta_h(\Delta_h^nf)$. Par exemple, pour $h = 1$, la deuxième dérivée discrète d'une fonction $f$ est
$$\begin{align*}
(\Delta_1^2f)(x)
& = (\Delta_1 f)(x+1) - (\Delta_1 f)(x) \\
& = \big( f(x+2)-f(x+1)\big) - \big(f(x+1)-f(x)\big) \\
& = f(x+2) - 2f(x+1) + f(x)
\end{align*}$$
Résultat
Plus généralement, on a
$$\Delta_h^nf(x) = \frac{1}{h^n} \sum_{i=0}^n (-1)^{n-i} \cdot C^i_n \cdot f(x+ih).$$
Idée de démonstration
Comme le coefficient binomial $C^i_n$ le laisse penser, on peut prouver l'égalité par récurrence à l'aide de la relation de Pascal.
Le cas des polynômes
Comme pour la dérivée usuelle, la dérivée discrète d'un polynôme est elle-même un polynôme. On a même un peu plus, comme le montre le résultat suivant. Cela nous donne donc un nouvel outil pour jouer avec les polynômes.
Proposition
Si $P$ est un polynôme de degré $n$ et de coefficient dominant $a_n$ alors $\Delta_h P$ est un polynôme de degré $n-1$ et de coefficient dominant $n \cdot a_n$.
Démonstration
Notons $P(x)=\sum_{i=0}^na_ix^i$. On peut alors calculer (en utilisant la formule du binôme de Newton)
$$\begin{align}
(\Delta_h P)(x)
& = \sum_{i=0}^n \frac{a_i}h \big((x+h)^i-x^i\big) \\
& = \sum_{i=0}^n \frac{a_i}h \left(\sum_{j=0}^{i}\, C^j_i \cdot h^{i-j} \cdot x^j - x^i \right) \\
& = \sum_{i=0}^n \frac{a_i}h \sum_{j=0}^{i-1}\, C^j_i \cdot h^{i-j} \cdot x^j.
\end{align}$$ En regardant attentivement, on se convainc qu'il s'agit bien d'un polynôme. De plus, le terme de plus haut degré est obtenu pour $i=n$ et $j=n-1$, il s'agit plus précisément de
$$\frac{a_n}h \cdot C^{n-1}_n \cdot h^1 \cdot x^{n-1} = n \cdot a_n \cdot x^{n-1}$$ comme attendu.
Nous sommes maintenant déjà en mesure de présenter une première application ! Le problème suivant possède en effet une solution simple utilisant ces notions.
Solution
Définissons le polynôme $P(x) = (x+k_1)(x+k_2)\ldots(x+k_n)$. L'énoncé indique que $P(x)$ est divisible par $k_1 k_2 \ldots k_n$ pour tout $x \in \mathbb N$.
- D'une part, la formule
$$(\Delta^nP)(x) = \sum_{i=0}^n (-1)^{n-i} \cdot C^i_n \cdot P(x+i)$$ permet d'affirmer que $k_1k_2\ldots k_n \mid (\Delta^nP)(x)$ pour tout $x \in \mathbb N$ (car tous les $P(x+i)$ sont divisibles par $k_1k_2 \ldots k_n$).
- D'autre part, $P$ étant initialement unitaire (i.e. son coefficient dominant est $1$), la dernière proposition appliquée $n$ fois nous donne $(\Delta^n P)(x) = n!$. En effet, il doit s'agir d'un polynôme de degré $n - n = 0$ et de coefficient dominant $n \cdot (n-1) \cdot \ldots \cdot 1 \cdot 1 = n!$.
On obtient dès lors $k_1k_2 \ldots k_n \mid n!$. On peut maintenant conclure : l'hypothèse
$$0 < k_1 < k_2 < \ldots < k_n$$ implique que $k_i \ge i$ pour tout $i$ puis $k_1k_2\ldots k_n\ge n!$. Le naturel $n!$ ne possédant pas beaucoup de diviseurs supérieurs à lui-même, on se situe dans le cas d'égalité $k_1k_2\ldots k_n=n!$ c'est-à-dire $k_i=i$ pour tout $i$.
2. Intégration
À partir de cette section, nous allons toujours prendre $h = 1$. Cela facilitera une nouvelle fois les énoncés.
Motivation
Nous motivons la notion d'intégration en nous intéressant au problème suivant.
Solution
On remarque que
$$\frac1{i(i+1)} = \frac1i - \frac1{i+1}. \quad (*)$$ On peut dès lors réécrire la somme comme
$$S = \left(\frac11-\frac12\right)+\left(\frac12-\frac13\right)+\ldots + \left(\frac1{99}-\frac1{100}\right)$$ dans laquelle la majorité des termes se simplifient. Il nous reste uniquement $S = \frac11-\frac1{100}=\frac{99}{100}$.
On pourrait retenir de cette preuve la seule relation $(*)$, ou bien l'idée des sommes télescopiques (honnêtement, c'est la seule idée de cette section, on aurait pu l'appeler "Intégration, ou l'Art des sommes télescopiques"), mais on va surtout noter que l'égalité $f(x) = \frac{1}{x(x+1)} = \frac{1}{x}-\frac{1}{x+1}$ n'est rien d'autre que $(\Delta F)(x)$ où $F(x) = - \frac{1}{x}$. (Ne nous tracassons pas de $x = 0$ ou $x = -1$ pour le moment.) Il apparaît alors dans la solution de ce problème que $f(1) + f(2) + \ldots + f(99)$ est égal à $F(100) - F(1)$. Est-ce un simple hasard ? Ou est-ce dû au fait que $f = \Delta F$ ? Vous devinez sans doute la réponse...
Primitive discrète
Avant de voir cela plus en détails, donnons une nouvelle définition. Étant données deux fonctions $f \colon \mathbb Z \to \mathbb R$ et $F \colon \mathbb Z \to \mathbb R$ telles que $\Delta F = f$, on a déjà vu que $f$ était appelée la dérivée discrète de $F$. Dans l'autre sens, on dit aussi que $F$ est une
primitive (discrète) de $f$.
Lorsqu'on est en présence d'une fonction $f \colon \mathbb Z \to \mathbb R$, en trouver une primitive $F$ peut souvent se révéler utile.
Dans le cadre de l'analyse classique, et pour ceux qui connaissent, on sait que les primitives d'une fonction $f$ sont de la forme $F_0+C$ où
$$F_0(x) = \int_0^x f(u)\,\mathrm du$$ et $C$ est une constante. Pour les dérivées discrètes, les primitives ont une forme similaire.
Formule pour les primitives
Soit $f \colon \mathbb Z \to \mathbb R$ une fonction. Alors les primitives de $f$ sont de la forme $F = F_0+C$ où
$$F_0(x) = \left\{ \begin{array}{cl}
\hspace{4mm} \displaystyle\sum_{i=0}^{x-1} f(i) & \text{ pour $x \in \mathbb{Z}_{> 0}$ } \\
0 & \text{ pour $x = 0$}\\
- \displaystyle\sum_{i=x}^{-1} f(i) & \text{ pour $x \in \mathbb{Z}_{< 0}$ }
\end{array} \right.$$ et $C \in \mathbb R$ est une constante.
Démonstration
Pour se faire une meilleure intuition de $F_0$, donnons ses valeurs autour de $0$ :
\begin{align}
F_0(-3) &= - f(-3) - f(-2) - f(-1)\\
F_0(-2) &= - f(-2) - f(-1)\\
F_0(-1) &= - f(-1)\\
F_0(0) &= 0\\
F_0(1) &= f(0)\\
F_0(2) &= f(0) + f(1)\\
F_0(3) &= f(0) + f(1) + f(2)
\end{align} De là, on voit aisément que $\Delta F_0 = f$. En effet, $(\Delta F_0)(x) = F_0(x+1) - F_0(x)$ et on observe bien que $F_0(x+1)$ est toujours obtenu de $F_0(x)$ en lui ajoutant le terme $f(x)$.
On a tout aussi rapidement que $\Delta(F_0+C) = f$, puisque
$$\Delta(F_0+C)(x) = \big(F_0(x+1) + C\big) - \big(F_0(x) + C\big) = F_0(x+1) - F_0(x) = (\Delta F_0)(x) = f(x).$$
Réciproquement, considérons $F$ une primitive de $f$ et notons $C = F(0)$. Le fait que $F$ est primitive de $f$ implique que $F(x+1) - F(x) = f(x)$ pour tout $x \in \mathbb Z$, et on peut donc trouver récursivement que
$$\begin{align}
F(1) &= F(0)+f(0) = C + f(0)\\
F(2) &= F(1)+f(1) = C + f(0)+f(1)\\
& \cdots
\end{align}$$ De la même manière dans les nombres négatifs, on a
$$\begin{align}
F(-1) &= F(0) - f(-1) = C - f(-1)\\
F(-2) &= F(-1) - f(-2) = C - f(-2) - f(-1)\\
& \cdots
\end{align}$$ On voit que $F$ est égal à $F_0 + C$, ce qui montre que toutes les primitives de $f$ sont bien de cette forme.
Dans la formule du résultat précédent, nous avons dû péniblement écrire des formules différentes selon que $x$ est supérieur, égal ou inférieur à $0$. Afin d'éviter cette discussion de cas à l'avenir, nous introduisons la convention suivante :
Cela peut paraître un peu barbare mais c'est en fait la façon naturelle de définir $\sum_{i=a}^{b-1} f(i)$ lorsque $b \leq a$ si l'on souhaite garder toutes les bonnes propriétés de la somme. Par exemple, avec cette convention on a
$$\sum_{i=a}^{b-1} f(i) + \sum_{i=b}^{c-1}f(i) = \sum_{i=a}^{c-1}f(i)$$ quel que soit l'ordre dans lequel les entiers $a, b, c$ se trouvent.
Théorème fondamental
En analogie avec le théorème fondamental de l'analyse
$$\int_a^b f(u)\,\mathrm du = F(b)-F(a) \quad ( =: [F(x)]_a^b),$$ on a du côté discret le théorème suivant.
Théorème (fondamental de l'analyse discrète)
Soit $f \colon \mathbb Z \to \mathbb R$ et $F \colon \mathbb Z \to \mathbb R$ une primitive de $f$. Nous avons l'égalité
$$\sum_{i=a}^{b-1} f(i) = F(b) - F(a) \quad (=: [F(x)]_a^b).$$
Démonstration
Cela découle directement de la formule que nous avons démontrée pour les primitives de $f$.
Au début de cette section nous avons vu pour un $f$ bien particulier que $f(1) + \ldots + f(99)$ était égal à $F(100) - F(1)$. On voit donc maintenant que ce n'était pas un hasard et que cette formule est vraie quelle que soit la fonction $f$ de départ.
Application
Passons maintenant à une autre application.
Solution
Commençons par calculer
$$\begin{align*}
\Delta P(m) & = P(m+1) - P(m) \\
\Delta\!^2 P(m) & = P(m+2) - 2P(m+1) + P(m) \\
\Delta\!^3 P(m) & = P(m+3) - 3P(m+2) + 3 P(m+1) - P(m).
\end{align*}$$ Par hypothèse, ces trois valeurs sont entières. De plus, vu que $P(x)$ est de degré $3$, sa troisième dérivée $\Delta^3 P(x)$ est de degré $0$, c'est-à-dire constante. Il existe donc $k \in \mathbb Z$ tel que $\Delta^3P(m) = k$ pour tout $m \in \mathbb Z$.
À partir de $\Delta^3 P$, on peut maintenant reconstruire $P$ en utilisant à plusieurs reprises le théorème fondamental de l'analyse discrète. Tout d'abord
$$\Delta^2P(n) = \Delta^2P(m) + \sum_{i=m}^{n-1} k.$$ On a donc $\Delta^2P(n) \in \mathbb Z$ pour tout $n \in \mathbb Z$. On peut ensuite recommencer :
$$\Delta P(n) = \Delta P(m) + \sum_{i=m}^{n-1} \Delta^2P(i) \in \mathbb Z$$ et finalement
$$P(n) = P(m) + \sum_{i=m}^{n-1} \Delta P(i) \in \mathbb Z$$ comme voulu.
3. Polynômes de Pochhammer
Tout cela est bien sympathique mais si l'on ne peut pas calculer
explicitement de primitives, ça ne nous avance pas fort. Comment pourrait-on calculer facilement les dérivées et primitives d'un polynôme ? Les deux sections suivantes ont pour but de répondre à cette question. On commence par examiner pourquoi ces opérations sont si simples avec la dérivée usuelle :
Lorsqu'on dérive $P(x)=a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$, on obtient
$$P'(x) = n a_n x^{n-1} + (n-1) a_{n-1} x^{n-2} + \ldots + 2 a_2 x + a_1$$ et similairement ses primitives sont
$$\int P(u) \,\mathrm du = \frac{a_n}{n+1} x^{n+1} + \frac{a_{n-1}} n x^n + \ldots + \frac{a_1}{2} x^2 + a_0 x + C.$$ Ces formules sympathiques viennent de "polynômes élémentaires" dont les dérivées sont elles-même jolies : on peut construire tout polynôme à base de polynômes de la forme $x^n$, et la dérivée de chaque $x^n$ est simplement $n x^{n-1}$.
Une nouvelle base
Dans le cas discret, le polynôme $x^n$ a pour dérivée $(x+1)^n - x^n$, ce qui est moins sympathique. (Comme vous l'aurez remarqué, dans cette section la sympathie des polynômes est souvent remise en question.) Pour cette raison on va partir d'une autre base de polynômes :
Ainsi, la liste commence par
\begin{align*}
(x)_0 & = 1 \\
(x)_1 & = x \\
(x)_2 & = x(x-1) \\
(x)_3 & = x(x-1)(x-2)
\end{align*}Comme annoncé, on a une jolie expression pour leurs dérivées :
Proposition (Relation de Pascal 2.0)
Les polynômes de Pochhammer vérifient la relation
$$\Delta (x)_n = n \cdot (x)_{n-1}.$$
Démonstration
Il s'agit d'un simple calcul :
$$\begin{align*}
\Delta (x)_n
& = (x+1)_n - (x)_n \\
& = (x+1)x\ldots(x-n+2) - x(x-1)\ldots(x-n+1) \\
& = \big((x+1)-(x-n+1)\big) \cdot x(x-1)\ldots (x-n+2) \\
& = n \cdot (x)_{n-1}
\end{align*}$$
Ainsi, si l'on vous donne un polynôme sous la forme $P(x)=b_n(x)_n + b_{n-1}(x)_{n-1}+\ldots+b_1(x)_1+b_0$, vous pourrez calculer sa dérivée
$$\Delta P(x) = nb_n(x)_{n-1} + (n-1)b_{n-1}(x)_{n-2} + \ldots + 2b_2(x)_1+b_1$$ tandis que ses primitives seront
$$\frac{b_n}{n+1}(x)_{n+1}+\frac{b_{n-1}}n(x)_n + \ldots + \frac{b_1}2(x)_2+b_0(x)_1 + C.$$
Comment changer de base ?
On pourrait encore objecter que $P(x)$ ne nous est jamais donné sous cette forme... Il faudrait donc trouver une méthode permettant de passer d'une écriture à l'autre. La première méthode part de l'observation que les $(x)_n$ sont unitaires et de degrés distincts, on peut donc choisir $n=\deg P$ ainsi que $q_n$ son coefficient dominant, puis soustraire $P(x)-q_n\cdot (x)_n$ afin d'obtenir un reste de degré inférieur (puis itérer). En équations,
$$\begin{eqnarray}
P(x) \;\, & - & \;\; q_n\cdot (x)_n & = & r_{n-1}(x) \\
r_{n-1}(x) \; & - & q_{n-1}\cdot (x)_{n-1} & = & r_{n-2}(x) \\
& & & \;\;\vdots & \\
r_1(x) \; & - & \;\; q_1\cdot (x)_1 & = & r_0(x) \\
r_0(x) \; & - & \;\; q_0\cdot (x)_0 & = & 0
\end{eqnarray}$$ afin d'obtenir $P(x)=q_n(x)_n+q_{n-1}(x)_{n-1}+\ldots+q_1(x)_1+q_0$.
Par exemple, pour $P(x)=x^3$,
$$\begin{eqnarray}
x^3 \hspace{7mm} & - & \; (x)_3 & = & 3x^2 - 2x \\
(3x^2 - 2x) \;& - & 3(x)_2 & = & \hspace{8mm} x \\
x \hspace{9mm} & - & \; (x)_1 & = & \hspace{8mm} 0
\end{eqnarray}$$ et donc $x^3 = (x)_3+3(x)_2+(x)_1$.
Une autre manière d'obtenir les coefficients d'un polynôme dans notre nouvelle base provient de la formule suivante :
Formule de Taylor
Si $P$ est un polynôme de degré $n$ alors
$$P(x) = \sum_{i=0}^n \frac{\Delta^i P(0)}{i!} \cdot (x)_i$$ (où bien sûr $\Delta^0 P=P$). Plus généralement, on a
$$P(x) = \sum_{i=0}^n \frac{\Delta^i P(a)}{i!} \cdot (x-a)_i$$
Démonstration
La preuve est identique à
celle de la formule usuelle, présentée dans un chapitre précédent.
Ceci nous donne un autre algorithme pour obtenir les coefficients d'un polynôme dans la base des polynômes de Pochhammer. Nous l'expliquons une nouvelle fois sur l'exemple de $P(x) = x^3$.
- On va construire un triangle de coefficients, en commençant par remplir la première ligne avec $P(0), P(1), \ldots, P(n)$ :
$$\begin{array}{c}
0 & & 1 & & 8 & & 27 \; \\
& \,*\, & & \,*\, & & \,*\, & \\
& & * & & * & & \\
& & & * & & &
\end{array}$$
- Itérativement, on remplace chaque entrée par la différence entre les deux entrées directement supérieures, spécifiquement celle de droite moins celle de gauche
$$\begin{array}{c}
\color\red0 & & 1 & & 8 & & 27 \\
& \color\red1 & & 7 & & 19 & \\
& & \color\red6 & & 12 & & \\
& & & \color\red6 & & &
\end{array}$$
- Finalement, les $\Delta^iP(0)$ sont obtenus en lisant la diagonale descendante (en rouge ci-dessus), en commençant par $\Delta^0P(0)=P(0)$. On obtient les coefficients en divisant par $i!$.
$$\begin{align} x^3 & = \frac{\color\red0}{0!}\cdot (x)_0 + \frac{\color\red1}{1!}\cdot (x)_1 + \frac{\color\red6}{2!} \cdot (x)_2 + \frac{\color\red6}{3!}\cdot (x)_3 \\ & = (x)_3 + 3(x)_2 + (x)_1. \end{align}$$
4. Nombres de Stirling
Et maintenant le
grand final. On donne une formule directe pour passer de $\sum_{i=0}^n a_ix^i$ à $\sum_{i=0}^n b_i(x)_i$.
Un peu de combinatoire
On commence par introduire les nombres de Stirling :
Par exemple, les partitions de $\{1,2,3,4\}$ en $2$ parties sont
$$\{1\}\sqcup\{2,3,4\}, \qquad \{2\}\sqcup \{1,3,4\}, \qquad \{3\}\sqcup \{1,2,4\}, \qquad \{4\}\sqcup\{1,2,3\}$$ $$\{1,2\}\sqcup\{3,4\}, \qquad \{1,3\}\sqcup \{2,4\} \qquad\text{et}\qquad \{1,4\}\sqcup \{2,3\}$$ et ainsi $\color{red}{\left\{ {4\atop 2 }\right\}=7}$. Voici quelques valeurs supplémentaires :
$$\begin{array}{c|c|c|c|c|c|c|c|c}
n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
0 & 1 & & & & & & & \\
1 & 0 & 1 & & & & & & \\
2 & 0 & 1 & 1 & & & & & \\
3 & 0 & 1 & 3 & 1 & & & & \\
4 & 0 & 1 & \color{red}7 & 6 & 1 & & & \\
5 & 0 & 1 & 15 & 25 & 10 & 1 & & \\
6 & 0 & 1 & 31 & 90 & 65 & 15 & 1 & \\
7 & 0 & 1 & 63 & 301 & 350 & 140 & 21 & 1
\end{array}$$ Plus efficacement, on peut les calculer via la formule suivante :
Indice
Compter les surjections $f \colon \{1,2,\ldots,n\} \to \{1,2,\ldots,k\}$ de deux manières différentes. Le $(-1)^{\ldots}$ n'est pas innocent.
Changement de base
Je me permets maintenant de vous rappeler que vous lisez un chapitre d'algèbre... À quoi servent tous ces coefficients combinatoires ? Et bien le lecteur attentif aura remarqué que
$$\sum_{i=0}^k (-1)^{k-i} \cdot C_k^i \cdot i^n = \Delta^kP(0)$$ pour $P(x)=x^n$. Autrement dit, le nombre $\left\{ {n\atop k }\right\}$ est exactement le coefficient de degré $k$ dans le développement de Taylor de $x^n$. Il suit donc :
Formule de changement de base
Pour tout naturel $n$, on a
$$x^n = \sum_{i=0}^n \left\{ {n\atop i }\right\} \cdot (x)_i.$$
Application
On conclut avec un problème classique :
Solution
Étant donnée une primitive $F$ de $f(x)=x^3$, le théorème fondamental nous offrirait
$$\sum_{i=1}^{m} f(i) = F(m+1) - F(1).$$ D'un autre côté, la formule de changement de base nous donne
$$x^3 = (x)_3 + 3(x)_2 + (x)_1$$ donc une telle primitive est donnée par
$$\begin{align*}
F(x)
& = \frac14 (x)_4 + (x)_3 + \frac12 (x)_2 \\
& = \frac{x(x-1)}4 \cdot \big((x-2)(x-3) + 4 (x-2) + 2\big) \\
& = \left(\frac{x(x-1)}2\right)^2
\end{align*}$$ On observe que $F(1)=0$ et finalement
$$1^3+2^3+\ldots+m^3 = \left(\frac{m(m+1)}2\right)^2.$$
Plus généralement, la même méthode donne
Proposition (Polynômes de Faulhaber)
Pour $n>0$ naturel, on a l'égalité
$$1^n + 2^n + \ldots + m^n = \sum_{j=1}^n \frac1{j+1} \left\{ {n\atop j }\right\} (m+1)_{j+1}.$$
(Bien qu'elle puisse sembler plus compliquée, le nombre de termes de la formule de droite ne dépend pas de $m$, elle a donc ses avantages.)