2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ $\sum_{k=s}^n \binom{k}s=\binom{n+1}{s+1}$. This is the Hockey Stick identity. $\endgroup$ – Mike Earnest Jan 29 at 1:24
  • $\begingroup$ 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$? $\endgroup$ – Petro Kolosov Jan 29 at 1:33
  • $\begingroup$ I understand now. Still, my comment just shows that $P_s(n)$ is nothing mysterious. $\endgroup$ – Mike Earnest Jan 29 at 1:51
  • $\begingroup$ Why don't you mention your previous question math.stackexchange.com/q/2774300 ? $\endgroup$ – Jean Marie Jan 30 at 18:25
  • $\begingroup$ 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 $\endgroup$ – Petro Kolosov Jan 30 at 18:30
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you show me a direct example for $s=2$ step by step ? The example of $\sum_{k=1}^n\binom{k}{s}$ please $\endgroup$ – Petro Kolosov Jan 29 at 1:53
  • 1
    $\begingroup$ @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$. $\endgroup$ – Mike Earnest Jan 29 at 2:36
  • $\begingroup$ 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 :) $\endgroup$ – Petro Kolosov Jan 29 at 3:09
  • $\begingroup$ 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)$ $\endgroup$ – Petro Kolosov Jan 29 at 3:18
  • 1
    $\begingroup$ $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 $\endgroup$ – Mike Earnest Jan 29 at 3:37
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.