L'opérateur de différence $\Delta P=P(X+1)-P(X)$

Ce qu'on a le droit d'utiliser. Le degré d'une somme et d'un produit, la formule du binôme, la composition $P(X+1)$, et le théorème « un polynôme non nul de degré $d$ a au plus $d$ racines » avec son corollaire « une infinité de racines force le polynôme nul ». La stratégie : $\Delta$ est une dérivée discrète — il abaisse le degré d'une unité, son noyau est réduit aux constantes, et il s'inverse par récurrence sur le degré.

1) $\Delta$ abaisse le degré d'une unité. Écrivons $P={\sum }_{k=0}^n{a}_k{X}^k$ avec $a_n\ne 0$. Par linéarité, $\Delta P={\sum }_{k=0}^n{a}_k((X+1{)}^k-X^k)$. Par le binôme, $(X+1{)}^k-X^k=k{X}^{k-1}+(\text{termes de degreˊ}\le k-2)$ : les termes de degré $k$ se détruisent, et le coefficient de $X^{k-1}$ est $\left(\genfrac{}{}{0ex}{}{k}{k-1}\right)=k$ (se lit « $k-1$ parmi $k$ »). Donc chaque $(X+1{)}^k-X^k$ est de degré $k-1$ pour $k\ge 1$, et nul pour $k=0$. Dans la somme, le terme $k=n$ apporte $n{a}_n{X}^{n-1}$, de degré $n-1$, et les autres sont de degré au plus $n-2$. Donc $\mathrm{deg}\Delta P=n-1$, de coefficient dominant $n{a}_n\ne 0$. Si $P=c$ est constant, $\Delta P=c-c=0$.

2) Le noyau de $\Delta$. Si $P$ est constant, $\Delta P=0$ par le 1). Réciproquement, supposons $\Delta P=0$, c'est-à-dire $P(X+1)=P(X)$. En évaluant en $k\in \mathbb{N}$ : $P(k+1)=P(k)$ pour tout $k$, donc par récurrence $P(k)=P(0)$ pour tout $k\in \mathbb{N}$. Le polynôme $P-P(0)$ admet donc tous les entiers naturels pour racines : une infinité. Il est nul. $P$ est constant. (On pouvait aussi dire : si $\mathrm{deg}P\ge 1$, alors $\mathrm{deg}\Delta P=\mathrm{deg}P-1\ge 0$, donc $\Delta P\ne 0$. Les deux arguments sont bons ; le second est plus court, le premier montre le rôle des racines.)

3) L'équation $\Delta P=X$. Si $P$ est solution, $P$ n'est pas constant ($\Delta P\ne 0$), et par le 1), $\mathrm{deg}P-1=\mathrm{deg}X=1$ : $\mathrm{deg}P=2$. Écrivons $P=a{X}^2+bX+c$ : $$\Delta P=a((X+1{)}^2-X^2)+b((X+1)-X)=a(2X+1)+b=2aX+(a+b).$$ L'identification avec $X$ donne $2a=1$ et $a+b=0$, soit $a=\frac{1}{2}$, $b=-\frac{1}{2}$, et $c$ reste libre. Réciproquement, $P=\frac{X(X-1)}{2}+c$ vérifie $\Delta P=\frac{(X+1)X-X(X-1)}{2}=\frac{X\cdot 2}{2}=X$. Les solutions sont les $\frac{X(X-1)}{2}+c$, $c\in \mathbb{K}$ — une droite affine, comme les primitives d'une fonction. Télescopage : avec $c=0$, sommons $P(k+1)-P(k)=k$ pour $k$ de $0$ à $n-1$ ; la somme de gauche se télescope en $P(n)-P(0)=P(n)$, d'où $$\sum _{k=0}^{n-1}k=P(n)=\frac{n(n-1)}{2}.$$

