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.)