Le calcul différentiel discret

I — Un opérateur qui abaisse le degré

1. On obtient

$$\Delta 1=0, \qquad \Delta X=1,$$ $$\Delta X^2=(X+1)^2-X^2=2X+1,$$

et

$$\Delta X^3=(X+1)^3-X^3=3X^2+3X+1.$$

Comme la dérivation usuelle, $\Delta$ annule les constantes et abaisse le degré des polynômes non constants d’une unité. En revanche, des termes de degré inférieur subsistent : par exemple

$$(X^2)'=2X \qquad\text{alors que}\qquad \Delta X^2=2X+1.$$

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

$$\begin{aligned} \Delta(\lambda P+\mu Q)(X) &=(\lambda P+\mu Q)(X+1)-(\lambda P+\mu Q)(X)\\ &=\lambda\Delta P(X)+\mu\Delta Q(X). \end{aligned}$$

De plus $\Delta P$ est encore un polynôme. Ainsi $\Delta$ est un endomorphisme de $\mathbb R[X]$.

Soit maintenant

$$P(X)=a_dX^d+\text{termes de degré inférieur}, \qquad d\geqslant1, \qquad a_d\neq0.$$

La formule du binôme donne

$$(X+1)^d-X^d=dX^{d-1}+\text{termes de degré au plus }d-2.$$

Les termes de degré inférieur de $P$ ne peuvent pas contribuer au coefficient de $X^{d-1}$ dans $\Delta P$. Par conséquent

$$\boxed{\deg(\Delta P)=d-1}$$

et le coefficient dominant de $\Delta P$ vaut

$$\boxed{d\,a_d}.$$

Toutes les constantes appartiennent à $\ker\Delta$. Réciproquement, si $P$ n’est pas constant, alors $\Delta P$ a degré $\deg P-1$ et n’est donc pas nul. Ainsi

$$\boxed{\ker\Delta=\mathbb R}.$$

3. Si $P\in E_n$, alors $\Delta P\in E_n$ ; la restriction de $\Delta$ à $E_n$ est donc un endomorphisme.

Chaque application de $\Delta$ abaisse exactement d’une unité le degré tant que le polynôme obtenu n’est pas constant. Il en résulte que

$$\Delta^{n+1}=0 \quad\text{sur }E_n.$$

En revanche,

$$\Delta^n(X^n)=n!\neq0,$$

puisque les coefficients dominants sont successivement multipliés par

$$n,n-1,\ldots,1.$$

L’indice de nilpotence de $\Delta$ sur $E_n$ est donc

$$\boxed{n+1}.$$

Plus précisément, pour $0\leqslant k\leqslant n+1$, un polynôme $P\in E_n$ vérifie $\Delta^kP=0$ si et seulement si $\deg P<k$ — avec le cas $P=0$ inclus. Ainsi, avec la convention $E_{-1}=\{0\}$,

$$\boxed{\ker(\Delta^k)=E_{k-1}.}$$

Le théorème du rang donne alors

$$\dim\operatorname{Im}(\Delta^k) =(n+1)-k.$$

Par ailleurs, $\Delta^k$ abaisse le degré d’au plus $k$, donc

$$\operatorname{Im}(\Delta^k)\subset E_{n-k}.$$

Pour $0\leqslant k\leqslant n$, les deux espaces ont la même dimension $n-k+1$, d’où

$$\operatorname{Im}(\Delta^k)=E_{n-k}.$$

Pour $k=n+1$, l’image est nulle, ce qui correspond encore à la convention $E_{-1}=\{0\}$. Finalement,

$$\boxed{\operatorname{Im}(\Delta^k)=E_{n-k} \qquad(0\leqslant k\leqslant n+1).}$$

Enfin, si le coefficient de $X^n$ dans $P$ est $a_n$, alors après $n$ différences tous les termes de degré inférieur à $n$ ont disparu, tandis que le terme dominant fournit

$$\boxed{\Delta^nP=n!\,a_n.}$$

II — Une base adaptée aux différences finies

4. Pour $k\geqslant1$, le polynôme $B_k$ est de degré $k$ et de coefficient dominant $1/k!$. Les polynômes

$$B_0,B_1,\ldots,B_n$$

ont donc des degrés deux à deux distincts : ils sont linéairement indépendants. Comme $E_n$ est de dimension $n+1$,

$$\boxed{(B_0,\ldots,B_n)\text{ est une base de }E_n.}$$

Pour $k\geqslant1$,

$$\begin{aligned} B_k(X+1)-B_k(X) &=\frac{(X+1)X\cdots(X-k+2)-X(X-1)\cdots(X-k+1)}{k!}\\ &=\frac{X(X-1)\cdots(X-k+2)}{k!} \bigl((X+1)-(X-k+1)\bigr)\\ &=\frac{X(X-1)\cdots(X-k+2)}{(k-1)!}. \end{aligned}$$

Ainsi

$$\boxed{\Delta B_k=B_{k-1}\quad(k\geqslant1),}$$

et $\Delta B_0=0$.

La relation précédente se réécrit