4) $\Delta$ s'inverse. Existence, par récurrence forte sur $d=\mathrm{deg}Q$. Si $Q=0$, $P=0$ convient. Supposons le résultat acquis pour tous les polynômes de degré $<d$, et soit $Q$ de degré $d\ge 0$, de coefficient dominant $q_d$. Par le 1), $\Delta (X^{d+1})$ est de degré $d$ et de coefficient dominant $d+1$. Donc $Q_1=Q-\frac{q_d}{d+1}\Delta (X^{d+1})$ est de degré $<d$ (les termes de degré $d$ se détruisent) ou nul. Par hypothèse de récurrence, il existe $P_1$ avec $\Delta P_1=Q_1$ et $P_1(0)=0$. Posons $P=P_1+\frac{q_d}{d+1}{X}^{d+1}$ : par linéarité de $\Delta$, $\Delta P=Q_1+\frac{q_d}{d+1}\Delta (X^{d+1})=Q$, et $P(0)=P_1(0)+0=0$. Unicité : si $P$ et $P^{\prime }$ conviennent, $\Delta (P-P^{\prime })=0$, donc $P-P^{\prime }$ est constant par le 2), et cette constante vaut $P(0)-P^{\prime }(0)=0$. Pour tout $Q$, il existe un unique $P$ tel que $\Delta P=Q$ et $P(0)=0.$

5) La somme des carrés. Cherchons $P$ avec $\Delta P=X^2$ et $P(0)=0$ ; par le 1), $\mathrm{deg}P=3$, et $P(0)=0$ : $P=\alpha X^3+\beta X^2+\gamma X$. On calcule $\Delta (X^3)=(X+1{)}^3-X^3=3X^2+3X+1$, $\Delta (X^2)=2X+1$, $\Delta (X)=1$, d'où $$\Delta P=3\alpha X^2+(3\alpha +2\beta )X+(\alpha +\beta +\gamma ).$$ L'identification avec $X^2$ donne $\alpha =\frac{1}{3}$, puis $1+2\beta =0$ soit $\beta =-\frac{1}{2}$, puis $\frac{1}{3}-\frac{1}{2}+\gamma =0$ soit $\gamma =\frac{1}{6}$. Ainsi $$P=\frac{X^3}{3}-\frac{X^2}{2}+\frac{X}{6}=\frac{2X^3-3X^2+X}{6}=\frac{X(X-1)(2X-1)}{6}.$$ Par télescopage de $P(k+1)-P(k)=k^2$ pour $k$ de $0$ à $n-1$ : $$\sum _{k=0}^{n-1}{k}^2=P(n)-P(0)=\frac{n(n-1)(2n-1)}{6}.$$ Contrôle : pour $n=4$, $0+1+4+9=14$ et $\frac{4\cdot 3\cdot 7}{6}=14$. En général, ${\sum }_{k=0}^{n-1}Q(k)=P(n)$ où $P$ est l'inverse de $Q$ par $\Delta$ : toute somme de valeurs d'un polynôme est un polynôme en $n$, de degré un de plus.

Le point délicat. Au 4), l'existence se construit par le terme dominant : on tue le degré $d$ de $Q$ avec un multiple bien choisi de $\Delta (X^{d+1})$, et l'on recommence plus bas. C'est l'algorithme de la division euclidienne, transposé à $\Delta$ ; il ne marche que parce que $\Delta$ abaisse le degré d'exactement une unité, avec un coefficient dominant $d+1$ non nul.

Ce que l'exercice installe. L'opérateur $\Delta$ est le pendant discret de la dérivation — il abaisse le degré, son noyau est fait des constantes, il s'inverse « à une constante près » — et le télescopage est le pendant discret du théorème fondamental de l'analyse. C'est la méthode générale pour sommer $\sum k^m$, et le principe des polynômes de Bernoulli ; on retrouvera $\Delta$ au chapitre 12 comme endomorphisme de ${\mathbb{K}}_n[X]$, nilpotent, de noyau ${\mathbb{K}}_0[X]$.