Mixing
Concerning the identity in sums of Binomial coefficients
$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?
combinatorics number-theory binomial-coefficients binomial-theorem
edited Jan 29 at 1:30
ETS1331
392214
asked Jan 29 at 0:40
Petro KolosovPetro Kolosov
115112
$endgroup$
add a comment |
$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?
combinatorics number-theory binomial-coefficients binomial-theorem
edited Jan 29 at 1:30
ETS1331
392214
asked Jan 29 at 0:40
Petro KolosovPetro Kolosov
115112
$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)^jbinom{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
add a comment |
$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?
combinatorics number-theory binomial-coefficients binomial-theorem
edited Jan 29 at 1:30
ETS1331
392214
asked Jan 29 at 0:40
Petro KolosovPetro Kolosov
115112
$endgroup$
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?
combinatorics number-theory binomial-coefficients binomial-theorem
combinatorics number-theory binomial-coefficients binomial-theorem
edited Jan 29 at 1:30
ETS1331
392214
asked Jan 29 at 0:40
Petro KolosovPetro Kolosov
115112
edited Jan 29 at 1:30
ETS1331
392214
asked Jan 29 at 0:40
Petro KolosovPetro Kolosov
115112
edited Jan 29 at 1:30
ETS1331
392214
edited Jan 29 at 1:30
ETS1331
392214
edited Jan 29 at 1:30
ETS1331
392214
392214
asked Jan 29 at 0:40
Petro KolosovPetro Kolosov
115112
asked Jan 29 at 0:40
Petro KolosovPetro Kolosov
115112
asked Jan 29 at 0:40
Petro KolosovPetro Kolosov
115112
115112
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)^jbinom{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
add a comment |
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)^jbinom{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
1
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$
$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$
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$
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$
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)^jbinom{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
$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)^jbinom{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
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
$$
sum_{k=0}^nbinom{k}s=sum_{k=0}^nsum_{i=0}^{k-1}binom{i}{s-1}=sum_{i=0}^{n-1}sum_{k=i+1}^nbinom{i}{s-1}=sum_{i=0}^{n-1}(n-i)binom{i}{s-1}=sum_{i=1}^nibinom{n-i}{s-1}
$$
In other words, you can let $F_s(n,k)=kbinom{n-k}{s-1}$, and you will have $sum_{k=0}^n binom{k}s=sum_{k=0}^{n}F_s(n,k)$.
answered Jan 29 at 1:49
Mike EarnestMike Earnest
26.2k22151
$endgroup$
$begingroup$
Can you show me a direct example for $s=2$ step by step ? The example of $sum_{k=1}^nbinom{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 $kbinom{n-k}s$ is polynomial in disguise. For example, $F_3(n,k)=kbinom{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)=kbinom{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)=kbinom{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
add a comment |
$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}^nbinom{s}3= \ sum_{s=1}^nsbinom{n-s}2=sum_{s=1}^n(n-s)binom{s}2=frac14sum_{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
$$frac14sum_{s=1}^n{s(n-s)(alpha n-(2alpha -2)s-2)} tag{*}$$
Going back to the favored solution:
$$sum_{s=1}^nbinom{s}3=sum_{s=1}^nfrac{s^3}{6}-frac{s^2}{2}+frac{s}{3}=sum_{s=1}^nfrac{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
$$Ksum_{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.$
answered Jan 29 at 6:27
Aaron MeyerowitzAaron Meyerowitz
1,435611
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3091598%2fconcerning-the-identity-in-sums-of-binomial-coefficients%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$$
sum_{k=0}^nbinom{k}s=sum_{k=0}^nsum_{i=0}^{k-1}binom{i}{s-1}=sum_{i=0}^{n-1}sum_{k=i+1}^nbinom{i}{s-1}=sum_{i=0}^{n-1}(n-i)binom{i}{s-1}=sum_{i=1}^nibinom{n-i}{s-1}
$$
In other words, you can let $F_s(n,k)=kbinom{n-k}{s-1}$, and you will have $sum_{k=0}^n binom{k}s=sum_{k=0}^{n}F_s(n,k)$.
answered Jan 29 at 1:49
Mike EarnestMike Earnest
26.2k22151
$endgroup$
$begingroup$
Can you show me a direct example for $s=2$ step by step ? The example of $sum_{k=1}^nbinom{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 $kbinom{n-k}s$ is polynomial in disguise. For example, $F_3(n,k)=kbinom{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)=kbinom{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)=kbinom{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
add a comment |
$begingroup$
$$
sum_{k=0}^nbinom{k}s=sum_{k=0}^nsum_{i=0}^{k-1}binom{i}{s-1}=sum_{i=0}^{n-1}sum_{k=i+1}^nbinom{i}{s-1}=sum_{i=0}^{n-1}(n-i)binom{i}{s-1}=sum_{i=1}^nibinom{n-i}{s-1}
$$
In other words, you can let $F_s(n,k)=kbinom{n-k}{s-1}$, and you will have $sum_{k=0}^n binom{k}s=sum_{k=0}^{n}F_s(n,k)$.
answered Jan 29 at 1:49
Mike EarnestMike Earnest
26.2k22151
$endgroup$
$begingroup$
Can you show me a direct example for $s=2$ step by step ? The example of $sum_{k=1}^nbinom{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 $kbinom{n-k}s$ is polynomial in disguise. For example, $F_3(n,k)=kbinom{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)=kbinom{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)=kbinom{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
add a comment |
$begingroup$
$$
sum_{k=0}^nbinom{k}s=sum_{k=0}^nsum_{i=0}^{k-1}binom{i}{s-1}=sum_{i=0}^{n-1}sum_{k=i+1}^nbinom{i}{s-1}=sum_{i=0}^{n-1}(n-i)binom{i}{s-1}=sum_{i=1}^nibinom{n-i}{s-1}
$$
In other words, you can let $F_s(n,k)=kbinom{n-k}{s-1}$, and you will have $sum_{k=0}^n binom{k}s=sum_{k=0}^{n}F_s(n,k)$.
answered Jan 29 at 1:49
Mike EarnestMike Earnest
26.2k22151
$endgroup$
$$
sum_{k=0}^nbinom{k}s=sum_{k=0}^nsum_{i=0}^{k-1}binom{i}{s-1}=sum_{i=0}^{n-1}sum_{k=i+1}^nbinom{i}{s-1}=sum_{i=0}^{n-1}(n-i)binom{i}{s-1}=sum_{i=1}^nibinom{n-i}{s-1}
$$
In other words, you can let $F_s(n,k)=kbinom{n-k}{s-1}$, and you will have $sum_{k=0}^n binom{k}s=sum_{k=0}^{n}F_s(n,k)$.
answered Jan 29 at 1:49
Mike EarnestMike Earnest
26.2k22151
answered Jan 29 at 1:49
Mike EarnestMike Earnest
26.2k22151
answered Jan 29 at 1:49
Mike EarnestMike Earnest
26.2k22151
answered Jan 29 at 1:49
Mike EarnestMike Earnest
26.2k22151
26.2k22151
$begingroup$
Can you show me a direct example for $s=2$ step by step ? The example of $sum_{k=1}^nbinom{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 $kbinom{n-k}s$ is polynomial in disguise. For example, $F_3(n,k)=kbinom{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)=kbinom{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)=kbinom{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
add a comment |
$begingroup$
Can you show me a direct example for $s=2$ step by step ? The example of $sum_{k=1}^nbinom{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 $kbinom{n-k}s$ is polynomial in disguise. For example, $F_3(n,k)=kbinom{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)=kbinom{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)=kbinom{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
$begingroup$
Can you show me a direct example for $s=2$ step by step ? The example of $sum_{k=1}^nbinom{k}{s}$ please
$endgroup$
– Petro Kolosov
Jan 29 at 1:53
$begingroup$
Can you show me a direct example for $s=2$ step by step ? The example of $sum_{k=1}^nbinom{k}{s}$ please
$endgroup$
– Petro Kolosov
Jan 29 at 1:53
1
1
$begingroup$
@PetroKolosov When $s=2$, you get $F_s(n,k)=k(n-k)$, just as you had. When $s>2$, the expression $kbinom{n-k}s$ is polynomial in disguise. For example, $F_3(n,k)=kbinom{n-k}2=k(n-k)(n-k-1)/2$.
$endgroup$
– Mike Earnest
Jan 29 at 2:36
$begingroup$
@PetroKolosov When $s=2$, you get $F_s(n,k)=k(n-k)$, just as you had. When $s>2$, the expression $kbinom{n-k}s$ is polynomial in disguise. For example, $F_3(n,k)=kbinom{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)=kbinom{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$
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)=kbinom{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)=kbinom{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
$begingroup$
I've fixed the error above, but still $F_s(n,k)=kbinom{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
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
$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
add a comment |
$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}^nbinom{s}3= \ sum_{s=1}^nsbinom{n-s}2=sum_{s=1}^n(n-s)binom{s}2=frac14sum_{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
$$frac14sum_{s=1}^n{s(n-s)(alpha n-(2alpha -2)s-2)} tag{*}$$
Going back to the favored solution:
$$sum_{s=1}^nbinom{s}3=sum_{s=1}^nfrac{s^3}{6}-frac{s^2}{2}+frac{s}{3}=sum_{s=1}^nfrac{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
$$Ksum_{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.$
answered Jan 29 at 6:27
Aaron MeyerowitzAaron Meyerowitz
1,435611
$endgroup$
add a comment |
$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}^nbinom{s}3= \ sum_{s=1}^nsbinom{n-s}2=sum_{s=1}^n(n-s)binom{s}2=frac14sum_{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
$$frac14sum_{s=1}^n{s(n-s)(alpha n-(2alpha -2)s-2)} tag{*}$$
Going back to the favored solution:
$$sum_{s=1}^nbinom{s}3=sum_{s=1}^nfrac{s^3}{6}-frac{s^2}{2}+frac{s}{3}=sum_{s=1}^nfrac{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
$$Ksum_{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.$
answered Jan 29 at 6:27
Aaron MeyerowitzAaron Meyerowitz
1,435611
$endgroup$
add a comment |
$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}^nbinom{s}3= \ sum_{s=1}^nsbinom{n-s}2=sum_{s=1}^n(n-s)binom{s}2=frac14sum_{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
$$frac14sum_{s=1}^n{s(n-s)(alpha n-(2alpha -2)s-2)} tag{*}$$
Going back to the favored solution:
$$sum_{s=1}^nbinom{s}3=sum_{s=1}^nfrac{s^3}{6}-frac{s^2}{2}+frac{s}{3}=sum_{s=1}^nfrac{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
$$Ksum_{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.$
answered Jan 29 at 6:27
Aaron MeyerowitzAaron Meyerowitz
1,435611
$endgroup$
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}^nbinom{s}3= \ sum_{s=1}^nsbinom{n-s}2=sum_{s=1}^n(n-s)binom{s}2=frac14sum_{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
$$frac14sum_{s=1}^n{s(n-s)(alpha n-(2alpha -2)s-2)} tag{*}$$
Going back to the favored solution:
$$sum_{s=1}^nbinom{s}3=sum_{s=1}^nfrac{s^3}{6}-frac{s^2}{2}+frac{s}{3}=sum_{s=1}^nfrac{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
$$Ksum_{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.$
answered Jan 29 at 6:27
Aaron MeyerowitzAaron Meyerowitz
1,435611
edited Jan 31 at 20:19
answered Jan 29 at 6:27
Aaron MeyerowitzAaron Meyerowitz
1,435611
answered Jan 29 at 6:27
Aaron MeyerowitzAaron Meyerowitz
1,435611
answered Jan 29 at 6:27
Aaron MeyerowitzAaron Meyerowitz
1,435611
1,435611
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3091598%2fconcerning-the-identity-in-sums-of-binomial-coefficients%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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)^jbinom{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