Faulhaber-Knuth

Magnéthorax

Bonjour,

Voici une courte note sur un sujet éculé : les sommes $\sum_{k=1}^n k^p$. Tout retour est le bienvenu.

Sommation itérée d'une puissance impaire des premiers entiers - Archive ouverte HAL (archives-ouvertes.fr)

M

Magnéthorax

Je me permets un petit tour d'ascenseur.

Magnéthorax

Bonjour
Il est bien connu que $$\sum_{k=1}^n k^3 = \binom{n+1}{2} ^2
$$ Il est moins connu que $$
\sum_{k=1}^n \sum_{\ell=1}^{k} \ell^3 = \frac{3}{10}\left(n^2+2n+\frac{1}{3}\right)  \binom{n+2}{3}
$$Dans la note ci-dessus, j'explique comment généraliser en$$\sum_{k_1=1}^n \sum_{k_2=1}^{k_1} \cdots \sum_{k_r=1}^{k_{r-1}} k_r^{2i-1} = \text{un polynôme en } \left(n+r\right)n \text{ à coefficients rationnels} \times \binom{n+r}{r+1}
$$C'est vieux (Faulhaber, première moitié du 17ème siècle). Il semble que la première démonstration rigoureuse soit due à Knuth (années 90), pour laquelle il introduit la notion de fonction $r$-réflexive. En piquant des idées dans son propre article, j'ai l'impression de faire plus rapide et plus explicite que lui.
Edit : correction. Merci @jandri.

jandri

Magnéthorax a dit :

Il est moins connu que $$
\sum_{k=1}^n \sum_{\ell=1}^{k} \ell^3 = \frac{3}{10}\left(n^2+2n+\frac{1}{3}\right)  \left(\sum_{k=1}^n k \right)^2
$$

Il y a une erreur dans cette formule, je trouve $\dfrac{n(n+1)(n+2)}{20}\left(n^2+2n+\dfrac{1}{3}\right)$.

Magnéthorax

Merci de ton retour. Dans la note, cette erreur n'est pas commise. Je corrige dans le message précédent.

jandri

Effectivement c'est bien cela que donne la note que tu as écrite.
Ta démonstration est très courte et élémentaire, j'avais seulement été un peu découragé en voyant l'expression de $\Pi_{i,r}$ en fonction des $a_{i,j}$ et des $P_{i,r}$ eux-mêmes un peu compliqués.
Mais pour une application numérique (par exemple $r=3$ et $i=2$ ou $i=3$) le résultat est simple.

Magnéthorax

Ce qui m'échappe un peu, c'est que les polynômes binomiaux $\left(\binom{X+j-1}{2j-1}\right)_{1\leq j \leq i}$ et les $a_{i,j}$ pour décomposer $X^{2i-1}$ sont bien mentionnés par Knuth dans son article, mais il ne les utilise pas pour démontrer le résultat de Faulhaber. Je doute qu'il soit passé à côté.

jandri

Je ne connaissais pas ces polynômes binomiaux et je n'ai pas trouvé les $a_{i,j}$ sur l'OEIS.

Magnéthorax

Pour les entiers positifs $a_{i,j}$, Knuth renvoie à Riordan (Combinatorial identities, 1968, p. 213). Ce dernier les appelle les nombres factoriels centraux de seconde espèce. Knuth donne leur fonction génératrice. En fouillant, il existe sans doute une interprétation combinatoire de ces $a_{i,j}$.

Magnéthorax

Bonjour,
Dans la note en pièce jointe, mieux rédigée et plus complète que la précédente, je démontre une propriété de l'endomorphisme
$$
\Sigma :
\left\{
\begin{array}{ccc}
\mathbf{Q}\left[X\right] & \longrightarrow & \mathbf{Q}\left[X\right]\\
P & \longmapsto & \left(n\in \N \mapsto \sum_{k=1}^n P\left(k\right)\right)
\end{array}
\right.
$$
Plus précisément, cela concerne l'itération de $\Sigma$. Le résultat en question date de la première moitité du 17ème siècle ! Je pense que la première démonstration remonte aux années 1990, ce qui est sûrement dû à l'oubli plutôt qu'à la difficulté.

jean lismonde

Bonjour

Je confirme le résultat de Jandri concernant la somme S(n) de Magnétorax, somme que l'on peut écrire :

$S(n) = \Sigma_{k=1}^{n}[\frac{k(k+1)}{2}]^2 = \frac{1}{4}\Sigma_1^nk^4 + \frac{1}{2}\Sigma_1^n.k^3 + \frac{1}{4}\Sigma_1^nk^2$

et en utilisant les formules de sommation bien connues, il vient 

$S(n) = \frac{n(n+1)(2n+1)(3n^2 + 3n -1)}{120} + \frac{n^2(n+1)^2}{8} + \frac{n(n+1)(2n+1)}{6}$
et après réduction et factorisation ultime il vient

$S(n) = \frac{n(n+1)(n+2)(3n^2 + 6n + 1)}{60}$

remarque sur les polynômes factoriels (ici prospectifs et au carré)
ils interviennent assez souvent en algèbre et analyse
en particulier dans la détermination des formules de sommation $S_p(n)$
avec $S_p(n) = 1 + 2^p + 3^p + .............+ n^p$
par exemple pour $S_{p-1}(n)$ et les polynômes factoriels rétrospectifs en p entier naturel 

$$(n+1)^p = pS_{p-1}(n) + \frac{p(p-1)}{2!}S_{p-2}(n) +........+\frac{p(p-1)(p-2).....(p-k+1)}{k!}S_{p-k}(n) + .....+ pS_1(n) + n + 1$$

Faulhaber les a étudiés précisément début 17ème siècle
mais Viète fin 16ème siècle, mathématicien français et ministre du roi Henri III 
avait déjà déterminé les formules de sommation (qui intéressent notre ami Magnétorax) jusqu'à p = 10

on peut démontrer que ces formules de sommation à partir de p = 4
ne sont pas factorisables complètement en binômes affines
mais le terme $\frac{n(n+1)}{2}$ apparaît toujours devant en facteur

d'autre part il existe une autre relation de récurrence entre les $S_p(n)$ par l'intermédiaire des nombres Q de Newton  soit 
$Q_pS_p(n-1) + Q_{p-1}S_{p-1}(n-1) + ...............+ Q_1S_1(n-1) + Q_0S_0(n-1) = 0$

enfin il faut signaler les liens de $S_p(n)$ avec les polynômes de Bernoulli $A_{p+1}(x)$ de variable x réelle et d'indice p + 1
soit $S_p(n) = \frac{A_{p+1}(n+1) - A_{p+1}(0)}{p+1}$

Cordialement

Magnéthorax

@jean lismonde : ce que j'écris concerne l'itération de la sommation, ce qui semble moins connu que la sommation. Et pour cause.