Timeline for Simplest form for sum of Binomial Expressions
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 26, 2018 at 7:52 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 16, 2016 at 8:34 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jul 17, 2016 at 7:42 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 17, 2016 at 7:34 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 18, 2016 at 6:11 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 24, 2014 at 18:53 | comment | added | The Masked Avenger | For sake of increased clarity, you might add after the word formally: let s and r be variables, and for fixed numerical values of a's and b's consider the function P(s,r) in s and r given by sum. I want to rewrite P(s,r) as a similar sum in fewer terms of s and r, as follows... This way it is more clear to me that the desired identity holds for s and r sufficiently large integers, and perhaps even for s and r small enough for your purposes. | |
| Nov 24, 2014 at 18:25 | comment | added | The Masked Avenger | No problem. Even though I misunderstood your intent (so that my trivial solution does not apply to the general question), I think there are two ways to take my answer and fully bake it. One is to choose several pairs s and r before applying the algorithm, and the other is to change representation: Pick A large enough, represent each of the n summands as a sum of terms (s-A) choose i, add all those "vectors" of length s-A+1 together, and then try the greedy strategy as before. This may only give you an upper bound on m, but it may suggest something else of low time complexity to try. | |
| Nov 24, 2014 at 18:21 | history | edited | Phylliida | CC BY-SA 3.0 |
added 85 characters in body
|
| Nov 24, 2014 at 18:16 | comment | added | Phylliida | @TheMaskedAvenger You're actually very right, sorry. I removed it now and replaced it with Emil's example. | |
| Nov 24, 2014 at 11:21 | comment | added | Emil Jeřábek | @DaniPhye: I think you misunderstood what I said. There is a complete list, and it consists of instances of the Pascal triangle identity. Whether this can give an efficient solution I don't know, but it sort of reduces the problem to linear algebra (find a 0-1 vector of minimal norm in a particular affine space). | |
| Nov 24, 2014 at 3:52 | comment | added | The Masked Avenger | Now that I have read your comments, can you explain to me how your second bulleted example is an example of the problem? It seems the dependence on r makes it not an example. | |
| Nov 23, 2014 at 22:37 | comment | added | Phylliida | @EmilJeřábek Thanks, yes, there are many such identities. It's possible that maybe just compiling a list of all of them - then proving that that list is comprehensive - would be sufficient to solve this problem, but I'm not sure if such a list can be constructed. Also that might just turn it into an NP-Hard or NP-Complete approximation algorithm of needing to "choose the right identities," however I'm not aware of any results showing either - so it's possible that maybe such a list of identities would be constructive in actually providing this reduction efficiently, I'm not sure. | |
| Nov 23, 2014 at 22:18 | comment | added | Phylliida | @TheMaskedAvenger, I think you're misunderstanding the question. In both problems, all $d_i$s and $f_i$s must be a constant (not dependent on $r$), and the relation must hold for any $r$ and $s$ greater than all $a_i, b_i, c_i, d_i$. Thus means $d_i$ can never equal $f_i r-1$ for all $r$ unless $f=0$. I might be misunderstanding your comment though. | |
| Nov 23, 2014 at 20:54 | comment | added | Emil Jeřábek | This doesn’t answer the question, but it is not hard to prove that any linear dependence $\sum_{i=1}^n\alpha_i\binom{r-a_i}{s-b_i}=0$ valid for all sufficiently large $r,s$ is a linear combination of the Pascal triangle identities $\binom{r-a+1}{s-b+1}-\binom{r-a}{s-b+1}-\binom{r-a}{s-b}=0$. | |
| Nov 23, 2014 at 20:30 | answer | added | The Masked Avenger | timeline score: 1 | |
| Nov 23, 2014 at 20:17 | comment | added | The Masked Avenger | For the second more general problem, you can insure m=1 by picking d = fr-1. The first problem looks less trivial to me. | |
| Nov 23, 2014 at 19:24 | comment | added | Phylliida | Sorry! No it was not. I edited the question now. | |
| Nov 23, 2014 at 19:24 | history | edited | Phylliida | CC BY-SA 3.0 |
edited body
|
| Nov 23, 2014 at 11:23 | comment | added | Michael Stoll | In your original sum, `$n$' occurs both as the upper summation limit and in the binomial coefficient. Is this intentional? | |
| Nov 22, 2014 at 23:27 | history | edited | Joonas Ilmavirta | CC BY-SA 3.0 |
added 16 characters in body
|
| Nov 22, 2014 at 23:18 | history | edited | Phylliida | CC BY-SA 3.0 |
deleted 67 characters in body
|
| Nov 22, 2014 at 23:16 | review | First posts | |||
| Nov 22, 2014 at 23:27 | |||||
| Nov 22, 2014 at 23:12 | history | asked | Phylliida | CC BY-SA 3.0 |