5

During work on my thesis, I am working on formulating a solution to some problem and I came across a huge and very complicated formula.

I tried plugging in a lot of different values and I have evidence that it can be simplified.

The formula is as follows:

$n$ is an integer bigger than one

$k$ is an integer which is smaller than $n$ and bigger than one.

$$\frac{1}{n}\sum_{i=1}^{n}{\sum_{r'=1}^{n}{ \sum_{c=0}^{i-1}\frac{{{r'-1}\choose{c}}{{n-r'}\choose{i-c-1}}}{{{n-1}\choose{i-1}}}\cdot\frac{ \sum_{r=n-k+1}^{n}{{{r-1}\choose{c}}{{n-r}\choose{i-c-1}}{}}}{ \sum_{r=c+1}^{n}{{{r-1}\choose{c}}{{n-r}\choose{i-c-1}}{}}}}}$$ As I mentioned, I plugged in lots of different values for $n$ and $k$ and the expression always evaluated $k$. Is it true that it always is equal to $k$?

Ran Elgiser
  • 63
  • 2
    What's your evidence that it can be simplified? In general it's a good idea to provide context to your question (such as where this expression came from and why you think it can be simplified). – skyking Oct 30 '19 at 10:27
  • @skyking Added a better explanation – Ran Elgiser Oct 30 '19 at 10:30
  • @PeterTaylor Made a mistake, fixed now – Ran Elgiser Oct 30 '19 at 11:02
  • You have $r'$s in a few places and $r$s in a few others; are those the same variable? – Steven Stadnicki Oct 30 '19 at 14:54
  • Did you try writing it down with factorials everywhere? Might not provide the full simplification you are looking for but it might as well induce somme cancelations that could help for the first steps. –  Oct 30 '19 at 15:03
  • Maybe I've got a bug in my code, but I'm not seeing many integers, let alone values equal to $k$. – Peter Taylor Oct 30 '19 at 21:34
  • 1
    @PeterTaylor I made a mistake, c starts from 0 and not 1, fixed it and tried your code with that modification and it returns k just like in my experiments. – Ran Elgiser Nov 02 '19 at 12:29
  • @RobinCarlier I did try but without success, maybe I'm just not smart enough haha – Ran Elgiser Nov 02 '19 at 12:29
  • @StevenStadnicki They are not, sorry for the confusion – Ran Elgiser Nov 02 '19 at 12:29
  • Ok, with that tweak it seems that $${\sum_{r'=1}^{n}{ \sum_{c=0}^{i-1}\frac{{{r'-1}\choose{c}}{{n-r'}\choose{i-c-1}}}{{{n-1}\choose{i-1}}}\cdot\frac{ \sum_{r=n-k+1}^{n}{{{r-1}\choose{c}}{{n-r}\choose{i-c-1}}{}}}{ \sum_{r=c+1}^{n}{{{r-1}\choose{c}}{{n-r}\choose{i-c-1}}{}}}}} = k$$ for every $1 \le i \le n$, which simplifies things slightly... – Peter Taylor Nov 02 '19 at 12:50

1 Answers1

1

Original goal

You want to show that $$\frac{1}{n}\sum_{i=1}^n \sum_{r'=1}^n \sum_{c=0}^{i-1} \frac{\binom{r'-1}{c} \binom{n-r'}{i-c-1}}{\binom{n-1}{i-1}} \frac{ \sum_{r=n-k+1}^n \binom{r-1}{c} \binom{n-r}{i-c-1} }{ \sum_{r=c+1}^{n}\binom{r-1}{c} \binom{n-r}{i-c-1} } = k$$

But some empirical investigation suggests that a stronger statement is true, so my revised goal is

$$\sum_{r'=1}^n \sum_{c=0}^{i-1} \binom{r'-1}{c} \binom{n-r'}{i-c-1} \frac{ \sum_{r=n-k+1}^n \binom{r-1}{c} \binom{n-r}{i-c-1} }{ \sum_{r=c+1}^{n}\binom{r-1}{c} \binom{n-r}{i-c-1} } = k \binom{n-1}{i-1}$$

Revised goal

If we start by reversing the order of the summations, we find that there's some symmetry which has been hidden:

$$\textrm{LHS} = \sum_{c=0}^{i-1} \frac{ \left[ \sum_{r=1}^n \binom{r-1}{c} \binom{n-r}{i-c-1} \right] \left[ \sum_{r=n-k+1}^n \binom{r-1}{c} \binom{n-r}{i-c-1} \right] }{ \sum_{r=c+1}^{n}\binom{r-1}{c} \binom{n-r}{i-c-1} } \\ = \sum_{c=0}^{i-1} \frac{ \sum_{r=1}^n \binom{r-1}{c} \binom{n-r}{i-c-1} }{ \sum_{r=c+1}^{n}\binom{r-1}{c} \binom{n-r}{i-c-1} } \sum_{r=n-k+1}^n \binom{r-1}{c} \binom{n-r}{i-c-1} \\$$

But when $r-1 < c$, we have $\binom{r-1}{c} = 0$, so the sum on top of the fraction in this new arrangement reduces to the sum on the bottom, and we have the much simpler

$$\textrm{LHS} = \sum_{c=0}^{i-1} \sum_{r=n-k+1}^n \binom{r-1}{c} \binom{n-r}{i-c-1} \\$$

Now let's substitute $s = n-r$:

$$\textrm{LHS} = \sum_{c=0}^{i-1} \sum_{s=0}^{k-1} \binom{n-s-1}{c} \binom{s}{i-c-1} \\$$

and it should be obvious that this can be identically equal to $k \binom{n-1}{i-1}$ iff $$s \ge 0 \implies \sum_{c=0}^{i-1} \binom{n-s-1}{c} \binom{s}{i-c-1} = \binom{n-1}{i-1}$$

But this is just a special case of Vandermonde's identity $$\sum_k \binom{r}{m+k} \binom{s}{n-k} = \binom{r+s}{m+n}$$

QED.

Peter Taylor
  • 13,425
  • Perfect ! Thank you so much I have a very similar formula for which I don't have a simplification. I don't know if this should be in a different question but here it goes:

    $$ \frac{1}{n}\sum_{i=1}^{n}{\sum_{r'=1}^{n}{r' \cdot \sum_{c=1}^{i-1}\frac{{{r'-1}\choose{c}}{{n-r'}\choose{i-c-1}}}{{{n-1}\choose{i-1}}}\cdot\frac{ \sum_{r=n-k+1}^{n}{{{r-1}\choose{c}}{{n-r}\choose{i-c-1}}{}}}{ \sum_{r=c+1}^{n}{{{r-1}\choose{c}}{{n-r}\choose{i-c-1}}{}}}}} $$

    The only difference is the multiplication with $r'$.

     – Ran Elgiser Nov 03 '19 at 09:03
  • Yes, that should be a separate question. I don't think the same techniques will necessarily work. It looks like when $n=k$ you get $n^2$, but otherwise the results are fractional. – Peter Taylor Nov 03 '19 at 21:06