# Minimizing a function over two variables

Given two natural numbers $i$ and $p$ such that $0 < i \leqslant 2^p$, let $$\psi(p,i) := p - \alpha + 1 - \frac{1}{2^p}\left((2^p+i)\lg(2^p+i) - i\lg i - i + \alpha - \frac{2^p}{i+1} - \frac{i}{2^p+1}\right),$$ where $\alpha \simeq 1.264499$ and $\lg n$ is the binary logarithm of $n$. I am looking for $\min_{p,i}\psi(p,i)$.

It seems that $\min_{i}\psi(p,i) = \psi(p,2^p)$ or $\psi(p,2^p-1)$. Anyway, I can then minimize over $p$.

We have $$\frac{\partial\psi}{\partial i}(p,i) = - \frac{1}{(i+1)^2} - \frac{1}{2^p}\left(\lg(2^p+i) - \lg i - \frac{1}{2^p+1} - 1\right).$$ (The derivative with respect to $p$ is much worse.) Also $$\lim_{i \rightarrow 0^{+}}\frac{\partial\psi}{\partial i}(p,i) = -\infty,\quad \text{and}\quad \left.\frac{\partial\psi}{\partial i}(p,i)\right|_{i=2^p} \!\!= \frac{1}{2^p(2^p+1)^2} > 0.$$ The derivative is strictly increasing (the second derivative is positive). How can I prove that the root of $\partial\psi/\partial i = 0$ is between $i=2^p-1$ and $i=2^p$? And which of these values is the minimum?

-
Something can't be right in your minimum formula. You take the minimum over $p$ and $i$ and the result still contains $p$? –  Raskolnikov Sep 5 '12 at 10:19
@Raskolnikov: You are right. Fixed. –  Christian Sep 5 '12 at 10:27

It is tedious, even with the help of some computer algebra system, to check that $\left.\partial\psi/\partial i\right|_{i=2^p-1} < 0$, so the root is indeed between $2^p-1$ and $2^p$. It is then fastidious to check that $\psi(p,2^p-1) > \psi(p,2^p)$, so $\min_{0<i\leqslant 2^p}\psi(p,i) = \psi(p,2^p)$.
After that, the minimization of $\psi(p,2^p)$ yields $\min_{0 < p, 0 < i \leqslant 2^p}\psi(p,i) = -\alpha$.