$$B_k(X+1)=B_k(X)+B_{k-1}(X).$$

En $X=m\in\mathbb N$, elle devient

$$\boxed{ \binom{m+1}{k} = \binom{m}{k} + \binom{m}{k-1}},$$

qui est la relation de Pascal.

5. Dans la base $(B_0,\ldots,B_n)$,

$$\Delta B_0=0,\qquad \Delta B_1=B_0,\qquad\ldots,\qquad \Delta B_n=B_{n-1}.$$

La matrice de $\Delta$ est donc

$$\boxed{ \operatorname{Mat}(\Delta)= \begin{pmatrix} 0&1&0&\cdots&0\\ 0&0&1&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&0\\ 0&\cdots&0&0&1\\ 0&\cdots&\cdots&0&0 \end{pmatrix}.}$$

Si l’on pose

$$C_k=\frac{X^k}{k!},$$

alors

$$C_0'=0, \qquad C_k'=C_{k-1}\quad(k\geqslant1).$$

La dérivation possède donc exactement la même matrice dans la base $(C_0,\ldots,C_n)$.

Cette matrice rend immédiatement visibles les résultats de la question 3 : sa puissance $k$ décale de $k$ positions, son noyau est engendré par les $k$ premiers vecteurs de base, son image par les $n+1-k$ premiers, et sa première puissance nulle est la puissance $n+1$.

III — Reconstruire un polynôme sur une grille

6. On calcule d’abord

$$\Delta^2f(x) =f(x+2)-2f(x+1)+f(x),$$

puis

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

Les coefficients suggèrent la formule

$$\boxed{ \Delta^kf(x) = \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}f(x+j).}$$

Pour $k=0$, elle redonne bien $f(x)$.

Démontrons-la par récurrence. Supposons-la vraie à l’ordre $k$. Alors

$$\begin{aligned} \Delta^{k+1}f(x) &=\Delta^kf(x+1)-\Delta^kf(x)\\ &=\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}f(x+j+1) -\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}f(x+j). \end{aligned}$$

Dans la première somme, posons $r=j+1$. Pour $1\leqslant r\leqslant k$, le coefficient de $f(x+r)$ devient

$$(-1)^{k+1-r} \left( \binom{k}{r-1}+\binom{k}{r} \right) = (-1)^{k+1-r}\binom{k+1}{r},$$

par la relation de Pascal. Les deux termes extrêmes ont eux aussi les coefficients attendus. La formule est donc vraie à l’ordre $k+1$.

7. Écrivons, de façon unique,

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

La question 4 donne, pour $0\leqslant j\leqslant n$,

$$\Delta^jP =\sum_{k=j}^{n}a_kB_{k-j}.$$

Or

$$B_0(0)=1 \qquad\text{et}\qquad B_r(0)=0\quad(r\geqslant1).$$

En évaluant en $0$, seul le terme $k=j$ subsiste :

$$\boxed{a_j=\Delta^jP(0).}$$

On obtient la formule de reconstruction

$$\boxed{ P(X)=\sum_{k=0}^{n}\Delta^kP(0)\,B_k(X).}$$

C’est la formule de Newton adaptée aux nœuds équidistants $0,1,\ldots,n$.

D’après la question 6,

$$\boxed{ \Delta^kP(0) = \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}P(j).}$$

Chaque coordonnée de $P$ dans la base $(B_k)$ est donc déterminée par les valeurs $P(0),\ldots,P(k)$. En particulier, les $n+1$ valeurs

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

déterminent toutes les coordonnées de $P$, donc $P$ lui-même.

8. Les différences successives des valeurs données sont

$$(2,3,8,23),$$ $$(1,5,15),$$ $$(4,10),$$

puis

$$(6).$$

Les différences initiales valent donc

$$P(0)=2,\qquad \Delta P(0)=1,\qquad \Delta^2P(0)=4,\qquad \Delta^3P(0)=6.$$

La formule de Newton donne

$$\boxed{P=2B_0+B_1+4B_2+6B_3.}$$

Or

$$B_1=X,\qquad B_2=\frac{X(X-1)}2,\qquad B_3=\frac{X(X-1)(X-2)}6.$$

Ainsi

$$\begin{aligned} P(X) &=2+X+2X(X-1)+X(X-1)(X-2)\\ &=\boxed{X^3-X^2+X+2}. \end{aligned}$$

IV — Inverser $\Delta$ et sommer

9. Écrivons

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

Puisque

$$\Delta B_{k+1}=B_k,$$

le polynôme

$$Q_0=\sum_{k=0}^{d}a_kB_{k+1}$$

vérifie

$$\Delta Q_0=P.$$

Il existe donc toujours une primitive discrète polynomiale.

Si $Q$ est une autre primitive discrète de $P$, alors

$$\Delta(Q-Q_0)=0.$$

La question 2 donne $Q-Q_0\in\mathbb R$. Ainsi toutes les primitives discrètes de $P$ sont

$$\boxed{Q_0+C,\qquad C\in\mathbb R.}$$

