On a souvent besoin de calculer des sommes de la forme $$S_n = \sum_{k=0}^nu_k.$$
peut se trouver en écrivant $$ \begin{matrix} &1 & 2 & 3 &\cdots & n-1& n\\ +&n &n-1&n-2&\cdots &2 &1\\ =&n+1&n+1&n+1&\cdots &n+1 &n+1 \end{matrix}$$ donc $2S_n=n(n+1)$, et $S_n=\frac{n(n+1)}2$.
découle immédiatement de la formule du binôme (et de son interprétation combinatoire).
Par exemple, $$1+2+2^2+2^3+\cdots+2^n=2^{n+1}-1.$$
def S1(n): return sum([k*2**k for k in range(n+1)])
def S2(n): return (n-1)*2**(n+1)+2
[S1(n) for n in range(1,10)]
[S2(n) for n in range(1,10)]
Dans le même genre, $$\sum_{k=0}^n k{n\choose k}=\left.\frac{d}{dx}(1+x)^n\right|_{x=1}=\left.n(1+x)^{n-1}\right|_{x=1}=n2^{n-1}.$$
Par exemple, le calcul de la complexité de l'algorithme de Held-Karp pour le problème du voyageur de commerce conduit à évaluer les trois sommes
$$\left(\sum _{k=2}^{n-1}k(k-1){\binom {n-1}{k}}\right)+(n-1)=(n-1)(n-2)2^{n-3}+(n-1)$$$$ \sum _{k=2}^{n-1}k={n(n-1) \over 2}-1 $$et $$ \left(\sum _{k=2}^{n-1}k{\binom {n-1}{k}}\right)+(n-1)=(n-1)2^{n-2} $$
Nous connaissons bien la deuxième, nous venons juste d'évaluer la troisième, et pour la première, on a $$ \sum _{k=2}^{n-1}k(k-1)x^{k-2}{\binom {n-1}{k}}=\frac{d^2}{dx^2}(1+x)^{n-1}=(n-1)(n-2)(1+x)^{n-3} $$ d'où le résultat annoncé en posant $x=1$.
On veut calculer $$S_p(n) = \sum_{k=0}^{n-1} k^p =0^p+ 1^p+2^p+\cdots+(n-1)^p.$$ On peut former une série génératrice exponentielle (pour $n$ fixé et $p$ variable) $$S(x;n)=\sum_{p\ge 0}S_p(n)\frac{x^p}{p!}=\sum_{p\ge 0}\frac{x^p}{p!}\sum_{k=0}^{n-1} k^p =\sum_{k=0}^{n-1}\sum_{p\ge 0}\frac{(kx)^p}{p!}=\sum_{k=0}^{n-1}e^{kx}=\frac{e^{nx}-1}{e^x-1}.$$
from sympy import *
var('t x') # on prend une variable t plutôt que n pour représenter les polynômes S_p(t)
series((exp(t*x)-1)/(exp(x)-1),x,0,5).removeO().as_poly(x)
_.all_coeffs()
[factor(f[1])*factorial(f[0]) for f in enumerate(_[::-1])]
On voit, sur ces développements (qu'il aurait été difficile de calcculer à la main), que $S_p(t)$ a l'air d'être un polynôme de degré $p+1$.
Peut-on préciser ses coefficients ?
Pour le numérateur $e^{tx}-1$, on connaît la série. Le dénominateur $e^x-1=x+\frac12x^2\cdots$ commence par $x$, son inverse n'est donc pas une série entière. Pour rétablir l'ordre, on écrit $$S(x;t)=\frac{e^{tx}-1}{x}\frac{x}{e^x-1},$$ et on définit les nombres de Bernoulli $B_n$ par $$\frac{x}{e^x-1}=\sum_{n\ge 0}B_n\frac{x^n}{n!}.$$ On a alors $$S(x;t)=\sum_{k\ge 0}\frac{t^{k+1}x^k}{(k+1)!}\sum_{l\ge 0}B_l\frac{x^l}{l!} =\sum_{p\ge 0}\left(\sum_{k=0}^p\frac{B_{p-k}t^{k+1}}{(k+1)!(p-k)!}\right)x^p =\sum_{p\ge 0}\left(\frac{1}{p+1}\sum_{k=0}^p{p+1\choose k}B_{p-k}t^{k+1} \right) \frac{x^p}{p!} $$ Finalement, $$S_p(t)=\frac{1}{p+1}\sum_{k=0}^p{p+1\choose k}B_{p-k}t^{k+1}.$$ Pour calculer les $B_n$, on écrit $$\sum_{k\ge 0}\frac{x^k}{(k+1)!}\sum_{l\ge 0}B_l\frac{x^l}{l!}=1$$ ce qui donne $B_0=1$ et la récurrence $$B_n=-\frac1{n+1}\sum_{k=0}^n{n+1\choose k}B_k$$
bb = {0:Rational(1)}
def B(n):
if n in bb: return bb[n]
else:
bb[n]= -sum([binomial(n+1,k)*B(k) for k in range(n)])/Rational(n+1)
return bb[n]
print([B(n) for n in range(18)])
Les polynômes de Bernoulli sont définis par $$\sum_{n\ge 0}B_n(t)\frac{x^n}{n!} =\frac{xe^{tx}}{e^x-1} =\sum_{n\ge 0}\left(\sum_{k=0}^n{n\choose k}B_{n-k}t^k\right)\frac{x^n}{n!} $$ Les nombres de Bernoulli sont donc les $B_n(0)$, et $$S_p(t)=\frac{B_{p+1}(t)-B_{p+1}(0)}{p+1}.$$
factor((bernoulli(4,t)-bernoulli(4))/4) #sympy les connaît !
L'opérateur de différence finie $\Delta$ est défini par $$\Delta f(t)=f(t+1)-f(t)$$
$$\Delta t^2 = (t+1)^2-t^2 = 2t+1 \not= 2t$$Les polynômes $$(t)_n :=t(t-1)\cdots (t-n+1)\quad\text{et}\quad (t)^n:=t(t+1)\cdots(t+n-1)$$ ont l'intéressante propriété $$\Delta (t)_n =(t+1)t(t-1)\cdots(t-n+2)-t(t-1)\cdots (t-n+1)=[(t+1)-(t-n+1)]t(t-1)\cdots(t-n+2)=n(t)_{n-1}$$ et de même, $\Delta(t)^n=n(t)^{n-1}$.
La différence finie $$\Delta_hf(t)=\frac{f(t+h)-f(t)}{h}$$ sert à approximer la dérivée en calcul numérique, et les $(t;h)_n=t(t-h)\cdots(t-(n-1)h)$ remplacent les puissances ordinaires. Quitte à changer les unités, on peut supposer $h=1$ pour avoir des formules plus simples. On va se servir de ces propriétés pour calculer des sommes.
En effet, d'un côté $$\sum_{t=0}^{n-1}\Delta (t)_{p+1} = (p+1)\sum_{t=0}^{n-1}(t)_p$$ et de l'autre, $$\sum_{t=0}^{n-1}\Delta (t)_{p+1}= \sum_{t=1}^n(t)_{p+1}-\sum_{t=0}^{n-1}(t)_{p+1}=(n)_{p+1}-(0)_{p+1}=(n)_{p+1}.$$ Donc, $$\sum_{t=0}^{n-1}(t)_p=\frac{(n)_{p+1}}{p+1}.$$ C'est l'analogue "discret" de $$\int_a^bx^pdx=\left[\frac{x^{p+1}}{p+1}\right]_a^b$$ et on pose (notation de Knuth) pour mettre en évidence l'analogie $$\Sigma_a^b f(t)\delta t =\sum_{t=a}^{b-1}f(t)$$ de sorte que $$\Sigma_a^b (t)_p\delta t = \left[\frac{(t)_{p+1}}{p+1}\right]_a^b$$
On peut maintenant calculer les sommes d'entiers consécutifs : $(t)_2=t(t-1)=t^2-t$, et $$\sum_{t=0}^{n-1}(t)_2=S_2(n)-S_1(n) =S_2(n)-\frac{n(n-1)}2 $$ donc $$S_2(n)= \frac{n(n-1)(n-2)}{3}+\frac{n(n-1)}2=\frac{n(n-1)(2n-1)}{6}. $$
Les coefficients des polynômes $(t)_n$ sont appelés nombres de Stirling signés de première espèce $$(t)_n = \sum_{k=0}^n s(n,k)t^k.$$ On peut calculer $$(t)_1=t,\ (t)_2=t^2-t,\ (t)_3= t^3-3t^2+2t,\ (t)_4=t^4-6t^3+11t^2-6t,\ \ldots$$ et en déduire dans l'autre sens $$t=(t)_1,\ t^2=(t)_2+(t)_1,\ t^3=(t)_3+3(t)_2+(t)_1,\ t^4=(t)_4+7(t)_3+6(t)_2+(t)_1.$$ Les coefficients du développement de $t^n$ sur les $(t)_k$ sont les nombres de Stirling se seconde espèce, notés $S(n,k)$ ou $\left\{n\atop k\right\}$. $$t^n=\sum_{k=0}^nS(n,k)(t)_k.$$
Ce sont bien sûr les mêmes que ceux rencontrés au cours précédent. On avait défini $S(n,k)$ comme le nombre de partitions en $k$ blocs d'un ensemble de $n$ éléments, et vu que la série génératrice des polynômes de Touchard $$T_n(t) = \sum_{k=0}^nS(n,k)t^k$$ était $$\sum_{n\ge 0}T_n(t)\frac{x^n}{n!}=e^{t(e^x-1)}.$$ La SGE des polynomes $(t)_n$ est $$\sum_{n\ge 0}(t)_n \frac{x^n}{n!}=\sum_{n\ge 0}{t\choose n}x^n =(1+x)^t$$ Si on remplace $x$ par $e^x-1$ dans cette égalité, on trouve $$(1+e^x-1)^t =e^{tx}.$$ Par ailleurs, en comparant $$e^{t(e^x-1)}=\sum_{n\ge 0}\sum_{k=0}^nS(n,k)t^k\frac{x^n}{n!}\quad (1)$$ et $$e^{t(e^x-1)}=\sum_{k\ge 0}\frac{t^k}{k!}(e^x-1)^k \quad(2)$$ on voit que si l'on remplace $t^k$ par $(t)_k$ dans (2), cette expression devient $$(1+(e^x-1))^t = e^{tx}$$ qui doit aussi être le résultat du remplacement de $t^k$ par $(t)_k$ dans (1), donc $$\sum_{n\ge 0}\sum_{k=0}^nS(n,k)(t)_k\frac{x^n}{n!}=e^{tx}=\sum_{n\ge 0}\frac{t^nx^n}{n!}$$ Par conséquent, $$t^n =\sum_{k=0}^nS(n,k)(t)_k.$$ C'est cette formule qui permet le calcul des $S_p(n)$ : $$\sum_{k=0}^{n-1}k^p = \sum_{k=0}^{n-1}\sum_{j=0}^pS(p,j)(k)_j =\sum_{j=0}^pS(p,j)\frac{(n)_{j+1}}{j+1}$$
Le nombres de Stirling verifient des récurrences simples analogues au triangle de Pascal.
Commençons par les Stirling1 non signés : $$\left[n\atop k\right] =|s(n,k)|\ \text{est le coefficient de $t^k$ dans $(t)^k=t(t+1)\cdots(t+k-1)$} $$ Il suffit d'écrire $$(t)^n = (t)^{n-1}\times (t+n-1)$$ de sorte que le coefficient de $t^k$ dans $(t)^n$ est égal à $(n-1)$ fois celui de $t^{k}$ dans $(t)^{n-1}$, plus celui de $t^{k-1}$, soit $$\left[n\atop k\right]=\left[n-1\atop k-1\right]+(n-1)\left[n-1\atop k\right].$$ Pour les nombres signés, on écrit $(t)_n=(t)_{n-1}(t-n+1))$, ce qui donne $$s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k).$$ Quant on nombre de seconde espèce, comme on sait que $S(n,k)$ est le nombre de partitions en $k$ blocs de $\{1,2,\ldots,n\}$, on peut dire qu'une telle parition peut s'obtenir en ajoutant un bloc $\{n\}$ à une partition de $\{1,2,\ldots,n-1\}$ en $k-1$ blocs, ($S(n-1,k-1)$ possibilités), soit en insérant $n$ dans un bloc d'une partition de $\{1,2,\ldots,n-1\}$ en $k$ blocs ($kS(n-1,k)$ possibilités). Donc, $$ \left\{n \atop k\right\} = \left\{n-1\atop k-1\right\}+k\left\{n-1\atop k\right\}.$$ C'est donc comme dans le triangle de Pascal, mais dans un cas l'élément du dessus est multiplié par son numéro de ligne, et dans l'autre par son numéro de colonne.
On peut vérifier que $\left[n\atop k\right]$ est égal au nombre de permutations de $[n]$ ayant exactement $k$ cycles : on peut ajouter un cycle $(n)$ à une permutation de $[n-1]$ à $k-1$ cycles ($\left[n-1\atop k-1\right]$ choix), ou insérer $n$ dans un cycle d'une permutation de $n-1$ à $k$ cycles. Il faut choisir l'élément qui le précède, donc on a $(n-1)\left[n-1\atop k\right]$ choix.
On pourra consulter la page Wikipedia consacrée aux nombres de Stirling.