I'm trying to understand a paper called "Diameter of Polyhedra: Limits of Abstraction" available here : http://sma.epfl.ch/~eisenbra/Publications/designs.pdf
My problem is with the first two calculations on top of page 790 : I can't understand how it proves the result...
I mean the goal is to show that for $m\geq n$ two non zero integers, given the relation $$\mathrm{h}(n,m) \leq 2\mathrm{h}(n,\lfloor m/2 \rfloor)+\mathrm{h}(n-1,m-1)$$ and knowing that $$\mathrm{h}(1,m)=m \\ \mathrm{h}(n,m)=0,\quad \text{if} \quad n > m$$ then the bound $$h(n,m)\leq m^{1+\log_2(n)}$$is true.
And what is done in the paper basically is : $$ \mathrm{h}(n,m)\leq 2 \mathrm{h}(n,\lfloor m/2 \rfloor)+\mathrm{h}(n-1,m-1) \leq 2\sum_{i=2}^n \mathrm{h}(i,\lfloor m/2\rfloor) + \mathrm{h}(1,m) $$ $$\leq 2(n-1)(2n)^{m-1} + m \leq (2n)^{\log(m)}$$ But I really can't see how $\mathrm{h}(n,m)\leq (2n)^{\log(m)}$ implies that $\mathrm{h}(n,m)\leq m^{1+\log_2(n)}$ holds... Even if supposing that $n,m \geq 2$.
Did I miss something ?
The two terms are equal.
Let $x = (2n)^{\log_2(m)}$ and $y = m^{1 + \log_2(n)}$
$\begin{align}\log_2(x) &= \log_2\left((2n)^{\log_2(m)}\right)\\ &=\left(\log_2(m)\right) \cdot \left(\log_2(2n)\right) \text{ since } \log a^b = b\log a\\&=\left(\log_2(m)\right) \cdot \left(\log_2(2) + \log_2(n)\right) \text{ since } \log ab = \log a + \log b\\&=\left(\log_2(m)\right) \cdot \left(1 + \log_2(n)\right)\end{align}$
$\begin{align}\log_2 (y) &= \log_2\left(m^{1 + \log_2(n)}\right)\\ &=\left(1 + \log_2(n)\right) \cdot \left(\log_ 2(m)\right)\\&=\log_2(x)\\\iff y &= x\end{align}$