Supposons $P$ non nul, de degré $d$ et de coefficient dominant $\alpha$. Toute primitive discrète $Q$ est alors de degré $d+1$. Si son coefficient dominant vaut $\beta$, la question 2 appliquée à $Q$ donne

$$\alpha=(d+1)\beta.$$

Par conséquent

$$\boxed{\beta=\frac{\alpha}{d+1}.}$$

Enfin, pour $a<b$ entiers,

$$P(m)=Q(m+1)-Q(m).$$

La somme télescope :

$$\begin{aligned} \sum_{m=a}^{b-1}P(m) &=\sum_{m=a}^{b-1}\bigl(Q(m+1)-Q(m)\bigr)\\ &=\boxed{Q(b)-Q(a)}. \end{aligned}$$

10. Comme $B_{k+1}$ est une primitive discrète de $B_k$,

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

Pour $k\geqslant0$, on a $B_{k+1}(0)=0$. Donc

$$\boxed{ \sum_{m=0}^{n-1}B_k(m)=B_{k+1}(n)=\binom{n}{k+1}.}$$

Les premières puissances s’écrivent dans la base $(B_k)$ sous la forme

$$X=B_1,$$ $$X^2=B_1+2B_2,$$ $$X^3=B_1+6B_2+6B_3.$$

On en déduit

$$\sum_{m=0}^{n-1}m =\binom n2 =\boxed{\frac{n(n-1)}2},$$

puis

$$\sum_{m=0}^{n-1}m^2 =\binom n2+2\binom n3 =\boxed{\frac{n(n-1)(2n-1)}6},$$

et enfin

$$\sum_{m=0}^{n-1}m^3 =\binom n2+6\binom n3+6\binom n4 =\boxed{\left(\frac{n(n-1)}2\right)^2}.$$

11. Soit $Q$ une primitive discrète de $P$. La question 9 montre que $Q$ est de degré $d+1$ et de coefficient dominant

$$\frac{a}{d+1}.$$

Pour tout $n\in\mathbb N$,

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

Le membre de droite est la valeur en $n$ du polynôme

$$S(X)=Q(X)-Q(0).$$

Soustraire une constante ne change ni le degré ni le coefficient dominant. Ainsi la fonction considérée coïncide sur $\mathbb N$ avec un polynôme de degré

$$\boxed{d+1}$$

et de coefficient dominant

$$\boxed{\frac{a}{d+1}}.$$

Le cas $n=0$ est inclus : la somme est vide et vaut $0=S(0)$.

V — Quand les différences finissent par s’annuler

12. Supposons d’abord qu’il existe $P\in\mathbb R_d[X]$ tel que

$$u_n=P(n)$$

pour tout $n\in\mathbb N$. Alors

$$(\Delta u)_n=P(n+1)-P(n)=(\Delta P)(n).$$

Par récurrence,

$$(\Delta^ku)_n=(\Delta^kP)(n).$$

Comme $\deg P\leqslant d$, la question 3 donne $\Delta^{d+1}P=0$. Donc

$$\Delta^{d+1}u=0.$$

Réciproquement, supposons

$$\Delta^{d+1}u=0.$$

Posons

$$c_k=(\Delta^ku)_0, \qquad 0\leqslant k\leqslant d,$$

et définissons

$$\boxed{ P(X)=\sum_{k=0}^{d}c_kB_k(X).}$$

Ce polynôme appartient à $\mathbb R_d[X]$. Notons

$$v_n=P(n).$$

D’après la relation $\Delta B_k=B_{k-1}$,

$$(\Delta^kv)_0=c_k=(\Delta^ku)_0$$

pour $0\leqslant k\leqslant d$, et $\Delta^{d+1}v=0$.

Considérons $w=u-v$. On a

$$\Delta^{d+1}w=0$$

et

$$(\Delta^kw)_0=0 \qquad(0\leqslant k\leqslant d).$$

La suite $\Delta^dw$ a une différence nulle : elle est donc constante. Son premier terme étant nul, elle est identiquement nulle. Alors $\Delta^{d-1}w$ est à son tour constante et son premier terme est nul ; elle est donc nulle. En descendant ainsi jusqu’à $w$, on obtient

$$w=0.$$

Par conséquent

$$u_n=P(n)$$

pour tout $n\in\mathbb N$.

Nous avons démontré

$$\boxed{ \Delta^{d+1}u=0 \quad\Longleftrightarrow\quad \exists P\in\mathbb R_d[X],\ \forall n\in\mathbb N,\ u_n=P(n).}$$

Le polynôme correspondant est explicitement

$$\boxed{ P(X)=\sum_{k=0}^{d}(\Delta^ku)_0\,B_k(X).}$$

Il est unique : deux polynômes de degré au plus $d$ prenant les mêmes valeurs pour tout $n\in\mathbb N$ ont une infinité de racines après soustraction, donc sont égaux.

Sources

[SOURCE] Isaac Newton — Methodus differentialis. Lien direct [SOURCE] Duncan C. Fraser — Newton's Interpolation Formulas. Lien direct [SOURCE] Charles Jordan — Calculus of Finite Differences. Lien direct