La somme $\sum_{k=1}^nk^2$

J'ai toujours personnellement pensé (pour avoir vu des fils compétents, exacts, mais ubuesques dans le passé sur le forum, à base de coefficients binomiaux dans tous les sens, que les preuves guident souvent dans un sens favorables les formules.
Par exemple, pour calculer (ie trouver $Q$ tel que) :
$$
Q(n) = \sum_{i\in n} \ P(n)

$$ je suis "contre" (idéologiquement) se "contenter" des cas particulier $P:=id^k$, puisque la preuve est triviale de
$$
\forall P,\ \exists Q,\ \forall n,\ [Q(n) = \sum_{i\in n} \ P(n)]

$$ alors qu'il n'en existe pas de "faciles" de
$$
\forall k,\ \exists Q,\ \forall n,\ [Q(n) = \sum_{i\in n} \ n^k].

$$ Bon pardon, c'était légèrement HS, mais je pense que ça peut aider des passants, surtout que vue la taille prise par le titre dans la liste des fils, il est difficile de ne pas cliquer dessus :-D (sur mon PC ça occupe la moitié de la liste, c'est rigolo).

Pour tout entier $d\in \N$ et tout polynôme $P\in \R[X]$ de degré $d$, il existe un polynôme $Q$ de degré $d+1$ tel que pour tout entier $n\in \N$, $\ Q(n)=\sum_{k=0}^n P(k)$.

En prouvant ça de façon "naturelle" on va dire, on [a] un algorithme qui apparaît pour calculer $Q$ en fonction de $P$.