Let be the following identity
$$\sum_{k=1}^{n}\binom{k}{2}=\sum_{k=0}^{n-1}\binom{k+1}{2}=\sum_{k=1}^{n}k(n-k)=\sum_{k=0}^{n-1}k(n-k)=\frac16(n+1)(n-1)n$$
As we can see the partial sums of binomial coefficients are expressed in terms of $3$-rd order polynomial $P_3(n)$, where $n$ is variable of upper bound of summation. We assume that order of resulting polynomial $P_3(n)$ depends on subscript of binomial coefficient being summed up (in our case the order of polynomial is $3=2+1$, where $2$ is subscript of bin. coef.)
The question:
Does there exist a generalized method to represent the sum of binomial coefficients $\sum_{k}^{n}\binom{k}{s}$ in terms of certain polynomials $P_{s+1}(n)=\sum_{k}^{n} F_s(n,k)$ for every non-negative integer $s$? I.e can we always find the function $F_s(n,k)$, such that $\sum_{k}^{n}\binom{k}{s}=\sum_{k}^{n}F_s(n,k)$ ? We assume that order of polynomial is $s+1$ by means of example above.
The sub-question: (In case of positive answer to the first question.) If there exists a method to represent the sums of bin. coef. in terms of polynomials in $n$, how do summation limits of the $\sum_{k}^{n}\binom{k}{s}$ implies to the form of polynomial $P_{s+1} (n)$ exactly?
Best Answer
$$ \sum_{k=0}^n\binom{k}s=\sum_{k=0}^n\sum_{i=0}^{k-1}\binom{i}{s-1}=\sum_{i=0}^{n-1}\sum_{k=i+1}^n\binom{i}{s-1}=\sum_{i=0}^{n-1}(n-i)\binom{i}{s-1}=\sum_{i=1}^ni\binom{n-i}{s-1} $$ In other words, you can let $F_s(n,k)=k\binom{n-k}{s-1}$, and you will have $\sum_{k=0}^n \binom{k}s=\sum_{k=0}^{n}F_s(n,k)$.