The following equality is true for every positive integer $n$ : $$\sum_{k=0}^n {n \choose k} = 2^n $$ It is a special case ($p = 0$) of the sequence : $$S_{p, n}=\sum_{k=0}^n k^p {n \choose k} $$ For example : $$S_{0,n}= 2^{n} \qquad S_{1,n}=n 2^{n-1} \qquad S_{2,n}=n(n+1)2^{n-2} \qquad S_{3,n}=n^2(n+3)2^{n-3} $$ More generally, we can write : $$S_{p, n} =Q_p(n) 2^{n-p} \qquad deg(Q_p)= p $$ I found the following recurrence relation : $$S_{p+1,n}=\sum_{k=1}^n k^{p+1}{n \choose k}=n\sum_{k=1}^n k^{p}{n-1 \choose k-1} =n\sum_{k=0}^{n-1} (k+1)^{p}{n-1 \choose k} = n\sum_{k=0}^{n-1} \left(\sum_{j=0}^p {p \choose j}k^j \right){n-1 \choose k} $$ Thus, we have : $$S_{p+1,n}=n\sum_{j=0}^p {p \choose j} \left(\sum_{k=0}^{n-1} k^j {n-1 \choose k}\right) =n \sum_{j=0}^p {p \choose j} S_{n-1,j}$$ Now, it is easy to see that : $$Q_{0}(n)= 1 \qquad Q_{p+1}(n)=n\sum_{j=0}^p {p \choose j}2^{p-j} Q_j(n-1)$$
The following python code seems to give right results (verified with Wolfram)
import numpy as np
from math import comb
ps = [np.poly1d([1])]
for _ in range(1, 10):
_q = np.poly1d([1, -1])
_p = np.poly1d([0])
p = len(ps) - 1
for j, poly in enumerate(ps):
s = np.polyval(poly, _q)
fac = np.poly1d([comb(p, j) * 2**(p-j)])
r = np.polymul(s, fac)
_p = np.polyadd(_p, r)
new_p = np.polymul(_p, np.poly1d([1, 0]))
ps.append(new_p)
for x in ps:
print(x)
The output is :
1
1 x
2
1 x + 1 x
3 2
1 x + 3 x
4 3 2
1 x + 6 x + 3 x - 2 x
5 4 3 2
1 x + 10 x + 15 x - 10 x
6 5 4 3 2
1 x + 15 x + 45 x - 15 x - 30 x + 16 x
7 6 5 4 3 2
1 x + 21 x + 105 x + 35 x - 210 x + 112 x
8 7 6 5 4 3 2
1 x + 28 x + 210 x + 280 x - 735 x + 28 x + 588 x - 272 x
9 8 7 6 5 4 3 2
1 x + 36 x + 378 x + 1008 x - 1575 x - 2436 x + 5292 x - 2448 x
For $n\geq 4$, the answer given by Wolfram uses the generalized hypergeometric function, I was wondering if there was a closed "simple" formula for $Q_p$?
