Le calcul différentiel discret

Sur une droite continue, la dérivée compare des valeurs infiniment proches. Sur la grille des entiers, il existe une autre comparaison naturelle : regarder ce qui change lorsqu'on avance exactement d'un pas. Ce devoir propose de construire, avec les outils de MPSI, un véritable petit calcul différentiel adapté à cette situation. On découvrira qu'il possède ses propres « monômes », sa formule de Taylor et ses primitives — et qu'il explique de façon structurelle pourquoi les sommes de puissances sont encore des polynômes.

Dans tout le problème, on travaille dans $\mathbb R[X]$. Pour tout polynôme $P$, on définit sa différence finie en avant de pas $1$ par

$$\Delta P(X)=P(X+1)-P(X).$$

Pour $k\in\mathbb N$, on note $\Delta^0=\operatorname{Id}$ et, pour $k\geqslant1$, $\Delta^k=\Delta\circ\Delta^{k-1}$.

La Methodus differentialis de Newton, imprimée en 1711, est l'une des sources historiques importantes de l'interpolation par différences finies. Le présent problème n'en reproduit pas le texte : il reconstruit, avec des notations modernes et un pas fixé à $1$, les mécanismes algébriques qui conduisent à la formule de Newton et à la sommation discrète.

I — Une dérivée sans limite ?

1. Calculer $\Delta P$ lorsque $P$ vaut successivement $1$, $X$, $X^2$ puis $X^3$. Comparer les résultats avec les dérivées usuelles de ces quatre polynômes.

2. Soient $P,Q\in\mathbb R[X]$ et $\lambda,\mu\in\mathbb R$.

(a) Montrer que $\Delta$ est un endomorphisme de $\mathbb R[X]$.

(b) Soit $P$ non constant, de degré $d\geqslant1$ et de coefficient dominant $a_d$. Déterminer le degré et le coefficient dominant de $\Delta P$.

(c) Déterminer le noyau de $\Delta$.

3. La dérivation vérifie la règle de Leibniz.

(a) Déterminer une formule pour $\Delta(PQ)$ faisant intervenir $P$, $Q$, $\Delta P$ et $\Delta Q$.

(b) En regroupant autrement les termes de la définition de $\Delta(PQ)$, obtenir une seconde écriture utile. Comparer ces formules à la règle de Leibniz et préciser ce qui empêche $\Delta$ d'être une dérivation au sens usuel.

4. Pour $n\in\mathbb N$, on note $E_n=\mathbb R_n[X]$ l'espace vectoriel des polynômes de degré au plus $n$.

(a) Montrer que $\Delta$ induit un endomorphisme de $E_n$.

(b) Pour $n\geqslant1$, déterminer $\operatorname{Im}\Delta$ dans $E_n$ à l'aide du théorème du rang.

(c) Déterminer une puissance de $\Delta$ qui est nulle sur $E_n$. Si $P\in E_n$ a pour coefficient de $X^n$ le réel $a_n$, déterminer $\Delta^nP$.

L'opérateur $\Delta$ abaisse donc le degré comme une dérivation. Mais, dans la base usuelle $(1,X,\ldots,X^n)$, les formules deviennent vite chargées. Pour la dérivation, les puissances sont naturellement adaptées. Cherchons les « bons monômes » de $\Delta$.

II — Les bons monômes du monde discret

Pour $k\in\mathbb N$, on définit le polynôme

$$B_0(X)=1,$$

et, pour $k\geqslant1$,

$$B_k(X)=\frac{X(X-1)\cdots(X-k+1)}{k!}.$$

On pourra aussi écrire $\binom{X}{k}=B_k(X)$ : pour une variable réelle, cette notation désigne donc un polynôme et non un nombre de choix combinatoires. Lorsque $m\in\mathbb N$, sa valeur $B_k(m)=\binom{m}{k}$ coïncide avec le coefficient binomial usuel ; elle vaut automatiquement $0$ lorsque $k>m$.

5. Soit $n\in\mathbb N$.

(a) Déterminer le degré et le coefficient dominant de $B_k$.

(b) En déduire que $(B_0,B_1,\ldots,B_n)$ est une base de $E_n$.

(a) Calculer $\Delta B_0$, $\Delta B_1$, $\Delta B_2$ et $\Delta B_3$. Quelle régularité apparaît ?

(b) Formuler puis démontrer la relation générale suggérée par ces calculs.

7. Soient $j,k\in\mathbb N$.

(a) Déterminer $\Delta^jB_k$ en distinguant les positions relatives de $j$ et $k$.

(b) Écrire la matrice de l'endomorphisme $\Delta$ de $E_n$ dans la base $(B_0,\ldots,B_n)$.

(c) Comparer cette matrice à celle de la dérivation dans la base

$$\left(1,X,\frac{X^2}{2!},\ldots,\frac{X^n}{n!}\right).$$

8. Réécrire la relation obtenue à la question 6 sous une forme reliant $B_k(X+1)$ à des polynômes de la famille $(B_j)$. Que devient cette identité lorsqu'on l'évalue en un entier naturel ? Identifier la relation combinatoire obtenue.

La base $(B_k)$ transforme donc $\Delta$ en un simple décalage. C'est exactement la situation qui permet, pour la dérivation usuelle, d'obtenir la formule de Taylor. On va maintenant construire son analogue discret.

III — Une formule de Taylor sur une grille

