Maximize partial sum of binomials

150 Views Asked by At

During my research I got to the point when I need to find

$$ \arg \max_w \left( (n-w) \sum_{j=0}^d \binom{w}{j} \binom{2^r - (j+1) 2^{r-j-1}-2}{t} \right) $$

with respect to $w$ only (i.e. $d$, $n$, $r$ and $t$ are considered as integer constants).

Again, I don't need the value of the maximized expression, I need only $w$ which maximizes the expression.

I could see some obvious conditions on the parameters (like $d \leqslant w$) but nothing interesting.

Combinatorics and sums are not my field so I don't really know what to do with this and what I can do in principle.

Approximations would be fine too, provided they are not too rough. Any hints or links would be also appreciated.

1

There are 1 best solutions below

3
On BEST ANSWER

It seems that many terms are irrelevant in terms of optimization. Thus, we can rewrite the problem as $$ \arg\max_w \left( (n-w)\sum_{j=0}^d {w\choose j}\alpha_j\right) $$ Since the combination numbers can be expressed using gamma function, we can write $$ (n-w)\sum_{j=0}^d {w\choose j}\alpha_j= (n-w)\sum_{j=0}^d \frac{w!}{(w-j)!j!}\alpha_j=(n-w)\sum_{j=0}^d \frac{\Gamma(w+1)}{\Gamma(w-j+1)\Gamma(j+1)}\alpha_j $$ which is continuous in $w$ and can be subject of differentiation and standard optimization methods and tools.