اولاّ فرمولی که گفتین اثبات بشه و فرمول تعداد افراز ها(معروف به اعداد استرلینگ نوع دوم) اشتباه است.
درستش:
$$ \sum_{i=1}^n i^k=\sum_{j=1}^k j!S(k,j) \binom{n+1}{j+1} $$
$$ S(k,i)=\frac{1}{i!} \sum_{j=0}^i {(-1)^{i-j} \binom{i}{j} }j^k $$
برای اثبات فرمول مجموع توان ها از 2 رابطه زیر استفاده میشه که اوّل اون ها رو میگم.
رابطه در اعداد استرلینگ:
$$ x^k= \sum_{i=1}^k S(k,i)(x)_i $$
که $ (x)_m $ ترتیب های m تایی x شیء است و از فرمول
$ (x)_k= k!\binom{x}{k} $ بدست می آید و به ازای $x<k$ حاصل صفر در نظر گرفته می شود.
همچنین رابطه زیر برای مجموع $ (x)_m $ به سادگی قابل اثبات است:
$$ \sum_{x=1}^n (x)_m= \frac{(n+1)_{m+1}}{m+1} $$
اما برای اثبات رابطه مورد سؤال:
$$ \sum_{i=1}^n i^k= \sum_{i=1}^n \sum_{j=1}^k S(k,j)(i)_j = \sum_{j=1}^k S(k,j)\sum_{i=1}^n(i)_j =\sum_{j=1}^k S(k,j) \frac{(n+1)_{j+1}}{j+1}
$$
$$ =\sum_{j=1}^k S(k,j) \frac{(n+1)!}{(j+1)(n-j)!}=\sum_{j=1}^k S(k,j)j! \frac{(n+1)!}{(j+1)j!(n-j)!} $$
$$= \sum_{j=1}^k S(k,j) j! \binom{n+1}{j+1} $$
