LFD Book Forum - View Single Post

AlexS · #12 01-23-2020, 02:57 AM

Quote:

Originally Posted by joseqft

I´ve been struggling with this problem too. Essentialiy we have to prove that the second expression in the min expression

$7(d_{VC}+K)\log_2(d_{VC}K)$ .

is a valid $\ell$ as explains magdon in

this means that the inequality

$(d_{VC}+K)^{7(d_{VC}+K)} > 2K\left[7(d_{VC}+K)\log_2(d_{VC}K)\right]^{d_{VC}}$ (1)

must be satisfied.

I have been finding upper bounds to the right hand side of (1), using the following tricks

$d_{VC}+K \geq d_{VC}K$ if $d_{VC}\geq 2$ (the case $d_{VC}= 1$ must be proved apart).

$\log_2(d_{VC}K) < d_{VC}K$ ,

$7 < 2^3 \leq K^3$ , because $K \geq 2$ (this is not the seven in the exponent) and

.

Then we arrive at an ASO expression that can be compared easily with the left hand side of (1) proving that this inequality is valid.

I think you will find mistake

it is not hard