Multivariable function analysis

Question

Sorry if the terms I'm going to use is not professional enough:) This is about the complexity analysis of an algorithm.

Let $\alpha$ be the greatest real root of the polynomial $f(x)=x^n-2x^{n-1}-x^{n-k}-2^k$, in which $k$ is a parameter.

The question is how to choose $k$, $(k=\beta n, 0<\beta<1)$ in order to minimize $\alpha$?

We believe that $g$ exists because to minimize $\alpha$, the term $2^k$ requires a small $k$ while the rest needs a big $k$.

Thank you in advance for any idea.

UPDATE:
We've just updated the recurrence relation, the idea is still the same. $k$ is still a relative value to $n$. Let $k=\beta n$. Then the new recurrence is
$f(x)=x^n-3x^{n-1}+x^{n-2}-x^{n-\beta n}-3^{\beta n}+3^{\beta (n-1)}$ Perhaps we can get more information from this one?

Answer 1

Let's write the function as $f(x,k)$.

For $k = 0$, the polynomial $f(x,0) = - 2 x^{n-1} - 1$ has no positive roots. For $k = 1$, $f(x,1) = x^n - 3 x^{n-1} - 2$ has a real root greater than $3$. For $k = 2$, $f(x,2) = x^{n-2} (x^2 - 2 x - 1) - 4 > 0$ if $x \ge 3$ and $n \ge 3$. For $k = n$, $f(x,n) = x^{n-1}(x - 2) - 1 - 2^n > 0$ if $x \ge 3$ and $n \ge 3$. Now $f(x,k)$ is a concave function of $\log_2(k)$ for fixed $x > 1$, so $f(x,k) > 0$ if $x \ge 3$, $n \ge 3$ and $2 \le k \le n$. Thus if $n \ge 3$, the greatest real root of $f(x,k)$ for integers $0 \le k \le n$ occurs at $k=1$.

Since the companion matrix of the polynomial $f(x,k)$ has nonnegative entries, the Perron-Frobenius theorem shows that the greatest real root is also the greatest in absolute value.

If we plot the roots, the picture is rather striking. Here is an animation showing the case $n=100$. For each $k\ge 1$ it appears that we have one positive root (near $x=3$ for $k=1$, decreasing rapidly to near $2$, and finally increasing slightly for $90 < k \le 100$), the other roots almost in a circle centred at $0$, of radius less than the real root, that expands as $k$ increases.