9. On étend ici la notation $\Delta$ à toute fonction $f:\mathbb R\to\mathbb R$ par

$$\Delta f(x)=f(x+1)-f(x).$$

(a) Exprimer $\Delta^2f(x)$ puis $\Delta^3f(x)$ uniquement à l'aide de valeurs de $f$.

(b) Observer les coefficients obtenus. Conjecturer une formule générale exprimant $\Delta^kf(x)$ à partir de $f(x),f(x+1),\ldots,f(x+k)$. La formule proposée devra aussi être cohérente pour $k=0$.

(c) Démontrer la formule conjecturée.

10. Soit $P\in E_n$. Comme $(B_0,\ldots,B_n)$ est une base, il existe d'uniques réels $a_0,\ldots,a_n$ tels que

$$P=\sum_{k=0}^{n}a_kB_k.$$

(a) Pour $j\in\{0,\ldots,n\}$, exprimer $\Delta^jP(0)$ en fonction de $a_0,\ldots,a_n$.

(b) En déduire les coordonnées de $P$ dans la base $(B_0,\ldots,B_n)$ à partir de ses différences successives en $0$. Écrire la formule de reconstruction obtenue.

(c) Mettre cette formule en parallèle avec la formule de Taylor polynomiale en $0$. Quel rôle jouent ici les $B_k$ ?

(a) À l'aide de la question 9, exprimer les coordonnées obtenues à la question 10 uniquement à partir des valeurs $P(0),P(1),\ldots$ nécessaires.

(b) En déduire qu'un polynôme de degré au plus $n$ est entièrement déterminé par ses $n+1$ valeurs

$$P(0),P(1),\ldots,P(n).$$

12. On considère les valeurs

$$P(0)=2,\qquad P(1)=3,\qquad P(2)=8,\qquad P(3)=23,$$

et l'on sait que $P$ est de degré au plus $3$.

(a) Construire la table des différences successives associée à ces quatre valeurs.

(b) En déduire $P$ d'abord dans la base $(B_0,B_1,B_2,B_3)$, puis sous forme développée.

Cette écriture n'est pas seulement un outil d'interpolation. Elle rend également très simple l'opération inverse de $\Delta$.

IV — Primitives discrètes et sommes exactes

On appelle primitive discrète d'un polynôme $P$ tout polynôme $Q$ tel que

$$\Delta Q=P.$$

13. Soit $P\in\mathbb R[X]$, écrit sous la forme

$$P=\sum_{k=0}^{n}a_kB_k.$$

(a) Construire une primitive discrète de $P$.

(b) Montrer que deux primitives discrètes d'un même polynôme diffèrent d'une constante.

(c) Si $P$ est non nul de degré $d$, déterminer le degré de ses primitives discrètes et relier leur coefficient dominant à celui de $P$.

14. Soient $a,b\in\mathbb Z$ avec $a<b$, et soit $Q$ une primitive discrète de $P$.

(a) Exprimer la somme

$$\sum_{m=a}^{b-1}P(m)$$

uniquement à l'aide de $Q$ et des bornes $a,b$.

(b) Comparer la formule obtenue au théorème fondamental de l'analyse pour une primitive usuelle.

15. Pour $k,n\in\mathbb N$, calculer exactement

$$\sum_{m=0}^{n-1}B_k(m).$$

Simplifier le résultat sous une forme combinatoire familière.

(a) À l'aide de la question 10, déterminer les coordonnées de $X$, $X^2$ et $X^3$ dans la base $(B_k)$.

(b) En déduire, pour tout $n\in\mathbb N$, les trois sommes

$$\sum_{m=0}^{n-1}m, \qquad \sum_{m=0}^{n-1}m^2, \qquad \sum_{m=0}^{n-1}m^3.$$

17. Soit $P$ un polynôme non nul de degré $d$. Montrer que la fonction

$$n\longmapsto \sum_{m=0}^{n-1}P(m)$$

coïncide sur $\mathbb N$ avec un polynôme. Déterminer son degré et son coefficient dominant en fonction de ceux de $P$.

Il reste une dernière question : l'annulation des différences successives est-elle seulement une conséquence du caractère polynomial, ou le caractérise-t-elle ?

18. Soit $d\in\mathbb N$. Pour une suite réelle $u=(u_n)_{n\geqslant0}$, on définit

$$(\Delta u)_n=u_{n+1}-u_n,$$

puis les différences itérées de la même manière.

(a) Si $u_n=P(n)$ pour un polynôme $P$ de degré au plus $d$, que peut-on dire de $\Delta^{d+1}u$ ?

(b) Réciproquement, supposons $\Delta^{d+1}u=0$. En vous inspirant de la formule de reconstruction de la partie III, construire un polynôme $R\in\mathbb R_d[X]$ à partir des différences initiales de $u$, puis démontrer que

$$u_n=R(n)$$

pour tout $n\in\mathbb N$.

(c) Formuler sous forme d'équivalence le critère structurel obtenu dans les deux questions précédentes.

Vous avez ainsi construit un calcul différentiel adapté à la grille des entiers. La base $(B_k)$ y joue le rôle des monômes divisés, la reconstruction de Newton remplace Taylor, et les primitives discrètes transforment les sommes finies en différences de valeurs aux extrémités. Surtout, le dernier résultat montre que l'annulation d'un nombre fini de différences ne constitue pas seulement une propriété des suites polynomiales : elle les caractérise.