# Concerning the identity in sums of Binomial coefficients

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?

• $\sum_{k=s}^n \binom{k}s=\binom{n+1}{s+1}$. This is the Hockey Stick identity. – Mike Earnest Jan 29 at 1:24
• The question is to find such polynomial $F_s(n,k)$ that $\sum_{k}^{n}\binom{k}{s}=\sum_{k}^{n}F_s(n,k)$. From our example it follows that: $F_2(n,k)=k(n-k)$ and $\sum_{k=1}^{n}\binom{k}{2}=\sum_{k=1}^{n}F_2(n,k)$. Can you provide examples for $s>2$? – Petro Kolosov Jan 29 at 1:33
• I understand now. Still, my comment just shows that $P_s(n)$ is nothing mysterious. – Mike Earnest Jan 29 at 1:51
• Why don't you mention your previous question math.stackexchange.com/q/2774300 ? – Jean Marie Jan 30 at 18:25
• thank you for reminding, by the way these coefficients could be found as \begin{equation} (2k-1)!T(2n,2k)=\frac{1}{r}\sum_{j=0}^{r}(-1)^j\binom{2r}{j}(r-j)^{2n}, \end{equation} where $r=n-k+1$ and $T(2n,2k)$ is central factorial number – Petro Kolosov Jan 30 at 18:30

## 2 Answers

$$\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)$$.

• Can you show me a direct example for $s=2$ step by step ? The example of $\sum_{k=1}^n\binom{k}{s}$ please – Petro Kolosov Jan 29 at 1:53
• @PetroKolosov When $s=2$, you get $F_s(n,k)=k(n-k)$, just as you had. When $s>2$, the expression $k\binom{n-k}s$ is polynomial in disguise. For example, $F_3(n,k)=k\binom{n-k}2=k(n-k)(n-k-1)/2$. – Mike Earnest Jan 29 at 2:36
• Are you sure that $F_3(n,k)=k(n-k)(n-k-1)/2$? For me it gives as follows: $F_s(n,k)=k\binom{n-k}{s-1}$, by the hockey stick pattern: $\binom{n-k}{s-1}=\sum_{j}^{n-k+1}\binom{j}{s-2}|_{s=3}=1/2 (-2 + k - n) (-1 + k - n)$ and multiplication by $k$ gives $F_3(n,k)=1/2 k (-2 + k - n) (-1 + k - n)$. PS and obviously i wrong with limits of hockey stick pattern :) – Petro Kolosov Jan 29 at 3:09
• I've fixed the error above, but still $F_s(n,k)=k\binom{n-k}{s-1}$, by the hockey stick pattern: $\binom{n-k}{s-1}=\sum_{j}^{n-k-1}\binom{j}{s-2}|_{s=3}=1/2 (k - n) (1 + k - n)$ and multiplication by $k$ gives $F_3(n,k)=1/2 k (k - n) (1 + k - n)$ is different from your example of $F_3(n,k)$ – Petro Kolosov Jan 29 at 3:18
• $k(n-k)(n-k-1)/2=\frac12k(k-n)(1+k-n)$. Your expression and mine for $F_3(n,k)$ are the same. All you did was expand $\binom{n-k}{s-1}$ using the HS identity, and then collapse it using the same identity. @PetroKolosov – Mike Earnest Jan 29 at 3:37

I would say that you have a good answer already. But their are other possible answers which seem reasonable. Further restriction might force the favored solution above.

In the case $$k=3$$ (which is the only one I will discuss in any detail)

$$\sum_{s=1}^n\binom{s}3= \\ \sum_{s=1}^ns\binom{n-s}2=\sum_{s=1}^n(n-s)\binom{s}2=\frac14\sum_{s=1}^n{s(n-s)(n-2)}=\frac1{24}\sum_{s=1}^n{(n+1)(n-1)(n-2)}$$

It is easy to see how to generalize these to other $$k.$$

The first three belong to the infinite family

$$\frac14\sum_{s=1}^n{s(n-s)(\alpha n-(2\alpha -2)s-2)} \tag{*}$$

Going back to the favored solution:

$$\sum_{s=1}^n\binom{s}3=\sum_{s=1}^n\frac{s^3}{6}-\frac{s^2}{2}+\frac{s}{3}=\sum_{s=1}^n\frac{n^2s}2-n{s}^{2}+\frac{s^3}2-\frac{ns}{2}+\frac{s^2}2.$$

If you wanted the thing on the right to be

$$\sum_{s=1}^nA{n^2s}+Bn{s}^{2}+C{s^3}+D{ns}+E{s^2}$$

Then you do need to have $$E=\frac12$$ But the rest have two degrees of freedom

$$C=-2A-\frac43B \ \ \ \ \ \ \ D=A-\frac13B-\frac23$$

For further restriction we might want to have $$D=-E=-\frac12$$ so than $$A{n^2s}+Bn{s}^{2}+C{s^3}+D{ns}+E{s^2}=0$$ when $$s=n$$

In this case the summand factors (of course) giving the family $$(*)$$ above.

If we want the right-hand side to be

$$K\sum_{s=1}^ns(An+(1-A)s+B)(Cn+(1-C)s+D)$$

It is possible to work out the requirements. I came up with $$6$$ families of solutions. Of course the set of solutions is invariant under switching the two terms and/or substituting $$s=n+1-s.$$